Apparatus, systems, and methods for providing location information
First Claim
1. An apparatus comprising:
- a memory device to store an index system that identifies sub-polygons in a region of interest; 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;
process a location query received from a client device, wherein the location query includes a location identifier associated with the client device'"'"'s location;
determine a query identifier corresponding to the 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 the 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;
determine that the location identifier provided by the client device is within the region of interest; and
provide a service associated with the region of interest to the client device over a communication network after determining that the location identifier provided by the client device is within 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
20 Claims
-
1. An apparatus comprising:
-
a memory device to store an index system that identifies sub-polygons in a region of interest; 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; process a location query received from a client device, wherein the location query includes a location identifier associated with the client device'"'"'s location; determine a query identifier corresponding to the 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 the 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; determine that the location identifier provided by the client device is within the region of interest; and provide a service associated with the region of interest to the client device over a communication network after determining that the location identifier provided by the client device is within the region of interest. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer-implemented method comprising:
-
process a location query received from a client device, wherein the location query includes a location identifier associated with the client device'"'"'s location; determine a query identifier corresponding to the location identifier; compare one or more bits in the query identifier with bits in an index system that identifies sub-polygons in a region of interest 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 the 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; determine that the location identifier provided by the client device is within the region of interest; and provide a service associated with the region of interest to the client device over a communication network after determining that the location identifier provided by the client device is within the region of interest. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A non-transitory computer readable medium having instructions executable by a data processing apparatus to:
-
process a location query received from a client device, wherein the location query includes a location identifier associated with the client device'"'"'s location; determine a query identifier corresponding to the location identifier; compare one or more bits in the query identifier with bits in an index system that identifies sub-polygons in a region of interest 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 the 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; determine that the location identifier provided by the client device is within the region of interest; and provide a service associated with the region of interest to the client device over a communication network after determining that the location identifier provided by the client device is within the region of interest. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification