Geo-temporal indexing and searching

Patent metadata

Field	Value
Publication number	US-9501507-B1
Application number	US-201213728879-A
Country	US
Kind code	B1
Filing date	Dec 27, 2012
Priority date	Dec 27, 2012
Publication date	Nov 22, 2016
Grant date	Nov 22, 2016

Abstract

A method and apparatus for a data analysis system for analyzing data object collections that include geo-temporal data is provided. One or more temporal granularities are specified for the purpose of generating a geo-temporal data index. The time granularities correspond to temporal ranges expected to correspond to temporal ranges specified in user queries against the data. One or more temporal index bucket groups are generated based on to the specified time granularities. Geo-temporal input data is indexed based on the generated temporal index bucket groups. The system allows a data analyst to specify geo-temporal queries that include both geospatial component and a temporal component. The system transforms geo-temporal queries into one or more second queries that retrieve data items based on the temporal index bucket groups.

First claim

What is claimed is:

1. A computer-implemented method for indexing data items that are associated with a geospatial component and a temporal component, the computer implemented method comprising:
receiving a data item that is associated with at least a geospatial component and a temporal time component;
generating, based on the geospatial component, an index key for indexing the data item in the geospatial index, wherein the index key is a Z-order curve value;
storing a reference to the data item in a geospatial index using the index key;
receiving index configuration data indicating a first time granularity, a second time granularity, and a third time granularity;
generating a first plurality of database index buckets for the first time granularity, a second plurality of database index buckets for the second time granularity, and a third plurality of database index buckets for the third time granularity;
storing, based on the time component, a second reference to the data item in a database index bucket of the first plurality, the second plurality, and the third plurality;
receiving a search query that comprises a second geospatial component and a second time component;
generating one or more second queries based on the second geospatial component and the second time component, wherein each of the second queries corresponds to a particular bucket of the first plurality, second plurality, or third plurality of database index buckets;
retrieving, for each particular bucket, one or more data items stored in the particular bucket;
wherein the method is performed by one or more computing devices.

2. The method of claim 1 , wherein the second time component comprises a time range.

3. The method of claim 1 , further comprising filtering one or more of the one or more data items retrieved by said second queries that are not in the time range specified by the search query.

4. The method of claim 1 , wherein the geospatial component comprises a Z-order geographic value.

5. The method of claim 1 , wherein the time component comprises a value representing a date and time.

6. The method of claim 1 , wherein the plurality of time granularities are specified by a user or based on requirements of a user-specified query.

7. The method of claim 1 , further comprising receiving one or more second data items that do not include a temporal component;
storing the one or more second data items in a non-temporal database index bucket.

8. A non-transitory computer-readable medium storing one or more sequences of instructions, which when executed by one or more processors, cause the one or more processors to carry out the steps of:
receiving a data item that is associated with at least a geospatial component and a time component;
generating, based on the geospatial component, an index key for indexing the data item in the geospatial index, wherein the index key is a Z-order curve value;
storing a reference to the data item in a geospatial index using the index key;
receiving index configuration data indicating at least a first time granularity, a second time granularity, and a third time granularity;
generating a first plurality of database index buckets for the first time granularity, a second plurality of database index buckets for the second time granularity, and a third plurality of database index buckets for the third time granularity;
storing, based on the time component, a second reference to the data item in a database index bucket of the first plurality, the second plurality, and the third plurality;
receiving a search query that comprises a second geospatial component and a second time component;
generating one or more second queries based on said second geospatial component and said second time component, wherein each of said second queries corresponds to a particular bucket of said first plurality, second plurality, or third plurality of database index buckets;
retrieving, for each particular bucket, one or more data items stored in the particular bucket;
wherein the method is performed by one or more computing devices.

9. The non-transitory computer readable medium of claim 8 , wherein said second time component comprises a time range.

10. The non-transitory computer readable medium of claim 8 , further comprising filtering one or more of the one or more data items retrieved by said second queries that are not in the time range specified by the search query.

11. The non-transitory computer readable medium of claim 8 , wherein the geospatial component comprises a Z-order geographic value.

12. The non-transitory computer readable medium of claim 8 , wherein said time component comprises a value representing a date and time.

13. The non-transitory computer readable medium of claim 8 , wherein said plurality of time granularities are specified by a user or based on requirements of a user-specified query.

14. The non-transitory computer readable medium of claim 8 ,
further comprising receiving one or more second data items;
storing a reference to said one or more second data items in a non-temporal database index bucket.

Assignees

• Palantir Technologies Inc
• Palantir Technologies Inc

Inventors

• Harris Michael
• Wang Jeff
• Prochnow Bobby

Classifications

• G06F17/30321 Primary

  Physics · mapped topic

• G06F16/2228 Primary

  Indexing structures · CPC title

• G06F16/2477

  Temporal data queries · CPC title

• G06F16/29

  Geographical information databases · CPC title

• G06F16/2255

  Hash tables · CPC title