System and method for determining exact location results using hash encoding of multi-dimensioned data

• US 9,646,036 B2
• Filed: 02/23/2015
• Issued: 05/09/2017
• Est. Priority Date: 03/01/2011
• Status: Active Grant

• Current Assignee: MongoDB, Inc.
• Original Assignee: MongoDB, Inc.
• Inventors: Merriman, Dwight, Horowitz, Eliot
• Primary Examiner(s): Tissot, Adam
• Assistant Examiner(s): CASTRO, PAUL A
• Application Number:
  US14/628,829
• Publication Number:
  US 20150161122A1
• Time in Patent Office: 806 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Aspects of the present invention are directed to system and methods for optimizing identification of locations within a search area using hash values. A hash value represents location information in a single dimension format. Computing points around some location includes calculating an identification boundary that surrounds the location of interest based on the location'"'"'s hash value. The identification boundary is expanded until it exceeds a search area defined by the location and a distance. Points around the location can be identified based on having associated hash values that fall within the identification boundary. Hashing operations let a system reduce the geometric work (i.e. searching inside boundaries) and processing required, by computing straightforward operations on hash quantities (e.g. searching a linear range of geohashes), instead of, for example, point to point comparisons.

Claims

1. A system for optimizing processing of location-based requests, the system comprising:

at least one processor operatively connected to a memory;

a hash component executable by the at least one processor and configured to generate a single dimension geospatial index from multi-dimension location inputs, the geospatial index comprising a plurality of bits;

an access component executable by the at least one processor and configured to access a given location for a point of interest and a distance threshold, wherein the given location and the distance threshold define a search area; and

an identification component executable by the at least one processor and configured to identify which locations associated with data in a database are within a distance from the point of interest, wherein the identification component is further configured to;

identify a subset of bits from the plurality of bits in of the geospatial index of the given location based on the distance threshold, the subset of bits including the most significant bits of the geospatial index and having fewer bits than the geospatial index;

generate the identification boundary based on the identified subset of bits in the geospatial index; and

identify locations within the distance from the point of interest based on the generated identification boundary.

2. The system according to claim 1, wherein the hash component is further configured to generate the single dimension geospatial index from a pair of location coordinates.

3. The system according to claim 2, wherein the hash component is further configured to interleave bits representing a first location value and a second location value from the pair of location coordinates to generate the single dimension geospatial index.

4. The system according to claim 3, wherein the hash component is further configured to reduce the first location value and the second location value by a respective minimum prior to generating the single dimension geospatial index.

5. The system according to claim 4, wherein the hash component is further configured to scale the reduced first location value and the reduced second location value prior to generating the single dimension geospatial index.

6. The system according to claim 5, wherein the hash component is further configured to round the reduced first location value and the reduced second location value to generate inputs to produce the single dimension geospatial index.

7. The system according to claim 1, wherein the identification component is further configured to:

generate an identification geospatial index, wherein the identification geospatial index includes the subset of bits; and

compute dimensions of the identification boundary based, at least in part, on the length of the subset of bits.

8. The system according to claim 7, wherein the hash component is further configured to invert the identification geospatial index to obtain identification boundary coordinates, and wherein the identification component is further configured to determine a position for the identification boundary based on the identification boundary coordinates.

9. The system according to claim 8, wherein the identification component is further configured to determine whether the dimensions of the identification boundary, at least, intersect with an outer bound of the search area.

10. The system according to claim 9, wherein the identification component is further configured to determine whether a condition is true in order to determine whether the identification boundary at least intersects with an outer bound of the search area, wherein the condition is at least one of:

an abscissa of a lower left corner of the identification boundary is less than the abscissa of the search area'"'"'s center minus the distance threshold;

the abscissa an of upper-right corner of the identification boundary is greater than an abscissa of the search area'"'"'s center plus the distance threshold;

the ordinate of a lower-left corner of the identification boundary is less than an ordinate of the search area'"'"'s center minus the distance threshold; and

an ordinate of an upper-right corner of the identification boundary is greater than the ordinate search area'"'"'s center plus the distance threshold.

11. The system according to claim 1, further comprising a determination component configured to determine which locations associated with data in a database are within the identification boundary, based on a respective geospatial index for a respective location associated with data in the database.

12. The system according to claim 11, wherein the determination component is further configured to determine whether the respective geospatial index for the respective location is within a range defined by the identification boundary.

13. The system according to claim 12, wherein the range defined by the identification boundary is determined based on the subset of bits in the geospatial index for the given location.

14. The system according to claim 11, further comprising a confirmation component configure to determine that a location determined to be within the identification boundary based on the respective geospatial index, is within the search area using location values corresponding to the respective geospatial index.

15. The system according to claim 14, wherein the confirmation component is configured to obtain the location values corresponding to the respective geospatial index based on at least one of a lookup in the database and an inversion of the respective geospatial index to obtain a location pair.

25. The method according to claim 14, wherein the act of comparing includes an act of obtaining the location values corresponding to the respective geospatial index based on at least one of a lookup in the database and an inversion of the respective geospatial index to obtain a location pair.

16. A computer implemented method for optimizing processing of location-based requests, the method comprising act of:

accessing, by a computer system, multi-dimensioned location information associated with data in a database;

transforming, by the computer system, the multi-dimensioned location information into a single dimension geospatial index comprising a plurality of bits; and

identifying, by the computer system, data in the database having a location within a distance from a point of interest, wherein the act of identifying includes;

identifying a subset of bits from the plurality of bits in the geospatial index of the given location based on a magnitude of the distance, the subset of bits including the most significant bits of the geospatial index and having fewer bits than the geospatial index;

generating an identification boundary based on the identified subset of bits in the geospatial index; and

identifying locations within the distance from the point of interest based on the generated identification boundary.

17. The method according to claim 16, wherein the method further comprises an act of determining, by the computer system, that the identification boundary, at least, intersects with an outer bound of a search area defined by the point of interest and a distance threshold.

18. The method according to claim 16, further comprising an act of expanding the identification boundary until the identification boundary, at least, intersects with an outer bound of a search area defined by the point of interest and a distance threshold.

19. The method according to claim 16, wherein the act of generating an identification boundary from the subset of bits in the geospatial index includes-generating an identification geospatial index including the subset of bits which corresponds to an identification boundary with dimensions based, at least in part, on the length of the subset of bits.

20. The method according to claim 19, further comprising acts of:

inverting the identification geospatial index to obtain identification boundary coordinates; and

establishing the identification boundary on the identification boundary coordinates.

21. The method according to claim 16, wherein the act of identifying, by the computer system, data in the database having a location within a distance from a point of interest, includes determining which locations associated with data in a database are within the identification boundary, based on a respective geospatial index for a respective location.

22. The method according to claim 21, wherein the act of determining includes determining the respective geospatial index for the respective location is with a range defined by the identification boundary.

23. The method according to claim 22, wherein the method further comprises an act of determining the range based on the subset of bits in the geospatial index for the given location.

24. The method according to claim 21, wherein the act of identifying includes an act of comparing respective location values corresponding to the respective geospatial index to the given location to determine the respective location values are within the search area, wherein the respective location values are determined to be within the identification boundary based on the respective geospatial index.