FAST LOCAL RECOMMENDER QUERIES VIA MODIFIED SPATIAL DATA STRUCTURE QUERYING

• US 20090077058A1
• Filed: 09/18/2007
• Published: 03/19/2009
• Est. Priority Date: 09/18/2007
• Status: Active Grant

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Roberts, Michael
• Granted Patent: US 7,743,081 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/53 using third party service providers
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/18 Information format or content conversion, e.g. adaptation by the network of the transmitted or received information for the purpose of wireless delivery to users or terminals

Abstract

One embodiment of the present invention provides a system that can recommend leisure activities to a user. During operation, the system receives one or more activity types. Next it receives a bound in terms of a nearness metric such as travel distance, travel time, or travel cost. Next, it receives location information associated with a computing device of the user. The system then uses the location information to identify a cell stored in a spatial database. The system then returns a set of leisure activities that match the activity types and that are within the bound relative to the cell. The spatial database includes leisure activity data that is segmented based on physical position such as latitude and longitude. Moreover, the cells of the spatial database are linked based on the nearness metric.

Claims

1. A method for providing recommendations of leisure activities to a user, comprising:

receiving one or more activity types;

receiving a bound in terms of a nearness metric;

receiving location information associated with a computing device of the user;

using the location information to identify a cell stored in a spatial database where leisure activity data is segmented based on physical position and where cells are linked based on the nearness metric;

retrieving from the spatial database a set of leisure activities that matches the activity types and that are within the bound relative to the cell; and

returning the set of leisure activities.

2. The method of claim 1, wherein the nearness metric is based on one or more of:

travel distance, travel time, and travel cost.

3. The method of claim 1, wherein receiving location information involves receiving a set of coordinates associated with the computing device of the user.

4. The method of claim 1, wherein using the location information to identify a cell stored in the spatial database further comprises:

computing the difference in latitude from the location of the computing device to an origin specified in the spatial database;

computing the difference in longitude from the location of the computing device to the origin specified in the spatial database;

dividing the change in latitude by horizontal cell size to yield the horizontal index of the cell;

dividing the change in longitude by vertical cell size to yield the vertical index of the cell; and

returning the horizontal and vertical indices of the cell.

5. The method of claim 1, wherein the number of cells in the spatial database depends on the density of leisure activities in a given geographic area and the type of leisure activity.

6. The method of claim 1, wherein retrieving the set of leisure activities from the spatial database that are near the cell in the spatial database, further comprises:

locating a set of cells in the spatial database that are within a fixed neighborhood of the cell based on the cell links; and

returning the set of leisure activities associated with each of the cells in said set of cells.

7. The method of claim 1, wherein retrieving the set of leisure activities from the spatial database that are near the cell in the spatial database involves transitively searching through the linked cells according to the nearness metric.

9. The computer-readable storage medium of claim 1, wherein the nearness metric is based on one or more of:

travel distance, travel time, and travel cost.

10. The computer-readable storage medium of claim 1, wherein receiving location information involves receiving a set of coordinates associated with the computing device of the user.

11. The computer-readable storage medium of claim 1, wherein using the location information to identify a cell stored in the spatial database further comprises:

computing the difference in latitude from the location of the computing device to an origin specified in the spatial database;

computing the difference in longitude from the location of the computing device to the origin specified in the spatial database;

dividing the change in latitude by horizontal cell size to yield the horizontal index of the cell;

dividing the change in longitude by vertical cell size to yield the vertical index of the cell; and

returning the horizontal and vertical indices of the cell.

12. The computer-readable storage medium of claim 1, wherein the number of cells in the spatial database depends on the density of leisure activities in a given geographic area and the type of leisure activity.

13. The computer-readable storage medium of claim 1, wherein retrieving the set of leisure activities from the spatial database that are near the cell in the spatial database, further comprises:

locating a set of cells in the spatial database that are within a fixed neighborhood of the cell based on the cell links; and

returning the set of leisure activities associated with each of the cells in said set of cells.

14. The computer-readable storage medium of claim 1, wherein retrieving the set of leisure activities from the spatial database that are near the cell in the spatial database involves transitively searching through the linked cells according to the nearness metric.

8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for providing recommendations of leisure activities to a user, the method comprising:

receiving one or more activity types;

receiving a bound in terms of a nearness metric;

receiving location information associated with a computing device of the user;

using the location information to identify a cell stored in a spatial database where leisure activity data is segmented based on physical position and where cells are linked based on the nearness metric;

retrieving from the spatial database a set of leisure activities that matches the activity types and that are within the bound relative to the cell; and

returning the set of leisure activities.

15. An apparatus for providing recommendations of leisure activities to a user, comprising:

a receiving mechanism configured to receive one or more activity types;

a receiving mechanism configured to receive a bound in terms of a nearness metric;

a receiving mechanism configured to receive location information associated with a computing device of the user;

an identification mechanism that uses the location information to identify a cell stored in a spatial database where leisure activity data is segmented based on physical position and where cells are linked based on the nearness metric;

a retrieval mechanism configured to retrieve from the spatial database a set of leisure activities that matches the activity types and that are within the bound relative to the cell; and

returning the set of leisure activities.

16. The apparatus of claim 15, wherein the nearness metric is based on one or more of:

travel distance, travel time, and travel cost.

17. The apparatus of claim 15, wherein receiving location information involves receiving a set of coordinates associated with the computing device of the user.

18. The apparatus of claim 15, wherein using the location information to identify a cell stored in the spatial database further comprises:

computing the difference in latitude from the location of the computing device to an origin specified in the spatial database;

computing the difference in longitude from the location of the computing device to the origin specified in the spatial database;

dividing the change in latitude by horizontal cell size to yield the horizontal index of the cell;

dividing the change in longitude by vertical cell size to yield the vertical index of the cell; and

returning the horizontal and vertical indices of the cell.

19. The apparatus of claim 15, wherein the number of cells in the spatial database depends on the density of leisure activities in a given geographic area and the type of leisure activity.

20. The apparatus of claim 15, wherein retrieving the set of leisure activities from the spatial database that are near the cell in the spatial database, farther comprises:

locating a set of cells in the spatial database that are within a fixed neighborhood of the cell based on the cell links; and

returning the set of leisure activities associated with each of the cells in said set of cells.