Grid-based geofence data indexing
AssigneeInternational Business Machines Corporation
InventorsGennady Laventman, Roie Melamed
Life of this patent
Estimating the term…
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.
Claims15
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.
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.
A computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, 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.
Dependencies are inferred from the claim text.