Back to results
US 10,242,116 B2Granted
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.
Claims19
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.
9 more elements
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.
14 more elements
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:
- divide a geographic area into a plurality of grid elements;
- associate one or more respective location updates from one or more respective user devices to a respective grid element to create one or more populated grid elements having at least one user device operating therein;
- create a hashtable comprising a plurality of keys, wherein at least one key is associated with respective sets of user device data corresponding to each respective populated grid element;
- resize the hashtable based on the one or more populated grid elements;
- determine an intersection between a geofence and one or more populated grid elements, wherein the geofence comprises a portion of the geographic area, by:
- determining one or more populated grid elements entirely contained within the geofence;
- and
- determining one or more populated grid elements having a first portion contained within the geofence and a second portion outside of the geofence;
- retrieve, based on determining an intersection between the geofence and the one or more populated grid elements, each respective set of user device data corresponding to 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 populated grid element of the one or more populated 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 populated grid element of the one or more populated grid elements having the first area contained within the geofence and the second area outside of the geofence.
9 more elements
Dependencies are inferred from the claim text.