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.

Description:
CLAIM OF PRIORITY 
       [0001]    This application claims priority from the following co-pending applications, which are hereby incorporated in their entirety: U.S. Provisional Application No. 60/806,366 entitled: “ADAPTIVE INDEX WITH VARIABLE COMPRESSION”, by Tsia Kuznetsov, et al., filed Jun. 30, 2006, (Attorney Docket No. TELA-07780US0) and U.S. Provisional Application No. 60/806,367 entitled: “NEAREST SEARCH ON ADAPTIVE INDEX WITH VARIABLE COMPRESSION”, by Tsia Kuznetsov, filed Jun. 30, 2006, (Attorney Docket No. TELA-07781US0). 
     
     BACKGROUND OF INVENTION 
       [0002]    A number of applications can use stored geographic data to provide mapping services for a user. The applications that can be implemented for mobile or stationary systems can include map rendering, spatial object search, geocoding or geo-lookup, path search, direction and positioning. Object search, particularly object search by a string key, can be used for these applications. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0003]      FIG. 1  shows a map-based system of one embodiment of the present invention. 
           [0004]      FIGS. 2A-2B  shows systems with and without indexing. 
           [0005]      FIGS. 3A-3B  shows a short leaf node and a long leaf node. 
           [0006]      FIGS. 4A-4B  shows a tree system of one embodiment. 
           [0007]      FIG. 5  is a flowchart of a method of one embodiment. 
           [0008]      FIGS. 6A-6C  illustrates the operation of embodiments of the method of  FIG. 5 . 
           [0009]      FIG. 7  illustrates an example where nodes contain indications of other search criteria, such as exclusion or inclusion information. 
           [0010]      FIG. 8  illustrates the use of a single object store with multiple trees. 
           [0011]      FIG. 9A-9B  illustrates the use of an API to select a key structure for the tree. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    One embodiment of the present invention is a computer-implemented method for adaptive construction of a search system for searching objects by their string key. The search system can include objects that reside in the object store  108 , and the tree  102  that can be constructed using the objects with their string key structure. 
         [0013]    The tree  102  can be based on a trie, or prefix tree, which is an ordered tree data structure that is used to index objects where the keys are strings that accommodate a specific search method. The trie facilitates retrieval of the choice of next characters, given a partial string key input. A description of tries is given in Donald Knuth.  The Art of Computer Programming,  Volume 3:  Sorting and Searching,  Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.3: Digital Searching, pp. 492-512. 
         [0014]    The trie can be reconstructed to be adaptable to restrictive storage requirements through a serious of steps that manipulate key prefixes and minimize the number of nodes and leaves. In one embodiment, most leaf nodes of the tree  102  can be associated with multiple objects in the object store, which can mean that only a portion of the full key is searched in the tree before obtaining a group of objects from the object store. For example, the tree  102  can be a variable-scale compression of a full trie. 
         [0015]    Tree storage can be minimized based on a given compression criteria. An adaptable search method can be used to retrieve objects via the search tree and said object store. The search can adapt to the tree structure resulting from compression and a given user interface. 
         [0016]    In one embodiment, the object store  108  models spatial objects in the real world that can be searched using a string key. The real world spatial objects can include cities, streets in the city, intersections, points of interests (POIs), or another type of object that can be associated with a string key. 
         [0017]    In one embodiment, objects can be stored in the leaves of the trie. In another embodiment, to accommodate multiple search methods on the same set of objects, a separate object store can be constructed for a given type of object as either fixed length or variable length storage. Storage for variable length objects can be constructed with a fixed length object offset directory. Such an object store can accommodate search and scrolling of objects. 
         [0018]    The object store entries can be determined by the unique key of each object, wherein the order of objects in the store can be determined by the object&#39;s sorting key. The object store can distinguish between components of the search key 
         [0019]    In one embodiment, once the object store is set up, the search tree  102  can be constructed such that the reference to each object in the store can be found in a tree leaf using object&#39;s search key. 
         [0020]    The search key structure of the tree can indicate spatial objects, such as streets, street intersections, Points of Interest (POIs) or other elements or attributes of objects. In one embodiment, the order by which components of the key for a given class of objects are concatenated indicates specific search method for this class of objects. The order of concatenation of the key components can be the simple mechanism by which the system designer can rapidly prototype and experiment with various user interfaces embodied in a multitude of string key definitions for a given class of objects. 
         [0021]    An API can be implemented and used in an application to aid in the construction of the search key and thus the search method, to allow designers to produce and experiment with a variety of user interfaces for the search of an object. In one embodiment, a GUI can be built using such API to define and select a key structure(s) for the search method(s) on a given class of objects, whereby imposing an appropriate order on the object store and tree(s). The API can give system designers the flexibility to change a search system&#39;s interface with ease typically associated with the RDBMS technology, without relying on a relational database management system, which may have impractical storage requirements for some environments. 
         [0022]    Thus by selecting the string key components and the component order for a composition of the key structure, a designer can assess a variety of user interfaces and underlying search methods. 
         [0023]      FIGS. 9A and 9B  show the construction of trees and object stores using an API  902 . A designer can select key components and order from the data  904 . For example, data fields of the data  904  can be used as key components. The key structure and the data can be used to construct a tree and object store that can be accessed via a user interface, which implements a search method expressed in the key structure. 
         [0024]      FIG. 9A  shows an example where the key structure is given by CITY/STREET. This means that the user interface  906  is adapted to receive data in this order.  FIG. 9B  shows an example when the key structure is given by STREET/CITY with the user interface  908  adapted to receive data in this order. 
         [0025]    For a given user interface profile and a chosen compression criteria, a score can be generated for search tree size, object store size, memory requirements, and best and worst case search performance. This can give system designer a tool to balance various requirements by comparing scores of different implementations. 
         [0026]    For example, the amount of compression can affect the performance of the system. High levels of compression can mean that more objects need to be obtained from the object store and analyzed. Low levels of compression can result in large storage requirements for the tree. The variable compression criteria that regulate tree construction and can maximize number of objects referenced by a leaf node can be tuned to reasonably balance performance, memory and storage use for the ultimate application. In one embodiment, compression criteria regulate a minimum number of objects under any branch of the tree. 
         [0027]    Looking again at  FIG. 1 , the tree can include leaf nodes that reference multiple objects in an object store  108  as the result of variable compression. The objects or object references in a leaf node can have different key values, with the common prefix matching that of a leaf&#39;s parent node. This can mean a more complex search algorithm that augments a partial search on the tree with following the object references to the object store to complete the search, as opposed to the straight forward search on the original non-compressed trie structure, 
         [0028]    The leaf nodes can be distinguished as a short leaf node or a long leaf node. A short leaf references a first object in the contiguous list, and a number of objects referenced. A long leaf can reference an arbitrary list of objects by storing a count of references, and a direct reference for each object in the list. The search can include finding a leaf node  110  based on a search key and locating a set of matches among the objects referenced by the leaf node. 
         [0029]    In one embodiment, a user inputs a search string character by character and the application searches the tree  102  to indicate a set of valid next input characters, until the search string is complete or the user requests a set of objects that match a partial key. The application can provide a display indicating the valid next characters, or otherwise output the valid next characters. In another embodiment, a user inputs an entire or a partial search string. The tree that supports such searches can store the key prefix string at each tree node, with the shortest at the root and the full search key at the leaf. In one embodiment of the present invention, the search tree is compressed by reducing the node&#39;s key prefix to store only its own extension of the parent&#39;s prefix, such that the actual key prefix of a node is obtained by concatenating all key prefix strings on the path from the root to this node with the node&#39;s stored key prefix. In one embodiment of the adaptive index, the search tree is further compressed by collapsing nodes with a single child. 
         [0030]    One embodiment of the present invention is a system comprising an application  104  with a map display  106  and a search system including a tree  102  and the object store  108 . The Tree  102  can be constructed with nodes associated with a key structure. The tree  102  can be compressed by reducing each node&#39;s prefix. The tree  102  can include leaf nodes that store objects, when the class of objects is intended to be accessed via a single search method. The tree  102  can include leaf nodes that contain references to objects in the object store, when that class of objects is intended to be accessed via more than one search method. The tree  102  can include leaf nodes that reference multiple objects in an object store  108 , as the result of variable compression. The search can include searching to find a leaf node  110  based on a search key and checking the objects indicated by the leaf node. 
         [0031]    The system  100  can have a user interface  110  that can receive input from the user and produce an output. One exemplary output can be next character indication that shows the valid next characters. The set of available next characters can be determined from a search of the tree  102  and/or object store  108  as discussed below. 
         [0032]      FIGS. 2A and 2B  shows examples of short leaf nodes that contain a pointer (ID) to the first object and a number of objects that can be retrieved from an object store with a minimum number of read operations.  FIG. 2A  shows an example where objects are stored in an object store  202  with fixed sized entries, requiring a single read (provided there is sufficient memory.)  FIG. 2B  shows an example where objects are stored in an object store  204  with variable sized entries. In that case, an offset array  206  with fixed sized offsets can be used to limit the number of read operations to two (provided there is sufficient memory.) 
         [0033]    In both cases, object data can be obtained corresponding to the number of counts. For example, if the count is 50, the next 50 objects can be obtained from the object store and analyzed as appropriate. Short leaf nodes reduce storage requirements for the tree. This can be valuable for mobile geographic applications implemented on resource-constrained systems. 
         [0034]    In one embodiment, consecutive objects can be stored in a short leaf as shown in  FIG. 3A . The short leaf node can contain an ID and a count. The order of the objects in the object store is arranged in the order indicated by the key structure. 
         [0035]      FIG. 3B  shows a long leaf. The long leaf can be used to point to non-consecutive objects with individual pointers for each object. 
         [0036]      FIG. 8  shows an example with two trees  802  and  804  pointing to objects in the same object store  806 . The two trees can be associated with two different input elements in a user interface. Typically, the tree whose search key structure follows the order of objects in the store  806  can use short leaf nodes to point to consecutive objects. The other trees can use long leaf nodes. Long leaves increase storage requirements. Number of read operations on long leaf objects is proportional to the number of objects in a long leaf. 
         [0037]      FIG. 4A  illustrates an example of how to get the set of “next available character” in one embodiment. If a user has input “PIN”, the next available characters can be obtained by checking the prefixes of children nodes for node  402 . 
         [0038]      FIG. 4B  shows a system where a leaf node  404  references multiple consecutive objects in the object store. In this example, the names of objects corresponding to node  404  are obtained from the object store and analyzed to get the “next character” information. In the example of  FIG. 4B , the names PINE RIDGE, PINE VALLEY, PINEBROOK, PINECONE, PINNACLE, PINTAIL, PINTO of objects associated with leaf node  404  all start with the user input “PIN”. These names can be analyzed to obtain the valid next characters {“,‘E’,‘N’,‘T’}, which can be output to the user. Scrolling and other functions can be implemented in a similar manner with groups of object data associated with leaf nodes being obtained and then processed for display. 
         [0039]    In one embodiment the leaf nodes need not have associated key information. This can mean that the leaf nodes will have the same key prefix as their parent node. This can allow the objects or object references to be easily combined into leaf nodes for most efficient packing. 
         [0040]    In one embodiment, the objects referenced by the leaf node can be accessed then analyzed to determine the next character and to implement scrolling. The tree can have the leaf nodes at different levels of the tree. 
         [0041]    One embodiment of the present invention is a computer-implemented method of constructing a tree comprising a list of keys following a key structure, constructing a full tree structure and then pruning it, by combining nodes such that most leaf nodes are associated with multiple objects. 
         [0042]    Compression techniques can include maximizing leaf node references to objects to minimize storage overhead required for each node, based on a given criteria. 
         [0043]      FIG. 5  shows an exemplary flowchart of one embodiment. In step  502 , a key structure is determined. An exemplary key structure for street name can be “street name?city-name” where “‘?’” Is a delimiting character. For example, “Kensington?San Francisco”. An exemplary key structure for Intersection may be “street1name?street2name?city-name”. Objects can be duplicated in the object store so that either order can be used to search for streets intersections. For example, “Oak?Elm?Sacramento” and “Elm?Oak?Sacramento” can represent two different tree search paths that lead to a single entry, or to two entries of the tree object store, each referencing the same real intersection with its set of attributes. 
         [0044]    In step  504 , a list of keys for the objects based on the key structure can be determined. The key structure can also determine the order of the objects in the object store. 
         [0045]    In step  506 , a full node structure can be created based on the list of keys. This full node structure can be compressed as shown in steps  508 ,  510  and  512  to reduce the size of the tree by reducing the number of nodes and leaves. Exemplary steps are also shown in  FIGS. 6A-6C . 
         [0046]    In  FIG. 6A , node  604  with a single child node  602  is combined with the child node  602  to form node  606 . Node  606  is associated with multiple characters in the search string. 
         [0047]      FIG. 6B  shows an example of a compressing step. In the example of  FIG. 6B , each grandchild node is checked to see whether it can be combined with another grandchild node. In one example, if both grandchild nodes have less than a given number of associated objects (such as 16 in one implementation), the tree is pruned to accommodate this criteria. In the example of  FIG. 6B , nodes  610 ,  612  and  614  are combined together to form node  616 . 
         [0048]      FIG. 6C  shows a case where node  620  is split into nodes  622  and  624  to keep the number of objects associated in each leaf node below a maximum size (such as 63 in one embodiment). 
         [0049]    The above example shows the steps as distinct. In another embodiment, the compression steps can be combined into a single step producing the same results. 
         [0050]    In one embodiment, tree nodes can store indications of other search criteria. A search or other operation on the tree can use the indications to determine whether the node and its offspring nodes or associated objects need to be further analyzed. In one embodiment, the indications can be used to implement an n-dimensional search 
         [0051]    In one embodiment, the searches can be filtered by object attributes such as a category or a city. The indications can include indications of object categories that are not found among the node&#39;s offspring and/or indications of object categories that are included in at least one of its offspring. Similarly, if indications include city id, the searches can be filtered by a city. In one embodiment, a user can search a point of interest by name, refined by a specified object category, and further refined by the name of the city where it resides. 
         [0052]    For example, if the presence or absence of points of interest categories is indicated on a tree node, a character search for a point of interest could eliminate from the search path the nodes that exclude a category, such as fast food. 
         [0053]    In one embodiment, the nodes can store category exclusion or inclusion information to simplify and speed up a search for a specific category. The exclusion information can indicate that no object associated with the node is in the category. The inclusion information can indicate that there is an object associated with the node in the category. 
         [0054]      FIG. 7  shows one example. In this example, a search on the tree segment can stop at node  702  if the search is for a restaurant and at node  704  if the search is for a gas station. The indications of other search criteria, such as exclusion information, can be implemented at the time of creation of the node tree. 
         [0055]    The tree of  FIG. 7  can be used for a multi-dimensional search. For example, the key information can be checked for a first dimension of the search and the search criteria information can be checked for additional dimensions of the search. 
         [0056]    In one example, the user interface can include checkboxes or the like to receive user input for additional search criteria indicated on the tree, for example object categories. The search can use the category information to determine which nodes to examine in the search. In the example of  FIG. 7 , if the user was looking for a gas station and had input a “P”, “I” would not be shown as a next available character because node  704  excludes gas stations. 
         [0057]    The search criteria can be a code associated with certain nodes to indicate the categories not found among the node&#39;s offspring or the like. The objects in the object store can also have associated category information so the two dimensional search can involve both the nodes of the tree and the objects in the object store. 
         [0058]    The API used to select the key structure can be used to add additional search criteria to the tree to enable the multi-dimensional search. 
         [0059]    As described in the co-pending U.S. Patent Application, NEAREST SEARCH ON ADAPTIVE INDEX WITH VARIABLE COMPRESSION, Ser. No. 60/806,367, (corresponding to attorney docket number TELA-07781US0), the search system can be used to do a nearest search to a specific position. 
         [0060]    One embodiment may be implemented using a conventional general purpose of a specialized digital computer or microprocessor(s) programmed according to the teachings of the present disclosure, as will be apparent to those skilled in the computer art. Appropriate software coding can readily be prepared by skilled programmers based on the teachings of the present discloser, as will be apparent to those skilled in the software art. The invention may also be implemented by the preparation of integrated circuits or by interconnecting an appropriate network of conventional component circuits, as will be readily apparent to those skilled in the art. 
         [0061]    One embodiment includes a computer program product which is a storage medium (media) having instructions stored thereon/in which can be used to program a computer to perform any of the features present herein. The storage medium can include, but is not limited to, any type of disk including floppy disks, optical discs, DVD, CD-ROMs, micro drive, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, DRAMs, flash memory of media or device suitable for storing instructions and/or data stored on any one of the computer readable medium (media), the present invention includes software for controlling both the hardware of the general purpose/specialized computer or microprocessor, and for enabling the computer or microprocessor to interact with a human user or other mechanism utilizing the results of the present invention. Such software may include, but is not limited to, device drivers, operating systems, execution environments/containers, and user applications. 
         [0062]    The forgoing description of preferred embodiments of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations will be apparent to one of ordinary skill in the relevant arts. For example, steps preformed in the embodiments of the invention disclosed can be performed in alternate orders, certain steps can be omitted, and additional steps can be added. The embodiments where chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications that are suited to the particular used contemplated. It is intended that the scope of the invention be defined by the claims and their equivalents.