APPARATUS, SYSTEMS, AND METHODS FOR PROVIDING LOCATION INFORMATION

• US 20140274154A1
• Filed: 03/14/2014
• Published: 09/18/2014
• 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
• Granted Patent: US 9,753,965 B2
• Time in Patent Office: Days
• US Class Current: 455/456.3
• 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:

a processor configured to run one or more modules stored in memory, wherein the one or more modules are configured to;

receive one or more polygons associated with a region of interest;

determine a plurality of sub-polygons that are contained within the one or more polygons, wherein each of the sub-polygons is associated with a unique code; and

generate a first index system based on at least a subset of the plurality of sub-polygons, thereby providing an efficient mechanism to determine whether a particular location is within the region of interest.

2. The apparatus of claim 1, wherein the unique code includes a location identifier based on a hierarchical encoding scheme.

3. The apparatus of claim 1, wherein the index system includes one of a hash table or a probabilistic data structure.

4. The apparatus of claim 1, wherein the one or more modules are further configured to:

determine a difference between the index system and a previously-generated index system; and

provide the difference to a computing device to update the previously-generated index system in the computing device.

5. The apparatus of claim 1, wherein the one or more modules are further configured to identify a tree structure that models the unique code of the plurality of sub-polygons based on a hierarchy of the unique codes and generate the first index system based on the tree structure.

6. The apparatus of claim 5, wherein the tree structure includes a branch node and a leaf node, and the branch node is associated with a geographic area that is larger than that of the leaf node, and wherein the one or more modules are configured to generate indices for the index system by traversing the tree structure from the branch node to the leaf node.

7. The apparatus of claim 5, wherein the one or more modules are further configured to:

determine a list of polygons that includes a particular sub-polygon, and

associate the list of polygons with a leaf node of the tree structure corresponding to the particular sub-polygon.

8. The apparatus of claim 5, wherein the one or more modules are further configured to merge the tree structure, corresponding to the region of interest, with a second tree structure corresponding to a second region of interest, thereby providing a single index system modeling both the tree structure and the second tree structure.

9. The apparatus of claim 1, wherein the one or more modules are further configured to remove one or more sub-polygons corresponding to a particular polygon from the index system.

10. The apparatus of claim 1, wherein the one or more modules are further configured to remove one or more sub-polygons from the plurality of sub-polygons to provide a reduced set of sub-polygons and generate the index system from the reduced set of sub-polygons, thereby reducing the size of the index system.

11. The apparatus of claim 1, wherein the one or more modules are further configured to receive a second index system from another computing device and to merge the first index system and the second index system by considering an overlap of sub-polygons corresponding to the first index system and the second index system.

12. The apparatus of claim 1, wherein the one or more modules are further configured to provide the index system to a computing device so that the computing device can use the index system to serve location queries.

13. A method for providing an index system for a region of interest, the method comprising:

receiving, at an index generation module of a computing system, one or more polygons associated with the region of interest;

determining, at the index generation module, a plurality of sub-polygons that are contained within the one or more polygons, wherein each of the sub-polygons is associated with a unique code;

generating, at the index generation module, a first index system based on at least a subset of the plurality of sub-polygons, thereby providing an efficient mechanism to determine whether a particular location is within the region of interest.

14. The method of claim 13, wherein the index system includes one of a hash table or a probabilistic data structure.

15. The method of claim 13, further comprising:

determining, by the index generation module, a difference between the index system and a previously-generated index system; and

providing, by the index generation module, the difference to a computing device to update the previously-generated index system in the computing device.

16. The method of claim 13, further comprising identifying a tree structure that models the unique code of the plurality of sub-polygons based on a hierarchy of the unique codes and generate the first index system based on the tree structure.

17. The method of claim 16, wherein the tree structure includes a branch node and a leaf node, and the branch node is associated with a geographic area that is larger than that of the leaf node, and wherein the method further comprises generating, at the index generation module, indices for the index system by traversing the tree structure from the branch node to the leaf node.

18. The method of claim 16, further comprising merging the tree structure, corresponding to the region of interest, with a second tree structure corresponding to a second region of interest, thereby providing a single index system modeling both the tree structure and the second tree structure.

19. The method of claim 13, further comprising receiving a second index system from another computing device and merging the first index system and the second index system by considering an overlap of sub-polygons corresponding to the first index system and the second index system.

20. The method of claim 13, further comprising providing the index system to a computing device so that the computing device can use the index system to serve location queries.

21. A non-transitory computer readable medium having executable instructions operable to cause a data processing apparatus to:

receive one or more polygons associated with a region of interest;

determine a plurality of sub-polygons that are contained within the one or more polygons, wherein each of the sub-polygons is associated with a unique code; and

generate a first index system based on the tree structure, thereby providing an efficient mechanism to search whether a particular location is within the region of interest.

22. The computer readable medium of claim 21, wherein the index system includes one of a hash table or a probabilistic data structure.

23. The computer readable medium of claim 21, wherein the executable instructions are further operable to cause the data processing apparatus to:

determine a difference between the index system and a previously-generated index system; and

provide the difference to a computing device to update the previously-generated index system in the computing device.

24. The computer readable medium of claim 21, wherein the executable instructions are further operable to cause the data processing apparatus to identify a tree structure that models the unique code of the plurality of sub-polygons based on a hierarchy of the unique codes and generate the first index system based on the tree structure.

25. The computer readable medium of claim 24, wherein the tree structure includes a branch node and a leaf node, and the branch node is associated with a geographic area that is larger than that of the leaf node, and wherein the method further comprises generating, at the index generation module, indices for the index system by traversing the tree structure from the branch node to the leaf node.

26. The computer readable medium of claim 21, wherein the executable instructions are further operable to cause the data processing apparatus to merge the tree structure, corresponding to the region of interest, with a second tree structure corresponding to a second region of interest, thereby providing a single index system modeling both the tree structure and the second tree structure.

27. The computer readable medium of claim 21, wherein the executable instructions are further operable to cause the data processing apparatus to receive a second index system from another computing device and merge the first index system and the second index system by considering an overlap of sub-polygons corresponding to the first index system and the second index system.

28. An apparatus comprising:

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

a memory device that is configured to maintain 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, and configured to run one or more modules that are configured to;

receive a location query 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.

29. The apparatus of claim 28, wherein the unique identifiers and the query identifier include location identifiers based on a hierarchical encoding scheme.

30. The apparatus of claim 29, wherein the one or more modules are configured 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

31. The apparatus of claim 30, wherein the one or more modules are configured to 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.

32. The apparatus of claim 31, wherein the index system comprises an index tree, when 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 one or more modules that are configured to determine that the query identifier is within the region of interest.

33. The apparatus of claim 28, wherein the one or more modules are configured to retrieve, from the index system, a polygon identifier associated with the query identifier, 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.

34. The apparatus of claim 28, wherein the one or more modules are configured to retrieve, from the index system, a polygon identifier associated with the query identifier, and provide data associated with the polygon identifier to the client device over the communication network.