System and method for determining exact location results using hash encoding of multi-dimensioned data
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
25 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 25)
-
-
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. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24)
-
Specification