Grid-based geofence data indexing

Patent metadata

Field	Value
Publication number	US-11061984-B2
Application number	US-201916239764-A
Country	US
Kind code	B2
Filing date	Jan 4, 2019
Priority date	Nov 12, 2015
Publication date	Jul 13, 2021
Grant date	Jul 13, 2021

Abstract

One or more location updates from one or more user devices can be associated with one or more grid elements dividing a geographic area. Each location update corresponding to a set of user device data can be stored in a hashtable according to grid element. The hashtable can be resized based on the number of grid elements containing one or more sets of user device data. A set of grid elements can be determined to overlap a geofence, and zero or more sets of user device data can be retrieved from the hashtable corresponding to zero or more user devices located within the geofence.

First claim

What is claimed is:

1. A method comprising:
dividing, by a processor, a geographic area into a plurality of grid elements;
associating, by the processor, respective location updates from respective user devices located within the geographic area to a respective grid element to create a plurality of non-empty grid elements by:
receiving a respective location update from a respective user device;
appending the respective location update to a head of a list associated with a location of the respective user device; and
deleting, in response to the appending, an outdated location update from a tail of the list, wherein the outdated location update has a timestamp earlier than a current time minus a user device location update interval, minus a clock drift parameter, and minus a transmission latency parameter;

creating, by the processor, a hashtable storing non-empty grid elements of the plurality of non-empty grid elements, wherein a first non-empty grid element comprises a set of user device data for user devices located in the first non-empty grid element;
resizing, by the processor, the hashtable based on a total number of non-empty grid elements;
determining, by the processor, that the first non-empty grid element overlaps a geofence in the geographic area; and
retrieving, by the processor and from the hashtable, the set of user device data stored in the first non-empty grid element and corresponding to user devices located in the geofence.

2. The method of claim 1 , wherein resizing the hashtable based on the total number of non-empty grid elements further comprises resizing the hashtable to contain a number of keys equal to the total number of non-empty grid elements.

3. The method of claim 1 , wherein creating a hashtable further comprises creating a hashtable having a minimum number of keys equal to a square root of a number of grid elements in the plurality of grid elements and a maximal number of keys equal to the number of grid elements in the plurality of grid elements.

4. The method of claim 1 , wherein each grid element of the plurality of grid elements is equally sized.

5. The method of claim 1 , further comprising:
sending, based on retrieving the set of user device data, a message to a user device located within the geofence.

6. A system comprising:
a tangible memory storing instructions; and
a processor communicatively coupled to the tangible memory and configured to perform a method comprising:
dividing a geographic area into a plurality of grid elements;
associating respective location updates from respective user devices located within the geographic area to a respective grid element to create a plurality of non-empty grid elements by:
receiving a respective location update from a respective user device;
appending the respective location update to a head of a list associated with a location of the respective user device; and
deleting, in response to the appending, an outdated location update from a tail of the list, wherein the outdated location update has a timestamp earlier than a current time minus a user device location update interval, minus a clock drift parameter, and minus a transmission latency parameter;

creating a hashtable storing non-empty grid elements of the plurality of non-empty grid elements, wherein a first non-empty grid element comprises a set of user device data for user devices located in the first non-empty grid element;
resizing the hashtable based on a total number of non-empty grid elements;
determining that the first non-empty grid element overlaps a geofence in the geographic area; and
retrieving from the hashtable, the set of user device data stored in the first non-empty grid element and corresponding to user devices located in the geofence.

7. The system of claim 6 , wherein resizing the hashtable based on the total number of non-empty grid elements further comprises resizing the hashtable to contain a number of keys equal to the total number of non-empty grid elements.

8. The system of claim 6 , wherein creating a hashtable further comprises creating a hashtable having a minimum number of keys equal to a square root of a number of grid elements in the plurality of grid elements and a maximal number of keys equal to the number of grid elements in the plurality of grid elements.

9. The system of claim 6 , wherein each grid element of the plurality of grid elements is equally sized.

10. The system of claim 6 , the method further comprising:
sending, based on retrieving the set of user device data, a message to a user device located within the geofence.

11. A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising: dividing a geographic area into a plurality of grid elements; associating respective location updates from respective user devices located within the geographic area to a respective grid element to create a plurality of non-empty grid elements by: receiving a respective location update from a respective user device; appending the respective location update to a head of a list associated with a location of the respective user device; and deleting, in response to the appending, an outdated location update from a tail of the list, wherein the outdated location update has a timestamp earlier than a current time minus a user device location update interval, minus a clock drift parameter, and minus a transmission latency parameter; creating a hashtable storing non-empty grid elements of the plurality of non-empty grid elements, wherein a first non-empty grid element comprises a set of user device data for user devices located in the first non-empty grid element; resizing the hashtable based on a total number of non-empty grid elements; determining that the first non-empty grid element overlaps a geofence in the geographic area; and retrieving from the hashtable, the set of user device data stored in the first non-empty grid element and corresponding to user devices located in the geofence.

12. The computer program product of claim 11 , wherein resizing the hashtable based on the total number of non-empty grid elements further comprises resizing the hashtable to contain a number of keys equal to the total number of non-empty grid elements.

13. The computer program product of claim 11 , wherein creating a hashtable further comprises creating a hashtable having a minimum number of keys equal to a square root of a number of grid elements in the plurality of grid elements and a maximal number of keys equal to the number of grid elements in the plurality of grid elements.

14. The computer program product of claim 11 , wherein each grid element of the plurality of grid elements is equally sized.

15. The computer program product of claim 11 , the method further comprising:
sending, based on retrieving the set of user device data, a message to a user device located within the geofence.

Assignees

• IBM

Inventors

• Laventman Gennady
• Melamed Roie

Classifications

• H04W4/021

  Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences · CPC title

• H04W4/12

  Messaging; Mailboxes; Announcements · CPC title

• G06F16/29

  Geographical information databases · CPC title

• G06F16/9537 Primary

  Spatial or temporal dependent retrieval, e.g. spatiotemporal queries · CPC title

• G06F16/2255

  Hash tables · CPC title