Indexing routes using similarity hashing

• US 9,689,690 B2
• Filed: 07/13/2015
• Issued: 06/27/2017
• Est. Priority Date: 07/13/2015
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Rolf, Daniel
• Primary Examiner(s): Badii, Behrang
• Application Number:
  US14/797,794
• Publication Number:
  US 20170016733A1
• Time in Patent Office: 715 Days
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G01C 21/3611 using character input or menus, e.g. menus of POIs character input methods in general G06F3/0233
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 3/041 Digitisers, e.g. for touch screens or touch pads, characterised by the transducing means
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A method and apparatus for indexing routes using similarity hashing. In an embodiment, a processor identifies a route wherein the route includes one or more links. The processor identifies a route attribute wherein the route attribute describes the route. The processor hashes the one or more links to determine a minimum link with a minimum hash value. The processor assigns the route attribute to the minimum link.

Claims

1. A method comprising:

identifying a route, wherein the route includes one or more links;

identifying a route attribute, wherein the route attribute describes the route;

generating a hash value for each of the one or more links;

identifying a minimum link of the one or more links with a minimum hash value;

assigning the route attribute to the minimum link in an index containing a plurality of links for a roadway network;

wherein the index is configured to provide a requested route that is described as the route attribute to a navigation device.

2. The method of claim 1, further comprising:

receiving a second route, wherein the second route includes one or more second links;

generating hash values for each of the one or more second links;

identifying a minimum second link which corresponds to a minimum second link hash value for the second route; and

assigning the route attribute to the second route when the minimum second link is the minimum link.

3. The method of claim 1, wherein the route attribute is a popularity of the route.

4. The method of claim 1, wherein the route attribute is a scenic value of the route.

5. The method of claim 1, wherein the route attribute is received from a user profile.

6. The method of claim 1, wherein the route attribute is received from a social media application.

7. The method of claim 1,

wherein the index aggregates how often the route attribute is assigned to the minimum link as a route attribute value.

8. The method of claim 7, further comprising:

receiving a route attribute request regarding a third route;

wherein the third route includes one or more third links;

generating hash values for each of the third links;

identifying a minimum third link hash value;

matching the minimum third link hash value to a minimum third link; and

transmitting the route attribute value that corresponds to the minimum third link in the index.

9. The method of claim 7, further comprising:

generating more than one indices by using more than one different hash functions to generate more than one minimum link hash value.

10. The method of claim 9, further comprising:

averaging a route attribute value from the more than one indices.

11. The method of claim 7, further comprising:

receiving a request including a route attribute, a starting point, and a destination;

generating one or more candidate route;

wherein the one or more candidate routes include the starting point and the destination;

wherein the candidate routes include one or more candidate links;

generating a hash value for each of the one or more candidate links;

identifying a minimum candidate link with a minimum hash value for each candidate route; and

transmitting a chosen candidate route that is the candidate route which has the minimum candidate link with a highest route attribute value found in the index.

12. The method of claim 11, wherein the chosen candidate route is the candidate route which has the minimum candidate link with the second highest route attribute value found in the index.

13. The method of claim 11, wherein each candidate route of the one or more candidate routes differ by one candidate link.

14. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs;

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform;

identify a route including one or more links;

identify a route attribute that describes the route;

generate a hash value for each of the one or more links;

identify a minimum link with a minimum hash value; and

assign the route attribute to the minimum link in an index containing a plurality of links for a roadway network;

wherein the index is configured to provide a requested route that is described as the route attribute to a navigation device.

15. The apparatus of claim 14, wherein

the index aggregates how often the route attribute was assigned to the minimum link as the route attribute value.

16. The apparatus of claim 14, wherein the route attribute is a popularity of the route.

17. The apparatus of claim 15, wherein the at least one memory and computer program code are configured to cause the apparatus to further perform:

generate more than one indices by using more than one hash function to generate more than one minimum link hash value for each of the one or more links.

18. The apparatus of claim 17, wherein the at least one memory and computer program code are configured to cause the apparatus to further perform:

average a route attribute value from the more than one indices.

19. A non-transitory computer readable medium including instructions that when executed are operable to:

receive a traveled route, wherein the traveled route includes one or more links;

receive a route attribute from a navigation device that traveled the traveled route, wherein the route attribute describes the traveled route;

generate a hash value for each of the one or more links;

identify a minimum link with a minimum hash value; and

assign the route attribute to the minimum link in an index containing a plurality of links for a roadway network;

wherein the index is configured to provide a requested route that is described as the route attribute to a navigation device.

20. The non-transitory computer readable medium of claim 19, wherein the route attribute is a popularity of the traveled route.