Cache management in a mobile device Number:7,143,241 from the United States Patent and Trademark Office (PTO) owispatent A user visiting a space is equipped with a mobile device in communication with a service system. Media items held by the service system are associated with various locations around the space and a user arriving at such a location is presented with the corresponding item or items. These media items are pre-emptively loaded into a cache of the user's mobile device in dependence on the user's progress around the space. Items can also be flushed from cache on this basis.<H management, device, Cache, managemen, 7143241.html, Patent, pto, 7143241

Title: Cache management in a mobile device

Abstract: A user visiting a space is equipped with a mobile device in communication with a service system. Media items held by the service system are associated with various locations around the space and a user arriving at such a location is presented with the corresponding item or items. These media items are pre-emptively loaded into a cache of the user's mobile device in dependence on the user's progress around the space. Items can also be flushed from cache on this basis.

Patent Number: 7,143,241 Issued on 11/28/2006 to Hull

Inventors: Hull; Richard (Bristol, GB)
Assignee: Hewlett-Packard Development Company, L.P. (Houston, TX)

Appl. No.: 10/635,863

Filed: August 5, 2003

Foreign Application Priority Data


Aug 06, 2002 [GB]			0218188.1
Oct 18, 2002 [GB]			0224219.6

Current U.S. Class: 711/133 ; 701/202; 701/209; 702/150; 711/113; 711/137

Current International Class: G06F 12/00 (20060101)

References Cited [Referenced By]

U.S. Patent Documents


6125396	September 2000	Lowe
6480804	November 2002	Maeda et al.
6631322	October 2003	Arthur et al.
6704649	March 2004	Miyahara
6766248	July 2004	Miyahara
6801852	October 2004	Takahashi et al.
6845321	January 2005	Kerns
6934628	August 2005	Harada
6954697	October 2005	Smith
2002/0183072	December 2002	Steinbach et al.
2003/0060973	March 2003	Mathews et al.
2005/0043060	February 2005	Brandenberg et al.
2005/0144049	June 2005	Kuzunuki et al.

Foreign Patent Documents


0 798 934	Oct., 1997	EP
1 039 721	Sep., 2000	EP
2 366 401	Mar., 2002	GB
99/67904	Dec., 1999	WO
01/35575	May., 2001	WO
01/38983	May., 2001	WO
02/089392	Nov., 2002	WO
03/085890	Oct., 2003	WO

Other References

