ADAPTIVE INDEX WITH VARIABLE COMPRESSION

• US 20080016066A1
• Filed: 06/28/2007
• Published: 01/17/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: SANDLER, ILYA M., Kuznetsov, Tsia
• Application Number:
  US11/770,058
• Publication Number:
  US 20080016066A1
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Present invention builds on the trie concept to construct a system for compact indexing and efficient multi-dimensional searching of objects using a flexible composition of a string search key and other search criteria, to facilitate fast prototyping of compressed object store and search trees, which embody a variety of search methods.

Claims

1. A computer-implemented method comprising;

searching a tree, the tree being constructed with nodes associated with a key, the tree being pruned according to the given compression criteria, the tree including leaf nodes storing multiple objects or referencing multiple objects in an object store, the multiple objects having different key values, the search including searching to find a leaf node based on a search key;

wherein the search further comprises checking the objects indicated by the leaf node.

2. The computer-implemented method of claim 1, wherein the leaf nodes are associated with the same key prefixes as their parent nodes.

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

4. The computer-implemented method of claim 3, wherein the indications of other search criteria include indications of object attributes that are not found among the node'"'"'s offspring.

5. The computer-implemented method of claim 3, wherein the indications of other search criteria include indications of object attributes that are included in at least one offspring of the node.

6. The computer-implemented method of claim 1, wherein an API is used to select a key structure for the search system and in response to the selection of the key structure, keys of objects are used to construct the object store and tree.

7. The computer-implemented method of claim 1, wherein a user inputs a key to an application character by character, the application searching the tree to indicate valid next input characters.

8. The computer-implemented method of claim 7, wherein the application provides an output indicating the valid next characters.

9. The computer-implemented method of claim 1, wherein the key structure indicates a geographic locality or object'"'"'s name.

10. The computer-implemented method of claim 1, wherein the key structure indicates states and cities.

11. The computer-implemented method of claim 1, wherein the key structure indicates streets.

12. The computer-implemented method of claim 1, wherein the key structure indicates street intersections.

13. The computer-implemented method of claim 1, wherein the key structures indicates Points of Interest.

14. The computer-implemented method of claim 1, wherein the key structure indicates coordinates.

15. The computer-implemented method of claim 1, wherein the key structure indicates objects linked to locations.

16. The computer-implemented method of claim 1, wherein the leaf nodes indicate multiple objects with the same prefix inherited from the leaf'"'"'s parent.

17. The computer-implemented method of claim 1, wherein the search is done for object names.

18. The computer-implemented method of claim 1, wherein the search is done for geo-coding, geo-lookup, reverse geocoding, and Points of Interest.

19. A system comprising;

an application and;

a search system to search a tree for the application, the tree being constructed with nodes associated with a key, the tree including leaf nodes associated with multiple objects in an object store, the multiple object having different key values, the search including searching to find a leaf node based on a search key;

wherein the search further comprises checking the objects indicated by the leaf node.

20. The system of claim 19, wherein nodes store indications of other search criteria.

21. The system of claim 20, wherein the indications of other search criteria include indications of object attributes that are not found among the node'"'"'s offspring.

22. The system of claim 19, wherein the objects searched for are non-spatial objects.

23. The system of claim 20, wherein the indications of other search criteria include indications of object attributes that are included in at least one offspring of the node.

24. The system of claim 19, wherein the objects searched for are spatial objects.

25. The system of claim 19, wherein an API is used to select a key structure for the search system and in response to the selection of the key structure, keys of objects are used to construct the object store and tree.

26. The system of claim 19, wherein a user inputs data to an application, the application searching the tree to indicate valid next input characters.

27. The system of claim 25, wherein the application provides a display indicating the valid next characters.

28. The system of claim 19, wherein a portion of the key indicates a state.

29. The system of claim 19, wherein a portion of the key indicates a city.

30. The system of claim 19, wherein a portion of the key indicates a street.

31. The system of claim 19, wherein a portion of the key indicates a street intersection.

32. The map based system of claim 19, wherein the key structure indicates points of interest.

33. The map based system of claim 19, wherein the key structure indicates coordinates.

34. The map based system of claim 19, wherein the key structure indicates objects linked to spatial objects.

35. The map based system of claim 19, wherein the leaf nodes indicate multiple objects with the same prefix.

36. The map based system of claim 19, wherein the search is done for geo-coding.

37. The map based system of claim 19, wherein the search is done for geo-lookup.

38. The map based system of claim 19, wherein the search is done for reverse geocoding.

