Temporal index sharding for space-time efficiency in archive search

Avishek Anand, Srikanta J. Bedathur, Klaus Berberich, Ralf Schenkel

Abstract

This paper introduces Temporal Index Sharding, a novel approach to organizing web archives for "time-travel" keyword searches. While traditional "slicing" methods partition indexes by time—leading to 200-300% index growth due to document replication—sharding partitions indexes horizontally by document ID. This method achieves superior query speeds with negligible space overhead by optimizing for physical disk seek costs and maintaining a "Staircase Property" to minimize wasteful reads.

1. Introduction

As web archives and wikis grow, the demand for "time-travel queries"—keyword searches restricted to specific historical intervals—has increased. Standard inverted indexes are typically optimized for the latest version of a document. To handle historical data, previous research utilized Slicing, which partitions the index into time-based chunks. However, if a document version remains unchanged over a long period, it overlaps multiple slices and must be replicated, causing significant "index blowup."

2. Methodology: From Slicing to Sharding

The core innovation of this work is "rotating the knife" by 90 degrees. Instead of slicing vertically by time, the authors propose sharding horizontally by document ID.

Comparison of Slicing (vertical partitioning by time) vs. Sharding (horizontal partitioning by document ID).

2.1 The Staircase Property

To prevent "wasteful reads" (loading data that doesn't match the query's time constraint), the authors define the Staircase Property. A shard satisfies this property if no document version within it completely "subsumes" (starts before and ends after) another. A greedy algorithm is employed to create the minimum number of shards necessary to maintain this property.

2.2 Cost-Aware Merging

While idealized sharding prevents wasted reads, too many shards increase random disk seeks, which degrades performance. The authors introduced a cost model based on the ratio of random access cost ($C_r$) to sequential read cost ($C_s$). This allows for a heuristic merging of shards, accepting minor sequential read overhead to avoid the high penalty of random seeks. Additionally, each shard utilizes a small in-memory "impact list" to act as a bookmark for efficient entry points.

3. Experimental Evaluation

The approach was evaluated on two massive datasets: the full revision history of English Wikipedia (WIKI, ~700 GB) and weekly crawls of U.K. government websites (UKGOV, ~400 GB).

3.1 Key Results

  • Space Efficiency: Slicing methods caused index growth of 50% to 200%. In contrast, Sharding resulted in a negligible ~1% increase in index size, primarily due to small in-memory impact lists.
  • Query Speed: Sharding consistently outperformed sliced indexes. On the UKGOV dataset, sharding was nearly 2x faster for day-granularity queries.
  • Robustness: The advantage of sharding was most pronounced for long time intervals, where slicing methods struggle with redundant data.

4. Discussion and Future Work

The "Knife Rotation" insight demonstrates that partitioning by document ID avoids the replication inherent in time-based partitioning. By treating subsumption as the primary efficiency killer and optimizing for hardware-specific costs, the index can be tuned for various storage media (SSD vs. HDD).

Future work includes addressing the complexity of updating sharded indexes as new crawls arrive and exploring large-scale distributed implementations on platforms like Hadoop. Additionally, the sensitivity of sharding to "Temporal Coalescing" (merging similar versions) remains an area for further investigation, as compression can alter the distribution of time intervals.

Summary updated

Abstract

Time-travel queries that couple temporal constraints with keyword queries are useful in searching large-scale archives of time-evolving content such as the web archives or wikis. Typical approaches for efficient evaluation of these queries involve slicing either the entire collection [20] or individual index lists [10] along the time-axis. Both these methods are not satisfactory since they sacrifice compactness of index for processing efficiency making them either too big or, otherwise, too slow. We present a novel index organization scheme that shards each index list with almost zero increase in index size but still minimizes the cost of reading index entries during query processing. Based on the optimal sharding thus btained, we develop a practically efficient sharding that takes into account the different costs of random and sequential accesses. Our algorithm merges shards from the optimal solution to allow for a few extra sequential accesses while gaining significantly by reducing the number of random accesses. We empirically establish the effectiveness of our sharding scheme with experiments over the revision history of the English Wikipedia between 2001-2005 (approx 700 GB) and an archive of U.K. governmental web sites (approx 400 GB). Our results demonstrate the feasibility of faster time-travel query processing with no space overhead.
BibTeX
@inproceedings{anand2011temporal,
  author = {Avishek Anand and Srikanta J. Bedathur and Klaus Berberich and Ralf Schenkel},
  title = {{Temporal index sharding for space-time efficiency in archive search}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2011},
  doi = {10.1145/2009916.2009991},
}

Loading related content...

Figure