Grid-based geofence data indexing

Patent metadata

Field	Value
Publication number	US-10242116-B2
Application number	US-201715650058-A
Country	US
Kind code	B2
Filing date	Jul 14, 2017
Priority date	Nov 12, 2015
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

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 a geographic area into a plurality of grid elements;
associating one or more respective location updates from one or more respective user devices located within the geographic area to a respective grid element to create one or more non-empty grid elements;
creating a hashtable storing each non-empty grid element, wherein each non-empty grid element comprises a respective set of user device data for each respective user device located in each respective non-empty grid element;
resizing the hashtable based on a total number of non-empty grid elements;
determining at least one non-empty grid element from the one or more non-empty grid elements which overlaps a geofence by:
determining one or more non-empty grid elements entirely contained within the geofence, wherein the geofence comprises an area overlapping the geographic area; and
determining one or more non-empty grid elements having a first portion contained by the geofence and a second portion outside of the geofence;

retrieving, from the hashtable, each respective set of user device data associated with each respective user device located in the geofence by:
retrieving, from the hashtable, each respective set of user device data associated with each respective user device located in each respective non-empty grid element of the one or more non-empty grid elements entirely contained within the geofence; and
retrieving, from the hashtable, each respective set of user device data associated with each respective user device located within the geofence and a non-empty grid element of the one or more non-empty grid elements having the first portion contained by the geofence and the second portion outside of the geofence.

2. The method of claim 1 , wherein resizing the hashtable based on a number of non-empty grid elements further comprises resizing the hashtable to contain a number of keys equal to the 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 the 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 associating one or more respective location updates from one or more respective user devices further comprises:
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, one or more outdated location updates from a tail of the list associated with the location of the respective user device.

5. The method of claim 4 , wherein deleting one or more outdated location updates from a tail of the list associated with the location of the respective user device further comprises:
determining a respective user device location update interval;
determining a respective clock drift parameter;
determining a respective transmission latency parameter; and
deleting one or more location updates having a timestamp earlier than a current time minus the respective user device location update interval, minus the respective clock drift parameter, and minus the respective transmission latency parameter.

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

7. The method of claim 1 , further comprising:
sending, based on retrieving each respective set of user device data, a message to at least one user device located within the geofence.

8. A system comprising:
a memory storing a geographic area, one or more geofence areas intersecting at least a portion of the geographic area, and one or more sets of user device data, wherein each respective set of user device data comprises at least a respective location of each respective user device;
a processor communicatively coupled to the memory and configured to compile user device location data and to identify user devices operating in the one or more geofence areas;
wherein, to compile user device location data, the processor is further configured to:
divide the geographic area into a plurality of grid elements;
associate each respective set of user device data to a respective grid element based on a respective location of each respective user device, wherein each respective grid element associated with one or more sets of user device data comprises a non-empty grid element;
create a hashtable storing each respective set of user device data and organized by non-empty grid element;
resize the hashtable based on a number of non-empty grid elements;

wherein, to identify user devices operating in the one or more geofence areas, the processor is further configured to:
retrieve a respective geofence area from the memory;
determine one or more non-empty grid elements intersecting, in whole or in part, the respective geofence area by:
determining one or more non-empty grid elements entirely contained within the geofence area; and
determining one or more non-empty grid elements having a first portion contained by the geofence area and a second portion outside of the geofence area;

retrieve, from the hashtable and based on the one or more non-empty grid elements intersecting the respective geofence area, a set of user device data associated with each respective user device located in the respective geofence area by:
retrieving, from the hashtable, each respective set of user device data associated with each respective user device located in each respective non-empty grid element of the one or more non-empty grid elements entirely contained within the geofence area; and
retrieving, from the hashtable, each respective set of user device data associated with each respective user device located within the geofence and a non-empty grid element of the one or more non-empty grid elements having the first portion contained within the geofence area and the second portion outside of the geofence area.

9. The system of claim 8 , wherein the processor configured to resize the hashtable based on a number of non-empty grid elements is further configured to resize the hashtable to contain a number of keys equal to the number of non-empty grid elements.

10. The system of claim 8 , wherein the processor configured to identify user devices operating in the one or more geofence areas is further configured to:
communicate a message to at least one of the user devices located in the respective geofence area.

11. The system of claim 8 , wherein the processor configured to associate each respective set of user device data to a respective grid element is further configured to:
append a respective location update to a head of a list associated with a location of a respective user device; and
delete, in response to appending a respective location update to a head of a list, one or more outdated location updates from a tail of the list.

12. The system of claim 11 , wherein the processor configured to delete one or more outdated location updates from the tail of the list is further configured to:
determine a respective user device location update interval;
determine a respective clock drift parameter;
determine a respective transmission latency parameter; and
delete one or more location updates having a timestamp earlier than a current time minus the respective user device location update interval, minus the respective clock drift parameter, and minus the respective transmission latency parameter.

13. The system of

Assignees

• IBM

Inventors

• Laventman Gennady
• Melamed Roie

Classifications

• H04W4/12

  Messaging; Mailboxes; Announcements · CPC title

• G06F17/3087 Primary

  Physics · mapped topic

• G06F17/30241

  Physics · mapped topic

• G06F17/3033

  Physics · mapped topic

• H04W4/021

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