Physical vs. Logical Indexing with IDEA: Inverted Deduplication-Aware Index
summary
IDEA indexes the physical unique chunks instead of logical files, maps terms to unique chunks and maintains a chunk-to-file map, and modifies chunking to whitespace-align words so terms never split across chunks. Prototype integrates with Lucene and a deduplicating store, implements inline indexing, offsets and basic ranking, and shows up to 94% faster indexing, 73% smaller indexes, and up to 82% (single-term) / 59% (multi-term) lower term-lookup latency in the paper’s tests.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 2:50Keyword indexing in storage
- 4:20Indexing duplicated storage
- 6:52Physical vs logical indexing
- 10:46Whitespace align chunking
- 13:39Implementation with Deduplication and Lucine
- 18:00Evaluation methodology
- 21:12Lookup time results
- 23:00Advanced features
- 24:23Conclusion
related talks
31mUnspoken overhead of the Inverted Index
12mThe Dilemma between Deduplication and Locality: Can Both be Achieved?
53mIndexing Internals for Developers & DBAs
20mTiDedup: A New Distributed Deduplication Architecture for Ceph4
37mAlgorithms & data-structures that power Lucene & ElasticSearch- 53mIndexing Internals for Developers & DBAs
37mLearned Indexes: a New Idea for Efficient Data Access #bbuzz
05mExploring Data Deduplication in LSM Tree-based Key-Value Stores (Work-in-Progress Report)