Geo-temporal indexing and searching

• US 10,691,662 B1
• Filed: 11/21/2016
• Issued: 06/23/2020
• Est. Priority Date: 12/27/2012
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Harris, Michael, Wang, Jeff, Prochnow, Bobby
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US15/358,002
• Time in Patent Office: 1,310 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/29 Geographical information databases

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.

Claims

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.