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

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.