Geo-temporal indexing and searching

Patent metadata

Field	Value
Publication number	US-10691662-B1
Application number	US-201615358002-A
Country	US
Kind code	B1
Filing date	Nov 21, 2016
Priority date	Dec 27, 2012
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

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 time component, the computer-implemented method comprising:
receiving a data item that is associated with at least a geospatial component and a time component;
storing a reference to the data item in a geospatial index based on the geospatial component;
receiving time 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 request comprising at least a second time component;
generating at least two search queries using the second time component retrieving one or more data items using the at least two search queries;
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 2 , further comprising filtering one or more of the one or more data items retrieved by the two search queries that are not in the time range specified by the search request.

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 first time granularity, the second time granularity, and the third time granularity are specified by a user or based on requirements of a user-specified query.

7. The method of claim 1 , wherein the first time granularity, the second time granularity, and the third time granularity are one of seconds, minutes, hours, days, months, years, decades, centuries.

8. The method of claim 1 , wherein each of the first plurality of database index buckets is identified by a hash value.

9. 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;
storing a reference to the data item in a geospatial index based on the geospatial component;
receiving time 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 request comprising at least a second time component;
generating at least two search queries using the second time component;
retrieving one or more data items using the at least two search queries.

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

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

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

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

14. The non-transitory computer readable medium of claim 9 , wherein the first time granularity, the second time granularity, and the third time granularity are specified by a user or based on requirements of a user-specified query.

15. The non-transitory computer readable medium of claim 9 , wherein the first time granularity, the second time granularity, and the third time granularity are one of seconds, minutes, hours, years, decades, centuries.

16. The non-transitory computer readable medium of claim 9 , wherein each of the first plurality of database index buckets is identified by a hash value.

Assignees

• Palantir Technologies Inc

Inventors

• Harris Michael
• Wang Jeff
• Prochnow Bobby

Classifications

• G06F16/2477

  Temporal data queries · CPC title

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F16/2228 Primary

  Indexing structures · CPC title

• G06F16/29

  Geographical information databases · CPC title