Method and system for multi-dimensional and geographic search
OwnerZhijing George Mouinventor
Life of this patent
Estimating the term…
Abstract
One embodiment of the present invention is directed to a multi-dimensional and geographic-search system that includes a search-region-receiving component that receives coordinates that define a region to be searched, an indexing component that generates an index for each of the received coordinates, a recursive-decomposition component that decomposes the region into sub-regions based on the indices generated by the indexing component, and a search component that selects points of interest from a points-of-interest database by comparing indices computed for the sub-regions to indices computed and stored in the database for each point of interest. Additional embodiments are directed to carrying out efficient, index-based searching for various additional types index-characterized entities.
Claims15
A multi-dimensional and geographic-search system comprising:
- a search-region-receiving component that receives a number i of sets of coordinates that define a region to be searched, the number i greater than 1 and each of the i sets of coordinates including d coordinates associated with a multidimensional space, each of the d coordinates represented by an ordered sequence of n bits;
- an indexing component that generates, by a bit-permutation mapping, i integer indexes that include an integer index for each of the i sets of the received coordinates, the bit-permutation mapping grouping, for each of the n bits used to represent each of the d coordinates of a set of coordinates, the bits of the d coordinates at each bit position within the ordered-bit-sequence representations of the d coordinates together into a subsequence of bits within an ordered sequence of subsequences of bits that together compose the integer index;
- a recursive-decomposition component that decomposes the region into sub-regions based on the integer indices generated by the indexing component;
- and
- a search component that selects points of interest from a points-of-interest database by comparing integer indices computed for the regular sub-regions to indices computed and stored in the database for each point of interest.
A mapping system comprising:
- a tile-specifying component that receives a number i of sets of coordinates that define region, the number i greater than 1 and each of the i sets of coordinates including d coordinates associated with a multidimensional space, each of the d coordinates represented by an ordered sequence of n bits;
- an indexing component that generates, by a bit-permutation mapping, i integer indexes that include an integer index for each i sets of the coordinate that defines the region, the bit-permutation mapping grouping, for each of the n bits used to represent each of the d coordinates of a set of coordinates, the bits of the d coordinates at each bit position within the ordered-bit-sequence representations of the d coordinates together into a subsequence of bits within an ordered sequence of subsequences of bits that together compose the integer index;
- a recursive-decomposition component that decomposes the region into regular sub-regions based on the integer indices generated by the indexing component;
- and
- a tile-retrieving component that retrieves tiles corresponding to the regular sub-regions computed by the recursive-decomposition component.
Dependencies are inferred from the claim text.