SYSTEM AND METHOD FOR DETERMINING EXACT LOCATION RESULTS USING HASH ENCODING OF MULTI-DIMENSIONED DATA

• US 20120226889A1
• Filed: 03/01/2011
• Published: 09/06/2012
• Est. Priority Date: 03/01/2011
• Status: Active Grant

• Current Assignee: MongoDB, Inc.
• Original Assignee: MongoDB, Inc.
• Inventors: Merriman, Dwight, Horowitz, Eliot
• Granted Patent: US 8,965,901 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• 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, wherein the system further comprises;

a hash component configured to generate a single dimension hash value from multi-dimension location inputs;

an access component 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;

an identification component 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 generate an identification boundary from a hash value of the given location, and wherein the identification component is further configured to 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 hash value 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 hash value.

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 value.

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 value.

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 output single value.

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

capture a prefix portion of the hash value of the given location;

generate an identification hash value, wherein the identification hash value includes the prefix portion; and

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

8. The system according to claim 7, wherein the hash component is further configured to invert the identification hash value 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 that the dimensions of the identification boundary, at least, intersect with the outer bound of the search area, in order to determine that the identification boundary, at least, intersects with an outer bound of the search area.

10. The system according to claim 9, wherein the identification component if further configured to calculate that a condition is true in order to determine 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 hash value 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 the respective hash value for the respective location is with 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 a prefix portion of the hash value 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 hash value, is within the search area using location values corresponding to the respective hash value.

15. The system according to claim 14, wherein the confirmation component is configured to obtain the location values corresponding to the respective hash values based on at least one of a lookup in the database and an inversion of the respective hash value 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 hash values based on at least one of a lookup in the database and an inversion of the respective hash value 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 hash values representative of a spatial distance; 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;

generating an identification boundary from a hash value of the point of interest, and

identifying locations within 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 a hash value of the point of interest includes:

capturing a prefix portion of the hash value of the given location;

generating an identification hash value including the prefix portion which corresponds to an identification boundary with dimensions based, at least in part, on the length of the prefix.

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

inverting the identification hash value 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 hash value for a respective location.

22. The method according to claim 21, wherein the act of determining includes determining the respective hash value 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 a prefix portion of the hash value 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 hash value 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 hash value.