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.
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