System and method for using skyline queries to search for points of interest along a route

• US 8,990,010 B2
• Filed: 12/21/2011
• Issued: 03/24/2015
• 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
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): GOLDMAN, RICHARD A
• Application Number:
  US13/332,602
• Publication Number:
  US 20130166586A1
• Time in Patent Office: 1,189 Days
• Field of Search: None
• US Class Current: 701/426
• 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 an initial link associated with an origin of the route path and one or more subsequent links that connect the origin of the route path with a destination of the route path;

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 subsequent links of the route path using a relation configured to store at least a link identifier for a subsequent link, a point of interest identifier for a point of interest, a distance between the subsequent 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 associated with one or more subsequent links of the route path, 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 in the plurality of 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 offered at the plurality of points of interest.

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 to the point of interest.

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

9. 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.

10. The computer-implemented method of claim 1, wherein the relation is stored before the route path is determined and before the skyline query is received.

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 a link identifier for a link related to the current position, a point of interest identifier for 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, wherein the relation is stored before the current position is determined;

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, wherein the indication comprises a map depicting at least one skyline point 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 11, wherein the link related to the current position further comprises one or more links that share a common endpoint with a 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 link identifier for the link related to the current position comprises:

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

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 in the plurality of points of interest.

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

18. 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.

19. 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;

limiting the plurality of points of interest based on a distance to a route path, the distance is selected as a function of a classification of at least a portion of the route path;

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.

20. The navigation system of claim 19, wherein the classification includes data indicative of a controlled access road, an arterial road, or a local road.