System and method for large-scale and near-real-time search of mobile device locations in arbitrary geographical boundaries

• US 8,868,106 B2
• Filed: 02/29/2012
• Issued: 10/21/2014
• Est. Priority Date: 02/29/2012
• Status: Active Grant

• Current Assignee: Aeris Communications Inc.
• Original Assignee: Aeris Communications Inc.
• Inventors: Chen, Yixiang, Johnson, Drew S.
• Primary Examiner(s): Arevalo, Joseph
• Application Number:
  US13/408,748
• Publication Number:
  US 20130225201A1
• Time in Patent Office: 965 Days
• Field of Search: 455/450, 455/456.2, 455/410, 455/556.1, 455/411, 455/435.1, 455/551, 455/456.3
• US Class Current: 455/456.2
• CPC Class Codes: G01S 5/0295 Proximity-based methods, e.g. position inferred from reception of particular signals

Abstract

A system and method for generating a one-dimensional spatial index and a temporal index in relation to one or more two-dimensional location points of one or more mobile devices to enable near-real-time searching of devices having fast-changing location information is provided for. The present invention may be used in a variety of implementations including being used in conjunction with searching for mobile devices within a geographical area for a time period; finding nearby devices within a time period; tracking device movement within a time period; determining clusters of devices for identification and location across different geographical regions at once.

Claims

1. A method for searching for one or more mobile devices having location information in a searchable range within an arbitrary geographical boundary, the method comprising:

generating a referential index pair in relation to one or more location points of the one or more mobile devices, wherein generating further includes generating a one-dimensional spatial index and generating a temporal index, where generating a temporal index is performed using a location report processor which determines a location-by-time index value in relation to location information of the one or more mobile devices, wherein the location report processor executes;

receiving a location report having location information of the one or more devices;

calculating a z-value from a latitude and longitude of the received location information for at least one of the one or more mobile devices; and

calculating a time slot from a location timestamp associated with at least one of the one or more mobile devices.

2. The method of claim 1, wherein the calculated time slot is determined to be a value for a row key and each of the one or more mobile devices has device identification.

3. The method of claim 2 wherein the location report processor further executes:

calculating a column key by concatrnating the calculated z-valued and the device identification; and

calculating a column attribute by concatenating longitude, latitude, and location timestamp.

4. The method of claim 3, wherein the step of concatenating the calculated z-value and the device identification results in a Z-order index value.

5. The method of claim 3, wherein the location report processor further executes:

transmitting the row key, column key and the column attribute as the temporal index to a storage device.

6. The method of claim 5, wherein the step of generating a one-dimensional spatial index is performed using a query processor which determines a spatial index value in relation to location information of the one or more devices.

7. The method of claim 6, wherein the query processor executes:

receiving a query to devices in a geographical area during a specific time interval;

decomposing the geographical area into a plurality of bounding boxes and calculating a search range for each bounding box in the plurality;

calculating a plurality of time slots in the time interval; and

concurrently executing the steps of;

constructing a sub-query using a time slot of the plurality as a row key value and a lower and higher bounds of a search range as a column-key bounds value;

transmitting the sub-query to a storage device to retrieve one or more column attributes from the temporal index;

constructing a device identification to location map data structure with device identification as a key;

iterating through a returned result from the storage device to extract location and device identification; and

generating a number of device identification to location map results after completion of the concurrent execution steps; and

generating a main search result.

8. The method of claim 7, wherein the storage device is a storage engine.

9. The method of claim 8, wherein the storage engine stores column keys in a sorted order on a data storage device.

10. The method of claim 9, wherein the storage engine further translates row key and column key based lookups into one or more predetermined storage device operations.

11. A system for performing near-real-time searching to locate one or more mobile devices in arbitrary geographical boundaries having location information, comprising:

a query generator for constructing and executing parallel search segments;

a location report generator for generating a time index and a one dimensional spatial index; and

