METHOD AND SYSTEM FOR MULTI-DIMENSIONAL AND GEOGRAPHIC SEARCH

• US 20100174721A1
• Filed: 12/21/2009
• Published: 07/08/2010
• Est. Priority Date: 12/23/2008
• Status: Active Grant

• Current Assignee: Zhijing George Mou
• Original Assignee: Zhijing George Mou
• Inventors: Mou, Zhijing George
• Granted Patent: US 8,510,310 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2448 for particular applications; for extensibility, e.g. user defined types
• CPC Class Codes: G06F 16/29 Geographical information databases

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.

Claims

1. A multi-dimensional and geographic-search system comprising:

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.

2. The multi-dimensional and geographic-search system of claim 1 wherein the search-region-receiving component receives real-valued longitudinal and latitudinal coordinates for two points that define a geographical region.

3. The multi-dimensional and geographic-search system of claim 2 wherein the real-valued longitudinal and latitudinal coordinates for two points that define a geographical region are coordinates for two, diagonally opposed corners of a rectangular region.

4. The multi-dimensional and geographic-search system of claim 1 wherein the search-region-receiving component receives real-valued coordinates for two points that define a volume in a space of three or more dimensions.

5. The multi-dimensional and geographic-search system of claim 1 wherein the recursive-decomposition component decomposes the region into sub-regions based on the indices generated by the indexing component by:

when a termination condition is not satisfied,

decomposing the region according to a pattern computed for the region to generate two or more lower-level sub-regions; and

recursively decomposing the two or more sub-regions.

6. The multi-dimensional and geographic-search system of claim 5 wherein a region or sub-region is decomposed into lower-level sub-regions by:

computing a pattern for the region or sub-region;

using the computed pattern to select a decomposition method; and

applying the selected decomposition method to the region or sub-region.

7. The multi-dimensional and geographic-search system of claim 6 wherein a decomposition method, when applied to a region or sub-region:

identifies corner points for two or more sub-regions of the region or sub-region; and

computes one-dimensional indices, based on the identified corner points, for the two or more sub-regions of the region or sub-region.

8. The multi-dimensional and geographic-search system of claim 7 wherein the decomposition method decomposes a region or sub-region in such a way that the precisions of the sub-regions produced by the decomposition method are maximized.

9. A mapping system comprising:

a tile-specifying component that receives coordinates that define a region;

an indexing component that generates an index for each coordinate that defines the region;

a recursive-decomposition component that decomposes the region into sub-regions based on the indices generated by the indexing component; and

a tile-retrieving component that retrieves tiles corresponding to the sub-regions computed by the recursive-decomposition component.

10. The mapping system of claim 9 wherein the tile-specifying component receives real-valued longitudinal and latitudinal coordinates for two points that define the region.

11. The mapping system of claim 10 wherein the real-valued longitudinal and latitudinal coordinates for two points that define the region are coordinates for two, diagonally opposed corners of a rectangular region.

12. The mapping system of claim 9 wherein the recursive-decomposition component decomposes the region into sub-regions based on the indices generated by the indexing component by:

when a termination condition is not satisfied,

decomposing the region according to a pattern computed for the region to generate two or more lower-level sub-regions; and

recursively decomposing the two or more sub-regions.

13. The mapping system of claim 12 wherein a region or sub-region is decomposed into lower-level sub-regions by:

computing a pattern for the region or sub-region;

using the computed pattern to select a decomposition method; and

applying the selected decomposition method to the region or sub-region.

14. The mapping system of claim 13 wherein a decomposition method, when applied to a region or sub-region:

identifies corner points for two or more sub-regions of the region or sub-region; and

computes one-dimensional indices, based on the identified corner points, for the two or more sub-regions of the region or sub-region.

15. The mapping system of claim 14 wherein the decomposition method decomposes a region or sub-region in a such a way that the precisions of the sub-regions produced by the decomposition method are maximized.