Geometry-based search engine for navigation systems

• US 7,574,428 B2
• Filed: 03/21/2006
• Issued: 08/11/2009
• Est. Priority Date: 10/11/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Telmap Limited (Intel Corporation)
• Inventors: Fagin, Alexander, Leiserowitz, Eran
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): OWYANG, MICHELLE N
• Application Number:
  US11/384,262
• Publication Number:
  US 20070083557A1
• Time in Patent Office: 1,239 Days
• Field of Search: 707/3, 701200-226
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A computer-implemented method for determining a requested map location includes providing a database holding a plurality of map objects having respective descriptors and loci. A search query including one or more query terms that describe the requested map location is accepted. One or more matched map objects are identified in the database such that the respective descriptors of the matched map objects each match at least one of the query terms. The respective loci of the matched map objects are processed to determine the requested map location.

Claims

1. A computer-implemented method for determining a requested map location, comprising:

providing a database holding a plurality of map objects having respective descriptors and loci;

accepting a search query comprising one or more query terms that describe the requested map location;

identifying in the database two or more matched map objects such that the respective descriptors of the matched map objects each match at least one of the query terms;

rendering the matched map objects onto a common grid using the loci;

identifying grid cells overlapped by at least one of the rendered map objects;

assigning respective scores to the identified grid cells based on a number of the matched map objects that overlap each of the identified grid cells; and

determining the requested map location responsively to the scores.

2. The method according to claim 1, wherein assigning the scores comprises assigning respective weights to the matched map objects and assigning the scores to the overlapped grid cells responsively to the weights.

3. The method according to claim 1, wherein rendering the matched map objects to the grid comprises representing the grid using a dynamic data structure so as to allocate memory only to overlapped grid cells when assigning the scores.

4. The method according to claim 3, wherein the dynamic data structure comprises one or more binary search trees.

5. The method according to claim 1, wherein providing the database comprises representing a first map object using first logical cells having a first area and representing a second map object using second logical cells having a second area different from the first area, and wherein rendering the respective matched map objects onto the grid comprises overlaying the first and second logical cells onto the grid cells of the common grid.

6. The method according to claim 1, wherein identifying the two or more matched map objects comprises comparing at least some of the map objects in the database to at least one of the query terms using an approximate string matching process.

7. The method according to claim 1, wherein accepting the search query comprises accepting free text input comprising the one or more query terms.

8. The method according to claim 1, wherein providing the database comprises associating the map objects with respective data layers, and wherein identifying the two or more matched map objects comprises searching for the two or more matched map objects only within a subset of the data layers.

9. The method according to claim 1, and comprising displaying a map comprising the requested map location to a user.

10. The method according to claim 1, and comprising providing to a user navigational instructions for traveling to the requested map location.

11. The method according to claim 1, wherein the map objects comprise streets having respective street names, and wherein at least one of the query terms comprises at least a part of a street name.

12. Apparatus for determining a requested map location, comprising:

a database, which is arranged to hold a plurality of map objects having respective descriptors and loci;

a user input device, which is arranged to accept a search query comprising one or more query terms that describe the requested map location; and

a processor, which is arranged to identify in the database two or more matched map objects such that the respective descriptors of the matched map objects each match at least one of the query terms, to render the respective matched map objects onto a common grid using the loci, to identify grid cells overlapped by at least one of the rendered map objects, to assign respective scores to the identified grid cells based on a number of the matched map objects that overlap each of the identified grid cells, and to determine the requested map location responsively to the scores.

13. The apparatus according to claim 12, wherein the processor is arranged to assign respective weights to the matched map objects and to assign the scores to the overlapped grid cells responsively to the weights.

14. The apparatus according to claim 12, wherein the processor is arranged to represent the grid using a dynamic data structure so as to allocate memory only to overlapped grid cells when assigning the scores.

15. The apparatus according to claim 14, wherein the dynamic data structure comprises one or more binary search trees.

16. The apparatus according to claim 12, wherein the processor is arranged to represent a first map object using first logical cells having a first area, to represent a second map object using second logical cells having a second area different from the first area, and to render the respective matched map objects onto the grid by overlaying the first and second logical cells onto the grid cells of the common grid.

17. The apparatus according to claim 12, wherein the processor is arranged to compare at least some of the map objects in the database to at least one of the query terms using an approximate string matching process so as to identify the two or more matched map objects.

18. The apparatus according to claim 12, wherein the user input device is arranged to accept free text input comprising the one or more query terms.

19. The apparatus according to claim 12, wherein the map objects in the database are associated with respective data layers, and wherein the processor is arranged to identify the two or more matched map objects only within a subset of the data layers.

20. The apparatus according to claim 12, and comprising a display, which is arranged to display a map comprising the requested map location to a user.

21. The apparatus according to claim 12, wherein the processor is arranged to provide to a user navigational instructions for traveling to the requested map location.

22. The apparatus according to claim 12, wherein the map objects comprise streets having respective street names, and wherein at least one of the query terms comprises at least a part of a street name.

23. A computer-readable medium storing program instructions, the program instructions configured to perform a method for determining a requested map location when executed on a computer, said method comprising:

accepting a search query comprising one or more query terms that describe the requested map location,

identifying in a database holding a plurality of map objects having respective descriptors and loci one or more matched map objects such that the respective descriptors of the matched map objects each match at least one of the query terms,

rendering the respective matched map objects onto a common grid using the loci,

identifying grid cells overlapped by at least one of the rendered map objects,

assigning respective scores to the identified grid cells based on a number of the matched map objects that overlap each of the identified grid cells, and

determining the requested map location responsively to the scores.

24. The computer-readable medium according to claim 23, wherein the map objects comprise streets having respective street names, and wherein at least one of the query terms comprises at least a part of a street name.