Organizing on-disk layout of index structures to support historical keyword search queries over temporally evolving data

1. A method, comprising:

organizing an on-disk corpus of multiple data index structures to support one or more queries over temporally evolving data, wherein the multiple data index structures comprise at least (i) a data item birth-time index, (ii) a data item death-time index, and (iii) an inverted index and/or postings list per keyword;

partitioning each of the multiple data index structures into (i) an active and/or latest state data partition and (ii) an archived data partition;

sub-partitioning each of the archived data partitions into multiple sub-partitions based on a lifespan of each item of the archived data;

executing a search query that includes (i) one or more temporal predicates and (ii) one or more keyword predicates across the on-disk corpus by:

pruning a collection of identified items of data from the on-disk corpus that contain the one or more keyword predicates using range metadata associated with the one or more temporal predicates to generate a pruned list of data items; and

performing a list intersection operation on at least (i) the data item birth-time index and (ii) the data item death-time index to generate a list of common data items from the pruned list of data items; and

retrieving the common data items from one or more of (i) the active and/or latest state data partitions and (ii) the archived data sub-partitions.

2. The method of claim 1 , wherein the multiple sub-partitions of the archived data are formed by partitioning a historic time-span encompassing the archived data into a logarithmic number of disjoint partitions comprising successive partitions catering to archived data items which have lifespan values existing within an exponentially increasing lifespan range.

3. The method of claim 1 , wherein said partitioning each of the multiple data index structures comprises placing each item of data in the on-disk corpus in exactly one partition.

4. The method of claim 1 , wherein the multiple archived data sub-partitions comprise a number of sub-partitions such that each of the multiple sub-partitions cover a lifespan range to match an expected lifespan distribution of the data in the on-disk corpus.

5. The method of claim 1 , wherein the range metadata associated with the one or more temporal predicates comprise a minimum data item identifier and a maximum data item identifier, wherein data item identifiers are assigned within the on-disk corpus in increasing order of birth-time of the data item and/or in increasing order of death-time of the data item.

6. The method of claim 1 , comprising:

maintaining the inverted index and/or postings list for each distinct item of data in the on-disk corpus, wherein the inverted index and/or postings list of a given item of data contains a list of one or more record identifiers associated with document versions that contain the given item of data.

7. The method of claim 1 , wherein said partitioning each of the multiple data index structures comprises forming the partitions around successive levels of an interval tree, wherein the interval tree comprises a data-structure used to represent data item lifespans.

8. The method of claim 1 , wherein the lifespan of each item of the archived data comprises an exact lifespan.

9. The method of claim 1 , wherein the lifespan of each item of the archived data comprises an approximate lifespan.

10. A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computing device to cause the computing device to:

organize an on-disk corpus of multiple data index structures to support one or more queries over temporally evolving data, wherein the multiple data index structures comprise at least (i) a data item birth-time index, (ii) a data item death-time index, and (iii) an inverted index and/or postings list per keyword;

partition each of the multiple data index structures into (i) an active and/or latest state data partition and (ii) an archived data partition;

sub-partition each of the archived data partitions into multiple sub-partitions based on a lifespan of each item of the archived data;

execute a search query that includes (i) one or more temporal predicates and (ii) one or more keyword predicates across the on-disk corpus by:

pruning a collection of identified items of data from the on-disk corpus that contain the one or more keyword predicates using range metadata associated with the one or more temporal predicates to generate a pruned list of data items; and

performing a list intersection operation on at least (i) the data item birth-time index and (ii) the data item death-time index to generate a list of common data items from the pruned list of data items; and

retrieve the common data items from one or more of (i) the active and/or latest state data partitions and (ii) the archived data sub-partitions.

11. The computer program product of claim 10 , wherein the multiple sub-partitions of the archived data are formed by partitioning a historic time-span encompassing the archived data into a logarithmic number of disjoint partitions comprising successive partitions catering to archived data items which have lifespan values existing within an exponentially increasing lifespan range.

12. The computer program product of claim 10 , wherein the lifespan of each item of the archived data comprises an exact lifespan.

13. The computer program product of claim 10 , wherein the lifespan of each item of the archived data comprises an approximate lifespan.

14. A system comprising:

a memory; and

at least one processor coupled to the memory and configured for:

organizing an on-disk corpus of multiple data index structures to support one or more queries over temporally evolving data, wherein the multiple data index structures comprise at least (i) a data item birth-time index, (ii) a data item death-time index, and (iii) an inverted index and/or postings list per keyword;

partitioning each of the multiple data index structures into (i) an active and/or latest state data partition and (ii) an archived data partition;

sub-partitioning each of the archived data partitions into multiple sub-partitions based on a lifespan of each item of the archived data;

executing a search query that includes (i) one or more temporal predicates and (ii) one or more keyword predicates across the on-disk corpus by:

pruning a collection of identified items of data from the on-disk corpus that contain the one or more keyword predicates using range metadata associated with the one or more temporal predicates to generate a pruned list of data items; and

performing a list intersection operation on at least (i) the data item birth-time index and (ii) the data item death-time index to generate a list of common data items from the pruned list of data items; and

retrieving the common data items from one or more of (i) the active and/or latest state data partitions and (ii) the archived data sub-partitions.

15. The system of claim 14 , wherein the multiple sub-partitions of the archived data are formed by partitioning a historic time-span encompassing the archived data into a logarithmic number of disjoint partitions comprising successive partitions catering to archived data items which have lifespan values existing within an exponentially increasing lifespan range.

16. The system of claim 14 , wherein the lifespan of each item of the archived data comprises an exact lifespan.

17. The system of claim 14 , wherein the lifespan of each item of the archived data comprises an approximate lifespan.