NEAREST SEARCH ON ADAPTIVE INDEX WITH VARIABLE COMPRESSION

• US 20080040384A1
• Filed: 06/28/2007
• Published: 02/14/2008
• Est. Priority Date: 06/30/2006
• Status: Abandoned Application

• Current Assignee: Tele Atlas North America (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Kuznetsov, Tsia
• Application Number:
  US11/770,426
• Publication Number:
  US 20080040384A1
• Time in Patent Office: Days
• US Class Current: 707/103Y
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A search system can search nodes of a tree to find the object stored in the tree that is nearest to a position input by the user. The tree can be constructed using object keys with interlaced coordinates such that nodes in the tree correspond to a bounding box that bounds a subset of objects. The search algorithm can find the nearest object to a position.

Claims

1. A computer-implemented method comprising:

a search system that searches nodes of a tree for a nearest object, the tree constructed using object keys that encode coordinates such that nodes in the tree correspond to a bounding box that is bounding a subset of the objects, the search algorithm finding the nearest object to a position;

wherein the bounding boxes of the tree nodes below the root only cover regions where objects are present and wherein the search eliminates nodes with certain bounding boxes from consideration.

2. The computer-implemented method of claim 1, wherein the precision of an encoded object key increases at every node on the path from the root to a leaf.

3. The computer-implemented method of claim 1, wherein the coordinates include latitude and longitude.

4. The computer readable medium of claim 1, wherein the object key information for a node is sufficient to encode its bounding box, such as by means of a corner position and extent.

5. The computer-implemented method of claim 1, wherein the coordinate information is interlaced.

6. The computer-implemented method of claim 5, wherein the lower left corner of the node'"'"'s bounding box is determined by de-interlaced coordinates, and the extent of the bounding box for each coordinate is determined from the make-up of the coordinates.

7. The computer-implemented method of claim 1, wherein nodes store indications of other search criteria.

8. The computer-implemented method of claim 7, wherein the indications of other search criteria include indications of categories of objects that are not included in a bounding box of a node.

9. The computer-implemented method of claim 8, wherein the indications of other search criteria include indications of categories of objects that are included in a bounding box of a node.

10. The computer-implemented method of claim 1, wherein most leaf nodes point to multiple objects.

11. The computer-implemented method of claim 1, wherein the tree construction tends to maximize the number of objects associated with the leaf nodes based on a given criteria

12. The computer-implemented method of claim 1, wherein the method maintains a maximum search radius value and, based on the maximum search radius, eliminates from consideration some nodes.

13. The computer-implemented method of claim 1, wherein the method maintains a minimum distance to a position for nodes and uses the minimum distance to eliminate from consideration nodes whose minimum distance value is greater than the maximum search radius.

14. The computer-implemented method of claim 1, wherein the node'"'"'s minimum and maximum distances to a position are calculated using the node'"'"'s bounding box.

15. The computer-implemented method of claim 1, wherein the objects include spatial objects.

16. The computer-implemented method of claim 15, wherein the spatial objects include map geometry features.

17. The computer-implemented method of claim 15, wherein the spatial objects include points of interest.

18. The computer implemented method of claim 1, wherein the computer-implemented method is part of a mapping system.

19. A system comprising:

an application including an interface to obtain a position;

wherein the application uses a search system that searches nodes of a tree for a nearest object to the position, the tree based on a search key with interlacing coordinates such that nodes in the tree correspond to a bounding box in given coordinates, the search finding the nearest object to a position, wherein the bounding boxes of the tree nodes below the root only cover regions where objects are present and wherein the search eliminates nodes with certain bounding boxes from consideration.

20. The system of claim 19, wherein the position is obtained based on a cursor selection.

21. The system of claim 19, wherein the position is obtained based on a user touch., a user location, a user voice input, or by other user interface means.

22. The system of claims 19, wherein the application includes a map display.

25. The system of claim 19, wherein the interface obtains the position from a GPS or other navigation system.

23. A computer-implemented system comprising:

a search system that searches nodes of a tree for a nearest object, the tree constructed using object keys that encode coordinates such that nodes in the tree correspond to a bounding box that is bounding a subset of objects, the search finding the nearest object to a position;

wherein the system maintains an overall maximum search radius value and a minimum distance for certain nodes and wherein the system uses the minimum distance to eliminate from consideration nodes whose minimum distance is greater than the maximum search radius.

24. A computer-implemented method comprising:

a search system that searches nodes of a tree for a nearest spatial object, the tree constructed using object keys that encode coordinates such that nodes in the tree correspond to a bounding box that is bounding a subset of the objects, the search algorithm finding the nearest spatial object to a position, wherein the bounding boxes of the tree nodes below the root only cover regions where spatial objects are present and wherein the method maintains a maximum search radius value and, based on the maximum search radius, eliminates from consideration some nodes, the search radius value being decreased based on bounding box information.