Indexing Routes Using Similarity Hashing

• US 20170016733A1
• Filed: 07/13/2015
• Published: 01/19/2017
• Est. Priority Date: 07/13/2015
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Rolf, Daniel
• Granted Patent: US 9,689,690 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

hashing the one or more links to determine a minimum link with a minimum hash value; and

assigning the route attribute to the minimum link.

2. The method of claim 1, further comprising:

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

hashing the one or more second links to generate hash values for the one or more second links;

determining 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, further comprising:

generating an index of one or more minimum links, 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;

hashing the third links to determine 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 hash function 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;

creating 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;

hashing the one or more candidate links to determine 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;

hash the one or more links to determine a minimum link with a minimum hash value; and

assign the route attribute to the minimum link.

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

generate an index of one or more minimum links, 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 index by using more than one hash function to generate more than one minimum link hash value.

18. The apparatus of claim 16, 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 index.

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

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

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

hash the one or more links to determine a minimum link with a minimum hash value; and

assign the route attribute to the minimum link.

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