Indexing routes using similarity hashing

Patent metadata

Field	Value
Publication number	US-9689690-B2
Application number	US-201514797794-A
Country	US
Kind code	B2
Filing date	Jul 13, 2015
Priority date	Jul 13, 2015
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

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.

First claim

I claim:

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.

Assignees

• Here Global Bv

Inventors

• Rolf Daniel

Classifications

• G01C21/00

  Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 (measuring distance traversed on the ground by a vehicle G01C22/00; control of position, course, altitude or attitude of vehicles G05D1/00; traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968) · CPC title

• G06F17/30702

  Physics · mapped topic

• G06F17/30241

  Physics · mapped topic

• G01C21/3469

  Fuel consumption; Energy use; Emission aspects · CPC title

• G01C21/3484

  Personalized, e.g. from learned user behaviour or user-defined profiles · CPC title