Apparatus, systems, and methods for providing location information
First Claim
1. An apparatus comprising:
- a memory device to store a master index system that identifies sub-polygons in a geographical region; and
a processor and non-volatile memory comprising a set of computer-readable instructions, wherein the processor is configured to execute the computer readable instructions to;
identify a region of interest associated with a target location determined from a location identifier;
retrieve from the master index system an index system corresponding to the identified region of interest;
determine a query identifier corresponding to a location identifier;
compare one or more bits in the query identifier with bits in the index system to determine that the query identifier is represented in the index system, wherein the step of comparing includes;
comparing a first set of bits of the one or more bits in the query identifier, corresponding to a lower-precision sub-polygon, to the bits in the index system, corresponding to sub-polygons in the region of interest;
comparing a second set of bits of the one or more bits in the query identifier, corresponding to a higher-precision sub-polygon, to the bits in the index system, corresponding to the sub-polygons in the region of interest; and
determine whether the target location corresponds to one or more of the sub-polygons within the region of interest,wherein the master index system comprises a plurality of index systems of unique identifiers corresponding to the sub-polygons of the region of interest.
5 Assignments
0 Petitions
Accused Products
Abstract
The disclosed apparatus, systems, and methods relate to a location query mechanism that can efficiently determine whether a target entity is located within a region of interest (ROI). At a high level, the location query mechanism can be configured to represent a ROI using one or more polygons. The location query mechanism can, in turn, divide (e.g., tessellate) the one or more polygons into sub-polygons. Subsequently, the location query mechanism can use the sub-polygons to build an index system that can efficiently determine whether a particular location is within any of the sub-polygons. Therefore, when a computing device queries whether a particular location is within the region of interest, the location query mechanism can use the index system to determine whether the particular location is within any of the sub-polygons.
-
Citations
26 Claims
-
1. An apparatus comprising:
-
a memory device to store a master index system that identifies sub-polygons in a geographical region; and a processor and non-volatile memory comprising a set of computer-readable instructions, wherein the processor is configured to execute the computer readable instructions to; identify a region of interest associated with a target location determined from a location identifier; retrieve from the master index system an index system corresponding to the identified region of interest; determine a query identifier corresponding to a location identifier; compare one or more bits in the query identifier with bits in the index system to determine that the query identifier is represented in the index system, wherein the step of comparing includes; comparing a first set of bits of the one or more bits in the query identifier, corresponding to a lower-precision sub-polygon, to the bits in the index system, corresponding to sub-polygons in the region of interest; comparing a second set of bits of the one or more bits in the query identifier, corresponding to a higher-precision sub-polygon, to the bits in the index system, corresponding to the sub-polygons in the region of interest; and determine whether the target location corresponds to one or more of the sub-polygons within the region of interest, wherein the master index system comprises a plurality of index systems of unique identifiers corresponding to the sub-polygons of the region of interest. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer-implemented method comprising:
-
identifying a region of interest associated with a target location determined from a location identifier; retrieving from a master index system that identifies sub-polygons in a geographical region, an index system corresponding to the identified region of interest; determining a query identifier corresponding to the location identifier; comparing one or more bits in the query identifier with bits in the index system to determine that the query identifier is represented in the index system, wherein the step of comparing includes; comparing a first set of bits of the one or more bits in the query identifier, corresponding to a lower-precision sub-polygon, to the bits in the index system, corresponding sub-polygons in the region of interest; comparing a second set of bits of the one or more bits in the query identifier, corresponding to a higher-precision sub-polygon, to the bits in the index system, corresponding the sub-polygons in the region of interest; and determining whether the target location corresponds to one or more of the sub-polygons within the region of interest, wherein the master index system comprises a plurality of index systems of unique identifiers corresponding to the sub-polygons of the region of interest. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A non-transitory computer readable medium having instructions executable by a data processing apparatus to:
-
identify a region of interest associated with a target location determined from a location identifier; retrieve from a master index system that identifies sub-polygons in a geographical region, an index system corresponding to the identified region of interest; determine a query identifier corresponding to a location identifier; compare one or more bits in the query identifier with bits in the index system to determine that the query identifier is represented in the index system, wherein the step of comparing includes; comparing a first set of bits of the one or more bits in the query identifier, corresponding to a lower-precision sub-polygon, to the bits in the index system, corresponding to sub-polygons in the region of interest; comparing a second set of bits of the one or more bits in the query identifier, corresponding to a higher-precision sub-polygon, to the bits in the index system, corresponding to the sub-polygons in the region of interest; and determine whether the target location corresponds to one or more of the sub-polygons within the region of interest, wherein the master index system comprises a plurality of index systems of unique identifiers corresponding to the sub-polygons of the region of interest. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26)
-
Specification