Apparatus, systems, and methods for providing location information

• US 9,753,965 B2
• Filed: 03/14/2014
• Issued: 09/05/2017
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Foursquare Labs, Inc.
• Original Assignee: Factual Incorporated (Foursquare Labs, Inc.)
• Inventors: Rana, Ahad, Shimanovsky, Boris
• Primary Examiner(s): Zewdu, Meless
• Application Number:
  US14/214,296
• Publication Number:
  US 20140274154A1
• Time in Patent Office: 1,271 Days
• CPC Class Codes: G05B 13/0265 the criterion being a learning criterion
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/235 Update request formulation
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/2386 Bulk updating operations data conversion details G06F16/258
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 30/0261 based on user location
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products
• CPC Class Codes: G06Q 50/01 : Social networking
• CPC Class Codes: H04L 41/14 : Network analysis or design
• CPC Class Codes: H04W 16/00 : Network planning, e.g. coverage or traffic planning tools; Network deployment, e.g. resource partitioning or cells structures
• CPC Class Codes: H04W 16/24 : Cell structures
• CPC Class Codes: H04W 16/30 : Special cell shapes, e.g. doughnuts or ring cells
• CPC Class Codes: H04W 16/32 : Hierarchical cell structures
• CPC Class Codes: H04W 4/02 : Services making use of location information
• CPC Class Codes: H04W 4/021 : Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/025 : using location based information parameters
• CPC Class Codes: H04W 4/029 : Location-based management or tracking services
• CPC Class Codes: H04W 4/50 : Service provisioning or reconfiguring
• CPC Class Codes: H04W 64/00 : Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 64/003 : locating network equipment
• CPC Class Codes: H04W 76/38 : triggered by timers
• CPC Class Codes: H04W 8/08 : Mobility data transfer
• CPC Class Codes: H04W 8/16 : selectively restricting mobility data tracking
• CPC Class Codes: H04W 8/18 : Processing of user or subscriber data, e.g. subscribed services, user preferences or user profiles; Transfer of user or subscriber data
• CPC Class Codes: H04W 88/00 : Devices specially adapted for wireless communication networks, e.g. terminals, base stations or access point devices
• CPC Class Codes: H04W 88/02 : Terminal devices

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.

Claims

1. An apparatus comprising:

one or more interfaces configured to provide communication with a client device via a communication network;

a memory device to store a hierarchical index system of unique identifiers corresponding to sub-polygons in a region of interest; and

a processor, in communication with the one or more interfaces, to;

process a location query received from the client device, wherein the location query includes a location identifier associated with the client device;

determine a query identifier corresponding to the location identifier;

compare the query identifier with the index system to 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 the communication network;

wherein;

the unique identifiers and the query identifier include location identifiers based on a hierarchical encoding scheme, and

the processor is to;

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 and that the location identifier provided by the client device is within the region of interest, and

compare a first set of bits of the query location identifier, corresponding to a lower-precision sub-polygon, to the index system before comparing a second set of bits of the query location identifier, corresponding to a higher-precision sub-polygon.

2. The apparatus of claim 1, wherein the index system comprises an index tree, and in response to the first set of bits of the query identifier matches a first index of the index system corresponding to a leaf node of the index tree, the instructions are further executable by the processor to determine whether the query identifier is within the region of interest.

3. The apparatus of claim 1, wherein the processor is to:

process a polygon identifier associated with the query identifier and retrieved from the index system, determine a group identifier associated with the polygon identifier, and provide the service associated with the group identifier to the client device over the communication network.

4. The apparatus of claim 1, wherein the processor is to:

process a polygon identifier associated with the query identifier and retrieved from the index system, and initiate transmission of information associated with the polygon identifier to the client device over the communication network.

5. A method comprising:

process a location query received from a client device via a communication network, wherein the location query includes a location identifier associated with the client device;

determine a query identifier corresponding to the location identifier;

compare the query identifier with a hierarchical index system of unique identifiers corresponding to sub-polygons in a region of interest to determine that the location identifier provided by the client device is within the region of interest;

provide a service associated with the region of interest to the client device via the communication network;

compare one or more bits in the query identifier with bits in the index system to determine that the query identifier is represented in an index system and that the location identifier provided by the client device is within the region of interest; and

compare a first set of bits of the query location identifier, corresponding to a lower-precision sub-polygon, to the index system before comparing a second set of bits of the query location identifier, corresponding to a higher-precision sub-polygon;

wherein the unique identifiers and the query identifier include location identifiers based on a hierarchical encoding scheme.

6. The method of claim 5, wherein the index system comprises an index tree, and in response determining that the first set of bits of the query identifier matching a first index of the index system corresponding to a leaf node of the index tree, determining whether the query identifier is within the region of interest.

7. The method of claim 5, further comprising processing a polygon identifier associated with the query identifier and retrieved from the index system, determine a group identifier associated with the polygon identifier, and provide the service associated with the group identifier to the client device over the communication network.

8. The method of claim 5, further comprising processing a polygon identifier associated with the query identifier and retrieved from the index system, and initiating transmission of information associated with the polygon identifier to the client device over the communication network.

9. A non-transitory computer readable medium having instructions executable by a data processing apparatus to:

process a location query received from a client device via a communication network, wherein the location query includes a location identifier associated with the client device;

determine a query identifier corresponding to the location identifier;

compare the query identifier with a hierarchical index system of unique identifiers corresponding to sub-polygons in a region of interest to determine that the location identifier provided by the client device is within the region of interest;

initiate communication of a service associated with the region of interest to the client device via the communication network;

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 and that the location identifier provided by the client device is within the region of interest; and

compare a first set of bits of the query location identifier, corresponding to a lower-precision sub-polygon, to the index system before comparing a second set of bits of the query location identifier, corresponding to a higher-precision sub-polygon;

wherein the unique identifiers and the query identifier include location identifiers based on a hierarchical encoding scheme.

10. The non-transitory computer readable medium of claim 9, wherein the instructions are further executable by a data processing apparatus to:

determine whether the query identifier is within the region of interest in response to determining that the first set of bits of the query identifier matching a first index of the index system corresponding to a leaf node of an index tree, wherein the index system comprises an index tree.

11. The non-transitory computer readable medium of claim 9, wherein the instructions are further executable by a data processing apparatus to:

process a polygon identifier associated with the query identifier and retrieved from the index system,

determine a group identifier associated with the polygon identifier, and

initiate communication with provide the service associated with the group identifier to the client device over the communication network.

initiate transmission information associated with the polygon identifier to the client device over the communication network.

12. The non-transitory computer readable medium of claim 9, wherein the instructions are further executable by a data processing apparatus to:

process a polygon identifier associated with the query identifier and retrieved from the index system, and

initiate transmission of information associated with the polygon identifier to the client device over the communication network.