a storage engine for performing key translations, each in relation to one or more two-dimensional location points of the one or more mobile devices;

wherein the location report generator receives a location report having location information of the one or more mobile devices;

calculates a z-value from a latitude and longitude of the received location information for at least one of the one or more mobile devices;

calculates a column attribute by concatenating longitude, latitude, and location timestamp of the one or more mobile devices;

generates a time index to the storage engine; and

wherein the query generator receives a query to the one or more mobile devices in a geographical area during a specific time interval;

calculates a plurality of time slots in the time interval;

transmits sub-query to the storage engine to retrieve one or more column attributes from the time index;

generates a number of devices identification to location map results; and

generates a main search result.

12. The system of claim 11, wherein the location information of the one or more mobile devices is fast-changing.

13. A system for searching for a plurality of mobile devices having location information in a searchable range within an arbitrary geographical boundary, comprising:

a query generator for generating a one-dimensional spatial index, wherein the query generator determines a spatial index value in relation to location information and a location report generator for generating a time index which determines a location-by-time index value in relation to location information of the one or more mobile devices, wherein the location report generator is a processor executing;

receiving a location report having location information of the one or more devices;

calculating a z-value from a latitude and longitude of the received location information for at least one of the one or more devices;

calculating a time slot from a location timestamp associated with at least one of the one or more devices;

calculating a column key by concatenating the calculated z-value and the device identification;

calculating a column attribute by concatenating longitude, latitude, and location timestamp; and

sending the row key, column key and the column attribute as the time index to a storage device.

14. The system of claim 13, wherein the query generator is a processor executing:

receiving a query to devices in a geographical area during a specific time interval;

decomposing the geographical area into a plurality of bounding boxes and calculating a search range for each bounding box in the plurality;

calculating a plurality of time slots in the time interval; and

concurrently executing the steps of;

constructing a sub-query using a time slot of the plurality as a row key value and a lower and higher bounds of a search range as a column-key bounds value;

transmitting the sub-query to the storage device to retrieve one or more column attributes from the time index;

constructing a device identification to location map data structure with device identification as a key;

iterating through a returned result from the storage device to extract location and device identification;

generating a number of device identification to location map results after completion of the concurrent execution steps; and

generating a main search result.

15. A computer program product stored on a computer usable medium, comprising:

computer readable program means for causing a computer to perform near-real-time searching to locate one or more mobile devices in arbitrary geographical boundaries having changing location information by generating a one-dimensional spatial index using a query processor;

a temporal index using a location report processor, wherein the location report processor executes;

receiving a location report having location information of the one or more devices;

calculating a z-value from a latitude and longitude of the received location information for at least one of the one or more devices;

calculating a time slot from a location timestamp associated with at least one of the one or more devices;

calculating a column key by concatenating the calculated z-value and the device identification;

calculating a column attribute by concatenating longitude, latitude, and location timestamp; and

sending the row key, column key and the column attribute as the time index to a storage device; and

a storage engine performing key translations, each in relation to one or more two-dimensional location points of the one or more mobile devices.

16. The product of claim 15, wherein

the query processor executes:

receiving a query to devices in a geographical area during a specific time interval;

decomposing the geographical area into a plurality of bounding boxes and calculating a search range for each bounding box in the plurality;

calculating a plurality of time slots in the time interval;

concurrently executing the steps of;

constructing a sub-query using a time slot of the plurality as a row key value and a lower and higher bounds of a search range as a column-key bounds value;

transmitting the sub-query to the storage engine to retrieve one or more column attributes from the time index;

constructing a device identification to location map data structure with device identification as a key;

iterating through a returned result from the storage device to extract location and device identification;

generating a number of device identification to location map results after completion of the concurrent execution steps; and

generating a main search result; and

the storage engine stores column keys in a sorted order on a data storage device and further translates row key and column key based lookups into one or more predetermined storage device operations.