Encoding routes to POIs in proximity searches using bloom filters

Patent metadata

Field	Value
Publication number	US-11566911-B2
Application number	US-201916419579-A
Country	US
Kind code	B2
Filing date	May 22, 2019
Priority date	May 22, 2019
Publication date	Jan 31, 2023
Grant date	Jan 31, 2023

Abstract

A POI request comprising query criteria and information identifying a starting location is received. A network version starting segment is identified based on the information identifying the starting location. A route determination algorithm is expanded, starting at the starting segment. When the route determination algorithm is expanded to a new segment, it is determined whether any POIs associated with the new segment match the query criteria. Responsive to determining that a POI associated with the new segment satisfies the query criteria, a POI route from the starting segment to the POI is extracted. Map version agnostic identifiers are generated for each segment of the POI routes. Each of the map version agnostic identifiers are coded using at least one coding function. A bloom filter having the coded map version agnostic identifiers as members is generated. The bloom filter is provided such that a mobile apparatus receives the bloom filter.

First claim

That which is claimed:

1. A method comprising:
receiving a point of interest (POI) request comprising query criteria and information identifying a starting location, the POI request received by a network apparatus comprising a processor, communication interface, and memory storing a network version of a digital map;
identifying, by the network apparatus, a network version starting segment based on the information identifying the starting location and the network version of the digital map;
expanding, by the network apparatus, a route determination algorithm starting at the starting segment, wherein when the route determination algorithm is expanded to a new segment, it is determined whether any POIs associated with the new segment satisfy the query criteria;
responsive to determining that a POI associated with the new segment satisfies the query criteria, extracting, by the network apparatus, a POI route from the starting segment to the POI from a state of the route determination algorithm, wherein the POI route identifies segments providing a route between the network version starting segment and the POI;
responsive to identifying a particular number of POIs that satisfy the query criteria, generating, by the network apparatus, a plurality of map version agnostic identifiers based on the segments of a plurality of POI routes and the network version of the digital map, each of the plurality of map version agnostic identifiers identifying a respective segment of at least one POI route of the plurality of POI routes, the plurality of POI routes including a respective POI route extracted for each POI of the particular number of POIs;
coding, by the network apparatus, each of the plurality of map version agnostic identifiers using at least one coding function;
generating, by the network apparatus, a bloom filter having the plurality of coded map version agnostic identifiers as members, such that the bloom filter encodes the plurality of POI routes by encoding each segment from the starting segment to a respective POI of each of the plurality of POI routes; and
providing, by the network apparatus, a data structure storing the bloom filter such that a mobile apparatus receives the data structure.

2. The method of claim 1 , wherein the particular number is at least two and the bloom filter encodes a route segment set defined by the POI routes corresponding to each of the particular number of POIs.

3. The method of claim 1 , wherein the POI request comprises the particular number.

4. The method of claim 1 , wherein the query criteria comprise at least one of a POI type or one or more keywords.

5. The method of claim 1 , further comprising generating a POI list comprising information identifying each of the particular number of POIs and providing the POI list with the bloom filter.

6. The method of claim 5 , wherein the POI list comprises information identifying a target location for each POI route.

7. The method of claim 5 , wherein the POI list comprises at least one of a length of each POI route or an expected travel time for each POI route.

8. The method of claim 1 , wherein the route determination algorithm is Dijkstra's algorithm and a cost value assigned to each new segment is determined based on at least one of a length of the new segment or an expected travel time for the new segment.

9. An apparatus comprising at least one processor, a communications interface configured for communicating via at least one network, and at least one memory storing computer program code and a network version of a digital map, the at least one memory and the computer program code configured to, with the processor, cause the apparatus to at least:
receive a point of interest (POI) request comprising query criteria and information identifying a starting location;
identify a network version starting segment based on the information identifying the starting location and the network version of the digital map;
expand a route determination algorithm starting at the starting segment, wherein when the route determination algorithm is expanded to a new segment, it is determined whether any POIs associated with the new segment satisfy the query criteria;
responsive to determining that a POI associated with the new segment satisfies the query criteria, extract a POI route from the starting segment to the POI from a state of the route determination algorithm, wherein the POI route identifies segments extending between the network version starting segment and the POI;
responsive to identifying a particular number of POIs that satisfy the query criteria, generate a plurality of map version agnostic identifiers based on the segments of a plurality of POI routes and the network version of the digital map, each of the plurality of map version agnostic identifiers identifying a respective segment of at least one POI route of the plurality of POI routes, the plurality of POI routes including a respective POI route extracted for each POI of the particular number of POIs;
code each of the plurality of map version agnostic identifiers using at least one coding function;
generate a bloom filter having the plurality of coded map version agnostic identifiers as members, such that the bloom filter encodes the plurality of POI routes by encoding each segment from the starting segment to a respective POI of each of the plurality of POI routes; and
provide a data structure storing the bloom filter such that a mobile apparatus receives the data structure.

10. The apparatus of claim 9 , wherein the particular number is at least two and the bloom filter encodes a route segment set defined by the POI routes corresponding to each of the particular number of POIs.

11. The apparatus of claim 9 , wherein the POI request comprises the particular number.

12. The apparatus of claim 9 , wherein the query criteria comprise at least one of a POI type or one or more keywords.

13. The apparatus of claim 9 , wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to at least generate a POI list comprising information identifying each of the particular number of POIs and provide the POI list with the bloom filter.

14. The apparatus of claim 13 , wherein the POI list comprises information identifying a target location for each POI route.

15. The apparatus of claim 13 , wherein the POI list comprises at least one of a length of each POI route or an expected travel time for each POI route.

16. The apparatus of claim 9 , wherein the route determination algorithm is Dijkstra's algorithm and a cost value assigned to each new segment is determined based on at least one of a length of the new segment or an expected travel time for the new segment.

17. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising executable portions configured, when executed by a processor of an apparatus, to cause the apparatus to:
receive a point of interest (POI) request comprising query criteria and information identifying a starting location;
identify a network version starting segment based on the information identifying the starting location and a network version of a digital map;
expand a route determination algorithm starting at the starting segment, wherein when the route determination algorithm is expanded to a new segment, it is determined whether any POIs associated with the new segment satisfy the query criteria;
respons

Assignees

• Here Global Bv

Inventors

• Cajias Raul
• Rolf Daniel

Classifications

• G01C21/3476 Primary

  using point of interest [POI] information, e.g. a route passing visible POIs · CPC title

• G01C21/3611

  using character input or menus, e.g. menus of POIs (character input methods in general G06F3/0233) · CPC title

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/3679 Primary

  Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities (G01C21/3611 takes precedence) · CPC title

• G01C21/3885

  Transmission of map data to client devices; Reception of map data by client devices · CPC title