SYSTEM AND METHOD FOR USING SKYLINE QUERIES TO SEARCH FOR POINTS OF INTEREST ALONG A ROUTE

• US 20130166586A1
• Filed: 12/21/2011
• Published: 06/27/2013
• Est. Priority Date: 12/21/2011
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Pfeifle, Martin, Suh, Jonghyun, Gumhold, Boris
• Granted Patent: US 8,990,010 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/024 Guidance services

Abstract

A method and system for searching for points of interest along a route is disclosed. A relation that includes records that associate link identifiers, point of interest identifiers, and distances between the links and the points of interest is generated during the compilation process of a first version of a geographic database. The relation is stored in compiled database products. When a compiled database product is being used by a navigation system, for example, navigation application software programs use the relation to accurately and efficiently find points of interest along a computed route. Navigation systems can also use the relation to service skyline queries and responsively generate skyline graphs of points of interest.

Claims

1. A computer-implemented method for determining skyline points of interest, comprising:

determining a route path at a navigation system, wherein the route path comprises one or more links;

receiving a request for a skyline query at the navigation system, wherein the skyline query is related to one or more point-of-interest attributes;

in response to the request, the navigation system;

determining a plurality of points of interest associated with the one or more links of the route path using a relation configured to store at least an identifier associated with a link, an identifier associated with a point of interest, a distance between the link and the point of interest, and a value for each attribute of the one or more point-of-interest attributes;

selecting one or more skyline points of interest from the plurality of points of interest, wherein a skyline point of interest is not dominated by other points of interest in the plurality of points of interest with respect to the one or more point- of-interest attributes; and

producing an indication of the one or more skyline points of interest.

2. The computer-implemented method of claim 1, wherein selecting the one or more skyline points of interest comprises performing a database query configured to determine whether a point of interest in the plurality of points of interest is not dominated by other points of interest.

3. The computer-implemented method of claim 1, wherein selecting the one or more skyline points of interest comprises selecting the one or more skyline points of interest using a skyline-query algorithm.

4. The computer-implemented method of claim 1, wherein the one or more point-of- interest attributes comprise a distance from the current position.

5. The computer-implemented method of claim 1, wherein the one or more point-of- interest attributes comprise a price.

6. The computer-implemented method of claim 1, wherein the one or more point-of- interest attributes comprise a point of interest category.

7. The computer-implemented method of claim 1, wherein the one or more point-of- interest attributes comprise a distance from the route path.

8. The computer-implemented method of claim 1, wherein the indication comprises a map depicting at least one skyline point of interest.

9. The computer-implemented method of claim 1, wherein the indication comprises a list that includes at least one indicated skyline point of interest.

10. The computer-implemented method of claim 1, wherein the indication comprises a list that includes at least one skyline point of interest and at least one point-of-interest attribute for the at least one skyline point of interest.

11. A computer-implemented method determining skyline points of interest, comprising:

determining a current position at a navigation system;

receiving a request for a skyline query at the navigation system, wherein the skyline query is related to one or more point-of-interest attributes;

in response to the request, the navigation system;

determining a plurality of points of interest associated with the current position using a relation configured to store at least an identifier associated with a link related to the current position, an identifier associated with a point of interest, a distance between the link related to the current position and the point of interest, and a value for each attribute of the one or more point-of-interest attributes;

selecting one or more skyline points of interest from the plurality of points of interest, wherein each skyline point of interest is not dominated by other points of interest in the plurality of points of interest with respect to the one or more point-of-interest attributes; and

producing an indication of the one or more skyline points of interest.

12. The computer-implemented method of claim 11, wherein the link related to the current position comprises a link closest to the current position.

13. The computer-implemented method of claim 12, wherein the link related to the current position further comprises one or more links that share a common endpoint with to the link closest to the current position.

14. The computer-implemented method of claim 11, wherein the link related to the current position comprises one or more links within a search radius of the current position.

15. The computer-implemented method of claim 11, wherein determining the plurality of points of interest associated with the current position using the relation configured to store at least the identifier associated with the link related to the current position comprises:

determining a historical list of links associated with the current position;

determining a direction of travel based on the historical list of links;

determining at least one next-traveled link based on the direction of travel; and

determining that the link related the current position comprises the at least one next-traveled link.

16. The computer-implemented method of claim 11, wherein selecting the one or more skyline points of interest comprises performing a database query configured to determine whether a point of interest in the plurality of points of interest is not dominated by other points of interest.

17. The computer-implemented method of claim 11, wherein the indication comprises a map depicting at least one skyline point of interest.

18. The computer-implemented method of claim 11, wherein the display comprises a list that includes at least one indicated skyline point of interest.

19. The computer-implemented method of claim 11, wherein the indication comprises a list that includes at least one skyline point of interest and at least one point-of-interest attribute for the at least one skyline point of interest.

20. A navigation system, comprising:

a processor,

a geographic database that includes a relation that associates link identifiers, point of interest identifiers, distances between links and points of interest, and point of interest attribute values; and

data storage containing instructions executable by the processor for carrying out skyline queries, including;

identifying a plurality of points of interest relevant to a search request using the relation;

selecting one or more skyline points of interest within the plurality of points of interest, wherein the skyline points of interest are not dominated by the other points of interest; and

providing the selected skyline points of interest.