"DARPA ITO Sponsored Research: Pheromone Robotics," INTERNET: <http://www.darpa.mil/ito/psum2001/H892-0.html> 3 pages total (Feb. 26, 2002). cited by other .
"Learning's in the air: museums, microcosms, and the future of the mobile net," Mpulse: A Cooltown Magazine, INTERNET: <http://cooltown.com/mpulse/0901-museums.asp?print=yes> 3 pages total (Mar. 13, 2002). cited by other .
Bederson, B.B., "Audio Augmented Reality: A Prototype Automated Tour Guide," ACM Human Computer in Computing Systems conference(CHI '95), pp. 210-211, INTERNET: <http://www.cs.umd.edu/.about.bederson/papers/chi-95-aar/index.html>- ; 4 pages total (Feb. 2, 2002). cited by other .
Russell, R.A., "Assoc. Prof. Andy Russell," INTERNET: <http://www.ecse.monash.edu.au/staff/rar/> 5 pages total (Aug. 5, 2002). cited by other .
Payton, D., et al., "Pheromone Robotics", Autonomus Robots 11, 319-324 (2001). cited by other .
Spasojevic, M., et al., "A Study of an Augmented Museum Experience", Tech Reports HPL 2001, retrieved May 8, 2006 from http://www.hpl.hp.com/techreports/2001/hpl-2001-178.pdf. cited by other .
Dorigo, M., et al., "Ant Colonies for the Traveling Salesman Problem", BioSystems, pp. 1-10 (1997) retrieved from http://www.idsia.ch/.about.luca/acs-bio97.pdf. cited by other .
Payton, D., et al., "Progress in Pheromone Robotics", The 7th International Conference on Intelligent Autonomous Systems (IAS-7) Marina Del Rey, CA (Mar. 25-27, 2002). cited by other.

Primary Examiner: Padmanabhan; Mano
Assistant Examiner: Patel; Kaushik

Claims

What the invention claimed is:

1. A method of managing a cache of a mobile device carried by a user, the cache being used for storing items associated with locations in a real-world space being visited by the user, the method comprising: (a) determining the probability of usage of an item in dependence on the user's progress around the space using visit history data of one or more previous users that have visited the space and identifying relevant visit history data for use in determining said probability of usage by matching the value of an indicator of said user's progress around the space with values of that indicator in said visit history data; and (b) changing the contents of the cache by adding or removing an item on the basis of the determination carried out in step (a) in respect of that item or other items.

2. A method according to claim 1, wherein in step (a) said probability of usage is determined on the basis of a distance between a location associated with said item and said user's current location in said space.

3. A method according to claim 2, wherein step (a) includes reducing said probability of usage where said item is associated with a location lying in a wake region extending behind the user with respect to the user's progression through the space.

4. A method according to claim 1, wherein in step (a) said probability of usage is determined on the basis of a distance between the location associated with said item and an onward track from said user's current location of a planned route being followed by the user.

5. A method according to claim 1, wherein in step (a) said probability of usage is determined on the basis of a distance between a location associated with said item and an onward track from said user's current location as predicted on the basis of the user's recent movement in said space.

6. A method according to claim 1, wherein said indicator is the user's current location, the item usage probability determined in step (a) being determined by reference to the visit history data of previous users who have been in the same location as the user's current location, this determination using portions of said visit history data relevant to a track taken by previous users from the user's current location in order to determine an onward track for the user, the probability of usage of said item being derived on the basis of a distance between a location associated with the item and said onward track.

7. A method according to claim 1, wherein said indicator is the user's current location, the item usage probability determined in step (a) being determined by reference to the visit history data of previous users who have been in a same location as the user's current location, this determination using portions of said visit history data relevant to item usage onward from the user's current location.

8. A method according to claim 7, wherein step (a) includes reducing said probability of usage where said item is associated with a location lying in a wake region extending behind the user with respect to the user's progression through the space.

9. A method according to claim 1, wherein said indicator is the user's recent movement in said space, the item usage probability determined in step (a) being determined by reference to the visit history data of previous users whose movement to the user's current location corresponds to that of the user's recent movement, this determination using portions of said visit history data relevant to a track taken by previous users from the user's current location in order to determine an onward track for the user, the probability of usage of said item being derived on the basis of a distance between a location associated with the item and said onward track.

10. A method according to claim 1, wherein said indicator is the user's recent movement in said space, the item usage probability determined in step (a) being determined by reference to the visit history data of previous users whose movement to the user's current location corresponds to that of the user's recent movement, this determination using portions of said visit history data relevant to item usage onward from the user's current location.

11. A method according to claim 1, wherein said indicator is an identity of the item whose associated location has been most-recently visited by the user, the item usage probability determined in step (a) being determined by reference to the visit history data of previous users who visited the same item-associated location as the user's most-recently visited item-associated location, this determination using portions of said visit history data relevant to item usage onward from the user's most-recently visited item-associated location.

12. A method according to claim 1, wherein said items are associated with a plurality of virtual features each of which has an associated location in said space, the or each item associated with a one of said plurality of virtual features having as its own associated location the location associated with that feature; said indicator of said user's progress around the space being the feature most recently visited by the user, and the item usage probability determined in step (a) being determined by reference to the visit history data of previous users who visited the same feature as the user's most-recently visited feature, this determination using portions of said visit history data relevant to item usage onward from the user's most-recently visited feature.

13. A method according to claim 1, wherein said indicator of said user's progress around the space is the sequence of at least two items whose item-associated locations have been most recently visited by the user, the item usage probability determined in step (a) being determined by reference to the visit history data of previous users having a same sequence of visited item-associated locations as the sequence of item-associated locations most recently visited by the user, this determination using portions of said visit history data relevant to item usage onward from the user's most-recently visited item-associated location.

14. A method according to claim 1, wherein said items are associated with a plurality of virtual features each of which has an associated location in said space, the or each item associated with a one of said plurality of virtual features having as its own associated location the location associated with that feature; said indicator of said user's progress around the space being a sequence of at least the two features most recently visited by the user, and the item usage probability determined in step (a) being determined by reference to the visit history data of previous users having a same sequence of visited features as the sequence of features most recently visited by the user, this determination using portions of said visit history data relevant to item usage onward from the user's most-recently visited feature.

15. A method according to claim 1, wherein said indicator is an identity of the item most-recently accessed for presentation by the user, the item usage probability determined in step (a) being determined by reference to the visit history data of previous users who accessed for presentation the same item as most-recently accessed for presentation by the user, this determination using portions of said visit history data relevant to item usage onward from the user's most-recently accessed item.

16. A method according to claim 1, wherein said items are associated with a plurality of virtual features each of which has an associated location in said space, the or each item associated with a one of said plurality of virtual features having as its own associated location the location associated with that feature; said indicator of said user's progress around the space being the feature associated with the item most recently accessed for presentation by the user, and the item usage probability determined in step (a) being determined by reference to the visit history data of previous users who accessed for presentation an item associated with the same feature as the item most-recently accessed for presentation by the user, this determination using portions of said visit history data relevant to item usage onward from the feature associated with the item most-recently accessed for presentation by the user.

17. A method according to claim 1, wherein said indicator of said user's progress around the space is a sequence of at least the two items most recently accessed for presentation by the user, the item usage probability determined in step (a) being determined by reference to the visit history data of previous users having a same sequence of items accessed for presentation as the sequence of items most recently accessed for presentation by the user, this determination using portions of said visit history data relevant to item usage onward from the user's most-recently accessed item.

18. A method according to claim 1, wherein said items are associated with a plurality of virtual features each of which has an associated location in said space, the or each item associated with a one of said plurality of virtual features having as its own associated location the location associated with that feature; said indicator of said user's progress around the space being the sequence of at least the two features associated with items most recently accessed for presentation by the user, and the item usage probability determined in step (a) being determined by reference to the visit history data of previous users having a same sequence of features with items accessed for presentation as the sequence of such features for items most recently accessed for presentation by the user, this determination using portions of said visit history data relevant to item usage onward from the user's most-recently visited feature.

19. A method according to claim 1, wherein in step (a) said probability of usage is determined using portions of said visit history data that are relevant to the progression onward of said user, said visit history data being data about one of: the items, or groups of associated items, next visited by said previous users; the items next accessed for presentation, or the groups of items with which those items are associated, by said previous users; the items next delivered, or requested for delivery, to the mobile-device caches of said previous users.

20. A method according to claim 1, wherein in step (b) an item is loaded into the cache, this item being the item in respect of which step (a) is effected, the probability of usage of the item being determined as being above a threshold value for loading items in the cache.

21. A method according to claim 1, wherein in step (b) an item is loaded into the cache, this item being an item not identified in a set of items having probabilities of usage, as determined by step (a); below a threshold value for loading items in the cache.

22. A method according to claim 1, wherein in step (b) an item is removed from the cache, this item being the item in respect of which step (a) is effected, the probability of usage of the item being determined as being below a threshold value for retaining items in the cache.

23. A method according to claim 1, wherein in step (b) an item is removed from the cache, this item being an item not identified in a set of items having probabilities of usage, as determined by step (a), above a threshold value for loading or retaining items in the cache.

24. An arrangement for managing a cache of a mobile device carried by a user, the cache being usable for storing items associated with locations in a real-world space being visited by the user, the arrangement comprising: prediction means for determining the probability of usage of an item in dependence on the user's progress around the space and arranged to determine said probability of usage using visit history data of one or more previous users that have visited the space, the prediction means including identifying means for identifying relevant visit history data for use in determining said probability of usage by matching a value of an indicator of said user's progress around the space with values of that indicator in said visit history data; and a cache manager for changing the contents of the cache by adding or removing an item on the basis of the determination carried out by the prediction means in respect of that item or other items.

25. An arrangement according to claim 24, wherein the prediction means is arranged to determine said probability of usage on the basis of a distance between a location associated with said item and said user's current location in said space.

26. An arrangement according to claim 25, wherein the prediction means includes means for reducing said probability of usage where said item is associated with a location lying in a wake region extending behind the user with respect to said user's progression through the space.

27. An arrangement according to claim 24, wherein the prediction means is arranged to determine said probability of usage on the basis of a distance between a location associated with said item and an onward track from said user's current location of a planned route being followed by the user.

28. An arrangement according to claim 24, wherein the prediction means is arranged to determine said probability of usage on the basis of a distance between a location associated with said item and an onward track from said user's current location as predicted on the basis of the user's recent movement in said space.

29. An arrangement according to claim 24, wherein said indicator is the user's current location, the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users who have been in the same location as the user's current location, and the prediction means further including track-determination means arranged to use portions of said relevant visit history data indicative of a plurality of tracks taken by said previous users from the user's current location in order to determine an onward track for the user, and probability-determining means for determining the probability of usage of said item on the basis of a distance between a location associated with the item and said onward track.

30. An arrangement according to claim 24, wherein said indicator is the user's current location, the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users who have been in the same location as the user's current location, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data that concern item usage onward from the user's current location.

31. An arrangement according to claim 30, wherein the prediction means includes means for reducing said probability of usage where said item is associated with a location lying in a wake region extending behind the user with respect to the user's progression through the space.

32. An arrangement according to claim 24, wherein said indicator is the user's recent movement in said space, the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users whose movement to the user's current location corresponds to that of the user's recent movement, and the prediction means further including track-determination means arranged to use portions of said relevant visit history data indicative of a plurality of tracks taken by previous users from the user's current location in order to determine an onward track for the user, and probability-determining means for determining the probability of usage of said item on the basis of a distance between a location associated with the item and said onward track.

33. An arrangement according to claim 24, wherein said indicator is said user's recent movement in said space, the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users whose movement to the user's current location corresponds to that of the user's recent movement, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data concerning item usage onward from the user's current location.

34. An arrangement according to claim 24, wherein said indicator is an identity of said item whose associated location has been most-recently visited by the user, the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users who visited the same item-associated location as said user's most-recently visited item-associated location, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data concerning item usage onward from said user's most-recently visited item-associated location.

35. An arrangement according to claim 24, wherein said items are associated with a plurality of virtual features each of which has an associated location in said space, the or each item associated with a one of said plurality of virtual features having as its own associated location the location associated with that feature; said indicator of said user's progress around the space being the feature most recently visited by the user, and the identifying means being arranged to identify as said relevant visit history data the visit history data of previous users who visited the same feature as the user's most-recently visited feature, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data concerning item usage onward from the user's most-recently visited feature.

36. An arrangement according to claim 24, wherein said indicator of the current user's progress around the space is a sequence of at least two items whose item-associated locations have been most recently visited by the user, the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users having a same sequence of visited item-associated locations as the sequence of item-associated locations most recently visited by the user, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data relevant to item usage onward from the user's most-recently visited item-associated location.

37. An arrangement according to claim 24, wherein said items are associated with a plurality of virtual features each of which has an associated location in said space, the or each item associated with a one of said plurality of virtual features having as its own associated location the location associated with that feature; said indicator of said user's progress around the space being a sequence of at least the two features most recently visited by the user, and the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users having a same sequence of visited features as the sequence of features most recently visited by the user, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data concerning item usage onward from the user's most-recently visited feature.

38. An arrangement according to claim 24, wherein said indicator is an identity of the item most-recently accessed for presentation by the user, the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users who accessed for presentation on the same item as most-recently accessed for presentation by the user, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data concerning item usage onward from the user's most-recently accessed item.

39. An arrangement according to claim 24, wherein said items are associated with a plurality of virtual features each of which has an associated location in said space, the or each item associated with a one of said plurality of virtual features having as its own associated location the location associated with that feature; said indicator of the current user's progress around the space being the feature associated with the item most recently accessed for presentation by the user, and the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users who accessed for presentation an item associated with the same feature as the item most-recently accessed for presentation by the user, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data concerning item usage onward from the feature associated with the item most-recently accessed for presentation by the user.

40. An arrangement according to claim 24, wherein said indicator of said user's progress around the space is a sequence of at least the two items most recently accessed for presentation by the user, the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users having a same sequence of items accessed for presentation as the sequence of items most recently accessed for presentation by the user, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data concerning item usage onward from the user's most-recently accessed item.

41. An arrangement according to claim 24, wherein said items are associated with a plurality of virtual features each of which has an associated location in said space, the or each item associated with a one of said plurality of virtual features having as its own associated location the location associated with that feature; said indicator of said user's progress around the space being a sequence of at least the two features associated with items most recently accessed for presentation by the user, and the identifying means being arranged to identify as said relevant visit history data the visit history data of said previous users having a same sequence of features with items accessed for presentation as the sequence of such features for items most recently accessed for presentation by the user, the prediction means being arranged to determine said probability of usage on the basis of portions of said relevant visit history data concerning item usage onward from the user's most-recently visited feature.

42. An arrangement according to claim 24, wherein the prediction means is arranged to determine said probability of usage using portions of said visit history data that are relevant to the progression onward of said user, said visit history data being data about one of: the items, or groups of associated items, next visited by said previous users; the items next accessed for presentation, or the groups of items with which those items are associated, by said previous users; the items next delivered, or requested for delivery, to the mobile-device caches of said previous users.

43. An arrangement according to claim 24, wherein the cache manager is arranged to load an item into the cache on the basis of the probability of usage determination carried out by the prediction means, this item being an item in respect of which the prediction means has carried out a probability of usage determination and the determined probability is above a threshold value for loading items in the cache.

44. An arrangement according to claim 24, wherein the cache manager is arranged to load an item into the cache on the basis of the probability of usage determination carried out by the prediction means, this item being an item not identified in a set of items having probabilities of usage, as determined by the prediction means, below a threshold value for loading items into the cache.

45. An arrangement according to claim 24, wherein the cache manager is arranged to remove an item from the cache on the basis of the probability of usage determination carried out by the prediction means, this item being an item in respect of which the prediction means has carried out a probability of usage determination and the determined probability is below a threshold value for retaining items in the cache.

46. An arrangement according to claim 24, wherein the cache manager is arranged to remove an item from the cache on the basis of the probability of usage determination carried out by the prediction means, this item being an item not identified in a set of items having probabilities of usage, as determined by the prediction means, above a threshold value for loading or retaining items in the cache.

Description

FIELD OF THE INVENTION

The present invention relates to methods and arrangements for managing the cache of a mobile device to which media objects are transferred, for example, as the user of the device moves around a space such as an exhibition space.

BACKGROUND OF THE INVENTION

In many uses of mobile computing devices, data (and/or services) stored on networked servers are associated with particular physical locations. The mobile devices are expected to access that data via a network connection when they are at the locations associated with the data. There is a latency associated with accessing data over a network, owing to delays in the network and the server hosting the data.

It is an object of the present invention to minimize this latency.

Once data has been loaded into the memory of a mobile device, it is well known to retain the data beyond its initial use in order to speed subsequent accesses to the same data, such subsequent accesses being a common occurrence. As the device memory is of finite size, data held in the device must occasionally be removed, for example to make space for new data.

It is a further or alternative object of the present invention to provide a way of determining what data to flush from the memory of the mobile device.

SUMMARY OF THE INVENTION

According to one aspect of the present invention, there is provided a method of managing a cache of a mobile device carried by a user, the cache being used for storing items associated with locations in a real-world space being visited by the user; the method comprising the steps of: (a) determining the probability of usage of an item in dependence on the user's progress around the space; (b) changing the contents of the cache by adding or removing an item on the basis of the determination carried out in step (a) in respect of that item or other items.

According to another aspect of the present invention, there is provided an arrangement for managing a cache of a mobile device carried by a user, the cache being usable for storing items associated with locations in a real-world space being visited by the user; the arrangement comprising: prediction means for determining the probability of usage of an item in dependence on the user's progress around the space; and a cache manager for changing the contents of the cache by adding or removing an item on the basis of the determination carried out by the prediction means in respect of that item or other items.

BRIEF DESCRIPTION OF THE DRAWINGS

Embodiments of the invention will now be described, by way of non-limiting example, with reference to the accompanying diagrammatic drawings, in which:

FIG. 1 is a diagram of an exhibition hall having an arrangement for delivering relevant media objects to visitors in a timely manner as the visitors encounter items of interest in the hall;

FIG. 2 is a diagram of a mobile device and service system used in the FIG. 1 arrangement;

FIG. 3 is a diagram of a location report sent from the mobile device to the service system of FIG. 2;

FIG. 4 is a diagram of a response message sent by the service system to the mobile device of FIG. 2;

FIG. 5 is a diagram illustrating some of the choices available when implementing a pheromone trail mechanism such as provided by the mobile device and service system of FIG. 2;

FIG. 6 is a diagram depicting the functional blocks involved in providing a pheromone trail mechanism;

FIG. 7 is a diagram depicting a wake zone behind a user progressing around the FIG. 1 hall;

FIG. 8 is a diagram illustrating the fall-off in allocated item usage probability with distance along and to the side of a movement track;

FIG. 9 is a table showing for each of multiple virtual features located around the FIG. 1 exhibition hall, the likely next feature to be visited from the current feature based on counts of what previous users have done;

FIG. 10 is a flow chart illustrating the operation of a first implementation of an arrangement by which the FIG. 2 mobile device seeks to obtain a desired feature item first from another mobile device before requesting the item from the service system; and

FIG. 11 is a flow chart illustrating the operation of a second implementation of an arrangement by which the FIG. 2 mobile device seeks to obtain a desired feature item first from another mobile device before requesting the item from the service system.

BEST MODE OF CARRYING OUT THE INVENTION

FIG. 1 depicts a real-world environment for which a number of zones have been defined in a virtual world that maps onto the environment. When a person moving in the environment (called a "user" below) is detected as moving into one of these zones, one or more media objects are delivered to the user via a communications infrastructure and a mobile device carried by the user. A zone may correspond to an area around a real-world object of interest with the media object(s) delivered to a user in this area relating to that real-world object. Alternatively, a zone may not correspond to any real-world object.

In considering such an arrangement, it is convenient, though not essential, to introduce the abstraction of a virtual feature which is the subject of each zone. Each such virtual feature is given a number of properties such as a unique identifier, a location in the real-world environment, the real-world extent of the zone associated with the feature, a subject description indicating what the feature concerns, and a set of one or more media-object identifiers identifying the media objects (or "feature items") associated with the feature. The zone associated with a virtual feature is referred to hereinafter as the `active zone` of the feature.

For a feature that is intended to correspond to a particular real-world item (and typically having an active zone that maps to an area about a real-world object), this can be indicated in the subject description of the feature. Using the feature abstraction makes it easier to associate feature items that all relate to the same zone and also facilitates adding/removing these features items since data about the real-world extent of the related zone is kept with the feature and not each feature item.

Each feature is represented by a feature record held in a data-handling system, the feature records together defining the aforesaid virtual world that maps to the real-world environment. Each feature can be thought of as existing in this virtual world with some of these virtual features mapping to real-world objects.

As already noted, when a user is detected as within an active zone of a feature, one or more feature items are delivered to the mobile device of the user for presentation to the user. A feature item can be presented automatically to the user upon delivery or the item can be cached and only presented upon the user having expressed an interest in the feature in some way such as by dwelling in the active zone of the feature more than a minimum time or by explicitly requesting presentation of the feature item. Indeed, the delivery of the feature item to the mobile device can also be deferred until the user is detected as having expressed an interest in the feature; however, since this approach can introduce a delay before the item is available for presentation, the embodiments described below deliver feature items to the mobile device of the user without awaiting a specific expression of interest in each feature (though, of course, a general filtering may be applied as to what items are delivered according what types of features are of interest to the user). Preferably, each feature or feature item is given a property indicating whether feature item delivery is to be effected automatically upon delivery or only after a user has expressed an interest in the feature; this enables important items (such as warning messages concerning features associated with potentially hazardous real-world items) to be pushed to the user whilst other items are subject to an expression of interest by the user. Advantageously, a user may elect to have feature items automatically presented even when the corresponding feature/item property does not require this. Furthermore, since as will be described hereinafter, pre-emptive caching of feature items in the user's mobile device may be implemented, automatic presentation is qualified so as only to apply where the user is in the active zone of the feature with which the feature item is associated.

Considering the FIG. 1 example in more detail, the environment depicted is an exhibition hall 10 having rooms 11 to 17 where: room 11 is an entrance foyer with reception desk 18 but no associated virtual features; room 12 is a reference library with no associated virtual features; rooms 13, 14 and 15 are used for displaying real-world objects, namely paintings 20 and sculptures 21, for each of which there is a corresponding virtual feature centred on the object concerned and with an associated active zone 25 (indicated by a dashed line); room 16 is used for experiencing virtual features for which there are no corresponding real-world objects, the location associated with each feature being indicated by a cross 22 and the corresponding active zone 25 by a dashed line; and room 17 is a cafeteria with no associated virtual features.

Virtual features are also defined in correspondence to the majority of openings 23 between rooms, the active zones 25 associated with the features again been indicated by dashed lines. Typically, the feature items associated with these features are incidental information concerning the room about to be entered and are automatically presented. It will be seen from FIG. 1 that only a single feature is applied to an opening 23 so that it is not possible to tell simply from the fact that a user is detected in the active zone of the feature which room the user is about to enter; however, as will be later described, it is possible to determine from the user's past activity (either location based or feature based) the general direction of progression of the user and therefore which room is about to be entered. This enables the appropriate feature item to be selected for delivery to the user from amongst the items associated with the feature.

On entering the exhibition hall 10, a user 30 collects a mobile device 31 from the reception desk 18 (or the user may have their own device). This device 31 cooperates with location-related infrastructure to permit the location of the user in the hall 10 to be determined. A number of techniques exist for enabling the location of the user to be determined with reasonable accuracy and any such technique can be used; in the present example, the technique used is based on an array of ultrasonic emitters 33 (represented in FIG. 1 by black triangles) positioned at known locations in each room (typically suspended above human level). The emitters 33 are controlled by controller 32 to send out emitter-specific emissions at timing reference points that are indicated to the mobile device 31 by a corresponding radio signal sent by the controller 32. The device 31 is capable of receiving both the timing reference signals and the emissions from the ultrasonic transmitters 33. The device 31 is also pre-programmed with the locations of these emitters and is therefore able to calculate its current location on the basis of the time of receipt of the emissions from the different emitters relative to the timing reference points.

The exhibition hall is equipped with a wireless LAN infrastructure 36 comprising a distribution system and access points 37. The wireless LAN has a coverage encompassing substantially all of the hall 10, the boundary of the coverage being indicated by chain-dashed line 38 in FIG. 1. The wireless LAN enables the mobile device to communicate with a service system 35 to download feature items appropriate to the feature (if any) corresponding to the current location of the user. In the present example, the determination of when the location of the user (as determined by the device in the manner already described) places the user within the active zone of a virtual feature, is effected by the service system; however, it is also possible to have the device 31 carry out this determination provided it is supplied with the appropriate information about the feature zones.

It will be appreciated that communication between the device 31 and service system 35 can be effected by any suitable means and is not limited to being a wireless LAN.

FIG. 2 shows the mobile device 31 and service system 35 in more detail. More particularly, the mobile device 31 comprises the following functional blocks: A location determination subsystem 40 with an associated timing reference receiver 41 and ultrasonic receiver 42 for receiving the timing reference signals from the location infrastructure 32 and the emissions from the ultrasonic emitters 33 respectively; the location determination subsystem 40 is operative to use the outputs of the receivers 41 and 42 to determine the location of the mobile device (as already described above) and to send location reports to the service system 35. A visit data memory 43 for holding data about the current "visit"--that is, the current tour of the hall 10 being undertaken by the user of the mobile device 31. A feature-item cache 44 for caching feature items delivered to the mobile device 31 from the service system 35. The cache 44 has an associated cache manager 45. A communications interface 46 for enabling communication between the mobile device 31 and the service system 35 via the wireless LAN infrastructure 36. A user interface 48 which may be visual and/or sound based; in one preferred embodiment the output to the user is via stereo headphones 60. A visit manager 47 typically in the form of a software application for providing control and coordination of the other functions of the mobile device 31 in accordance with input from the user and the service system 35. A visit path guide 49 for giving the user instructions/indicators for following a planned route around the hall 10. Much of the foregoing functionality will typically be provided by a program-controlled general purpose processor though other implementations are, of course, possible.

The visit data held by memory 44 will typically include a user/device profile data (for example, indicating the subjects of interest to the user, the intended visit duration, and the media types that can be handled by the device), an electronic map of the hall 10, the user's current location as determined by the subsystem 40, and the identity of the feature (if any) currently being visited together with the IDs of its related feature items. The visit data also includes a feature history for the visit, which is either: the history of visited features and their related feature item IDs in the order the features were visited (thus, a feature is added to the top of the visited-feature history list when the feature is encountered), or the history of accessed features and their related feature item IDs in the order the features were visited (thus, a feature is added to the top of the accessed-feature history list when one of its feature items is accessed by--that is, presented to--the user whilst the feature is the currently visited feature). If a visited-feature history list is kept, a history of accessed features can be embedded in it by providing each feature in the history with an associated flag to indicate whether or not the feature was accessed whilst current. Although keeping a visited-feature history provides more information about the visit, it will inevitably use more memory resources than an accessed-feature history and in many cases it will only be desired to track features which the user has found sufficiently of interest to access an associated feature item. Where the purpose of the feature history is simply to keep a list of features (and related feature items) that were of interest to the user, it may be desirable to exclude from the list features for which items were automatically presented but are not associated with exhibits (real or virtual)--that is, exclude features concerned with incidental information about the hall.

The feature history preferably covers the whole of the visit though it may alternatively only cover the most recently visited/accessed features. In either case, the most recent several entries in the history list form what is hereinafter referred to as the "feature tail" of the user and provides useful information about the path being taken by the user.

The visit data held in memory 43 may further include details of a planned route being followed by the user, and a history of the locations visited by the user (this may be a full history or just the locations most recently visited--hereinafter termed the "location tail" of the user).

The service system 35 comprises the following main functional elements: A communications interface 50 for communicating with the mobile device 50 via the wireless LAN infrastructure 36. An internal LAN 51 (or other interconnect arrangement) for interconnecting the functional elements of the service system. A data store 52 for storing feature data and, in particular, a feature record for each feature with each record comprising the feature identifier, the subject of the feature, the corresponding real-world location and extent of the feature's active zone, the IDs and media type of the or each associated feature item, and a flag which when set indicates that feature item presentation of an associated feature item is to be effected automatically upon delivery when the feature is being visited. A feature-item server 53 for serving an identified feature item to the mobile device 31 in response to a request from the latter. A location report manager 54 for receiving location reports from the location determination subsystem 40 of the mobile device and for passing on data from the reports to functional elements 55 and 56 (see below). A pheromone trial subsystem 55 for receiving location data, via manager 54, from all user mobile devices to build up trail data in a manner akin to the use of pheromones by ants. An item-data response subsystem 56 for receiving location and other data from the manager 54 in order to prepare and send a response back to the mobile device 31 that provided the location data, about what feature items it needs, or is likely to need, both now, in view of a feature currently being visited, and (where, as in the present embodiment, pre-emptive caching is implemented) in the near future. Subsystem 56 comprises a location-to-feature item translation unit 57 which can either be implemented independently of the data held in store 52 or, preferably, be arranged to operate by querying the store 52, the latter having associated functionality for responding to such queries. Subsystem 56 further comprises a prediction unit 58 for predicting, in any of a variety of ways to be described hereinafter, what feature items are most likely to be needed in the near future. A route planner 59 for responding to requests from the mobile device 31 for a route to follow to meet certain constraints supplied by the user (such as topics of interest, time available, person or tour to follow, an exhibit or facility to be visited, etc). In providing a planned route, the route planner will typically access data from one or both of the feature data store 52 and the pheromone trail subsystem 55. The route planner 59 can conveniently hold a master map of the hall 10 for use by itself and the other elements of the service system 35, and for download to each mobile device 31 at the start of each new visit and/or whenever the master map is changed.

The functional elements of the service system 35 can be configured as a set of servers all connected to the LAN 51 or be arranged in any other suitable manner as will be apparent to persons skilled.

The mobile device 31 and service system 35 provide a number of useful capabilities that will each be described in detail below after an overview of the general operation of the mobile device and service system during a visit. It is to be understood that the split of functionality between the mobile device 31 and service subsystem 35 can be varied substantially form that indicated for the FIG. 2 embodiment; indeed all functionality can be provided either entirely by the mobile device 31 (with all feature items being stored in the device) or by the service system 35 (with the presentation of feature items to a user being by means of fixed input/output devices located around the hall near the locations associated with the virtual features).

In general terms, a user starting a visit can request a route to follow using the user interface 48 of the mobile device 31 to indicate parameters to be satisfied by the route. This route request is sent by the visit manager to route planner 50 and results in the download to the mobile device 31 of a planned route. The path guide 49 then provides the user (typically, though not necessarily, only when asked) with guide indications to assist the user in following the planned route. Where the interface 48 includes a visual display, this can conveniently be done by displaying a map showing the user's current location and the planned route; in contrast, where only an audio interface is available, this can be done by audio cues to indicate the direction to follow. A user need not request a planned route and in this case will receive no guide indications. A user may request a route plan at any stage of a visit (for example a route to an exhibit of interest).

As the user moves through the hall, the location determination subsystem 40 sends periodic location reports 62 (see FIG. 3) to the location report manager 54 of the service system 35 via the wireless LAN 36. In addition to the user's current location, these reports typically include a user identifier (and possibly, additionally or alternatively, a type identifier indicative of any variable of interest such as, for example, the group of users to which the device user belongs or an activity being undertaken by the user), user/device profile data, and prediction-assist data for use by the prediction unit 58 in predicting what feature items are likely to be needed shortly. This prediction-assist data can comprise one or more of the following: route data concerning any planned route being followed; the user's "location tail"; and the most recent feature (either the "most-recently visited" or "most-recently accessed") associated with the user, either provided alone or as part of the user's "feature tail".

When a location report 62 is received by the manager 54, it passes on the user's current location in the report to the pheromone trail subsystem 55 to enable the latter to build up trail data from all devices; additionally, the user and/or type identifier may be passed on to subsystem 55 if provided in the location report. The user's current location is also passed to the item-data response subsystem 56 together with any profile data and prediction-assist data in the location report 62. The item-data response subsystem 56 then constructs and sends a response 65 (see FIG. 4) to the mobile device 31 that originated the location report.

More particularly, the location-item to feature translation unit 57 of subsystem 56 uses the data passed to subsystem to determine the feature, if any, currently being visited by the user and thus what feature items are relevant to the user in their current location. In doing this, the unit 57 may also use the supplied profile data to disregard both features that do not relate to a subject of interest to the user and feature items of a media type that cannot be handled by the mobile device 31. The unit 57 may also use elements of the prediction-assist data (for example, the location or feature last encountered before the current one) to enable it to determine the direction of progression of the user and thus to select between feature items of a feature in dependence on the direction of approach of the user. This is done, for example, for the features associated with openings 25 in order to select a feature item appropriate to entering a room. The IDs of feature items identified by the unit 57 together with the identity of the corresponding feature and the status of the automatic presentation flag of the feature, form a first part 66 of the response 65 to be sent back to the mobile device 31. Where the current location does not correspond to the active zone of any feature, the first response part 66 simply indicates this.

A second part 67 of the item-data response 65 is produced by the prediction unit 58 and comprises a list of the feature items most likely to be needed in the near future by the mobile device 31; for each such feature item, the second response part 67 includes the feature ID, its type, size and probability of usage (discussed in detail hereinafter). Like the unit 57, the unit 58 uses supplied profile data to disregard feature items of features not of interest to the user or of a media type that cannot not be handled by the mobile device 31. The number of feature items identified in response part 67 is preferably limited (for example, to ten such items). The item-data response subsystem 56 then sends the response 65 back to the mobile device 31 of the user by using a return address supplied with the original location report 62 and passed to subsystem 56 by the manager 54.

Rather than having the prediction unit 58 provide a prediction each and every time the mobile device 31 sends a location report, it is possible to arrange for the prediction unit 58 only to operate when required by the mobile device 31 with the latter only requiring a prediction, for example, every nth location report or only after the user has moved a certain distance since the last prediction made by unit 58. Conveniently, the location report field used to carry the prediction-assist data is also used to indicate when a prediction is required by, for example, setting the field to a predetermined value when prediction is not required.

The item-data response received back at the mobile device 31 is processed by the visit manager 47. If the first part 66 of the response identifies a feature (thereby indicating that the current location of the user corresponds to the active zone of feature), the manager 47 updates the `current feature` data in memory 45 to the feature identifier and item IDs in the first response part. These item IDs are also passed to the cache manager 45 and are used by the latter to request immediate delivery of these items from the server 53 of the service system to cache 44, if not already present in the cache. If the feature history data held by memory 43 relates to visited, rather than accessed, features, and if the feature identifier and item IDs in the first response part 66 differ from the most recent entry in the feature history list, the latter is updated with the feature identifier and item IDs from the first response part 66.

In the case that no feature is identified in the first part of the response 65, the `current feature` data in memory 43 is set to null.

The manager 47 also determines whether the (first) feature item (if any) identified in the first response part 66 is to be immediately presented to the user, this determination taking account of the setting of the automatic presentation flag in the first part of the response, any user indication (stored, for example in the profile data) that all items are to be automatically presented, and any monitored indications of the user's interest in the currently-visited feature. Where a feature item identified in the first response part is to be immediately presented to the user, the manager 47 requests the item from the cache manager 45 (there may be a delay in the delivery of the item if it has not yet been received from the server 53). At the same time, if the feature history concerns accessed features the manager 47 updates the feature history with an entry corresponding to the feature identifier and item IDs forming the `current feature` data; where the feature history although recording all visited features, provides for indicating whether a feature has been accessed, the manager updates the feature history accordingly.

With respect to the data contained in the second part 67 of the response 65, the visit manager simply passes this data to the cache manager 45 which determines whether or not to request from server 53 any of the items identified that are not already in the cache 44. The cache manger 47 in making this determination takes account of the probability that an item will be needed in the near future and the available cache space. The cache manager 45 may decide to create additional cache space by flushing one or more items from the cache and/or by reducing the space they occupy, as will be more fully described hereinafter.

In this manner, the cache manager 45 seeks to ensure