39. The map based system of claim 19, wherein the search is done to locate Points of Interest.

40. A computer-implemented method comprising;

searching a tree to determine available next characters, the tree being constructed with nodes associated with a key, the tree including leaf nodes associated with multiple objects in an object store, the multiple object having different key values, wherein the search to determine available next characters includes getting available next character information from the tree and/or from objects in the object store.

41. A computer-implemented method of constructing a tree structure comprising:

receiving a list of objects with keys following a key structure;

constructing a full tree structure; and

combining nodes such that most leaf nodes are associated with multiple objects.

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

43. The computer-implemented method of claim 42, wherein the indications of other search criteria include indications of object attributes that are not found among the node'"'"'s offspring.

44. The computer-implemented method of claim 42, wherein the indications of other search criteria include indications of object attributes that are included in at least one offspring of the node.

45. The computer-implemented method of claim 42, wherein an API is used to select a key structure for the search system and in response to the selection of the key structure, keys of objects are used to construct the object store and tree.

46. The computer-implemented method of claim 41, wherein the tree height is pruned according to the compression criteria.

47. The computer-implemented method of claim 41, wherein the combining steps includes combining leaf nodes.

48. The computer-implemented method of claim 41, wherein the objects referenced by short leaf nodes are stored contiguously.

49. The computer-implemented method of claim 41, wherein the objects referenced by long leaf nodes point to non-sequential objects.

50. A computer-implemented method comprising:

searching nodes of a tree, the nodes of tree indicating key information, at least some nodes indicating additional search criteria information, the search being multi-dimensional such that the key information is checked for a first dimension of the search and the search criteria information is checked for an additional dimensions of the search.

51. The system of claim 50, wherein the key values are compared to user input in the first dimension of the search.

52. The system of claim 50, wherein the pruned tree includes leaf nodes that store multiple objects or reference multiple objects in an object store.

53. The system of claim 50, wherein the search criteria indicate object attributes not found among the node'"'"'s offspring.

54. The system of claim 50, wherein the search criteria indicate object attributes included in the node'"'"'s offspring.

55. A computer-implemented system comprising;

a) a definition, for a class of objects, of string search key components that can be manipulated to accommodate a multitude of user interfaces;

b) an object store that distinguishes between components of a search key;

c) a composition of a search key structure from said components to yield a given user interface;

d) an adaptable search tree composed for a given search key definition where nodes are associated with a search key structure, the leave nodes store objects or reference objects in an object store, and the tree storage is minimized based on a given compression criteria, wherein an adaptable search method is used to locate matching objects via the search tree and said object store, the search adapting to the tree structure resulting from compression and a given user interface.

56. The computer implemented system of claim 55, where retrieval of matching objects from the said tree is based on an input of a partial or a full search key.

57. The computer implemented system of claim 55, where a search key is defined by selecting a full set or a subset of primary search key components.

58. The computer implemented system of claim 55, where a search key is defined by imposing an order on selected primary search key components.

59. The computer implemented system of claim 55, where the object store order is imposed by the primary search key.

60. The computer implemented system of claim 55, wherein one or more search trees, each with its own search key structure, can reference the same object store.

61. The computer implemented system of claim 55, where unique key structure is defined for a class of objects.

62. The computer implemented method of claim 55, wherein next available input characters can be retrieved from compressed tree and/or an object store.

63. The computer implemented system of claim 55, wherein for a given user interface profile and a chosen compression criteria, a score is generated for search tree size and best, average and worst case search performance, giving system designer a tool to balance various requirements by comparing scores of different implementations.

64. The computer implemented system of claim 55, accommodating multi-dimensional search by optionally storing at each tree node additional search criteria indicating presence of at least one object matching a given criterion among that node'"'"'s offspring.

65. The computer implemented system of claim 55, wherein the compression includes combining and splitting nodes and branches.

66. The computer implemented system of claim 65, wherein the combining and splitting is done in a single step.

67. A computer implemented system for accommodating a variety of user interface look and feel profiles, comprising:

a) a definition, for a class of objects, of a string search key components that can be manipulated to accommodate a multitude of user interfaces;

b) an object store that distinguishes between components of a search key;

c) a composition of a search key structure from said components whereby manipulation of components of a key implement a different user interface;

d) an API to define a string key structure whereby a designer can select components of a key and an order of components in a key that results in a different user interface of the search; and

e) an adaptive compressed search tree to accommodate object search for one of a multitude of user interfaces that can be implemented from search key components in the object store, wherein nodes are associated with a search key structure, the leaves store objects or reference objects in an object store.