DBScholar

Back to papers

Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores

Summary: Rosetta: probabilistic range filter for LSM-tree KV stores; space-time optimized to reduce FPR. Hierarchical Bloom filters index all key prefixes; ranges map to multiple probes; workload-aware tuning; RocksDB integration; up to 40x faster range lookups and net performance gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h01e2076d4cb9119d
Venue
SIGMOD
Year
2020
Pagerank
8.1324472e-05
Overall Rank
2,667 | 82.13%
DOI
10.1145/3318464.3389731

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{luo_sigmod20,
        title = {{Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores}},
        author = {Luo, Siqiang and Chatterjee, Subarna and Ketsetsidis, Rafael and Dayan, Niv and Qin, Wilson and Idreos, Stratos},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389731},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389731},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 40 of 40 citing papers.

Rank Citing Paper Year Venue Pagerank
1,991 Chucky: A Succinct Cuckoo Filter for LSM-Tree 2021 SIGMOD 9.2264312e-05
2,780 Constructing and Analyzing the LSM Compaction Design Space 2021 VLDB 8.0073289e-05
2,844 SNARF: A Learning-Enhanced Range Filter 2022 VLDB 7.9291659e-05
3,489 Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine 2022 VLDB 7.2421958e-05
4,207 Proteus: A Self-Designing Range Filter 2022 SIGMOD 6.7226406e-05
4,706 Grafite: Taming Adversarial Queries with Optimal Range Filters 2024 SIGMOD 6.4426536e-05
4,771 GRF: A Global Range Filter for LSM-Trees with Shape Encoding 2024 SIGMOD 6.412225e-05
4,901 Oasis: An Optimal Disjoint Segmented Learned Range Filter 2024 VLDB 6.3483238e-05
5,046 Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems 2021 VLDB 6.2884087e-05
5,065 Dissecting, Designing, and Optimizing LSM-based Data Stores 2022 SIGMOD 6.2789973e-05
5,082 InfiniFilter: Expanding Filters to Infinity and Beyond 2023 SIGMOD 6.2679091e-05
5,272 Endure: A Robust Tuning Paradigm for LSM Trees Under Workload Uncertainty 2022 VLDB 6.1887235e-05
6,135 LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR 2024 SIGMOD 5.8584732e-05
6,137 Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads 2023 SIGMOD 5.8576977e-05
6,558 Memento Filter: A Fast, Dynamic, and Robust Range Filter 2024 SIGMOD 5.7292202e-05
6,889 Accelerating String-key Learned Index Structures via Memoization-based Incremental Training 2024 VLDB 5.6393954e-05
7,258 CaaS-LSM: Compaction-as-a-Service for LSM-based Key-Value Stores in Storage Disaggregated Infrastructure 2024 SIGMOD 5.5577384e-05
7,925 CAMAL: Optimizing LSM-trees via Active Learning 2024 SIGMOD 5.4086685e-05
7,959 Aleph Filter: To Infinity in Constant Time 2024 VLDB 5.4014706e-05
8,155 Diva: Dynamic Range Filter for Var-Length Keys and Queries 2025 VLDB 5.372731e-05
8,245 ArceKV: Towards Workload-driven LSM-compactions for Key-Value Store Under Dynamic Workloads 2026 VLDB 5.3556365e-05
8,342 How to Grow an LSM-tree? Towards Bridging the Gap Between Theory and Practice 2025 SIGMOD 5.3345258e-05
8,976 Practical Dynamic Extension for Sampling Indexes 2023 SIGMOD 5.2343756e-05
9,111 MirrorKV: An Efficient Key-Value Store on Hybrid Cloud Storage with Balanced Performance of Compaction and Querying 2023 SIGMOD 5.208561e-05
9,162 Rethinking The Compaction Policies in LSM-trees 2025 SIGMOD 5.2035666e-05
9,215 Structural Designs Meet Optimality: Exploring Optimized LSM-tree Structures in A Colossal Configuration Space 2024 SIGMOD 5.1921944e-05
9,270 TIGER: Training Inductive Graph Neural Network for Large-scale Knowledge Graph Reasoning 2024 VLDB 5.1860131e-05
9,678 Hourglass: An Adaptive Range Filter with Lightweight Hybrid Encoding 2026 SIGMOD 5.1258854e-05
9,681 Are Joins over LSM-trees Ready? Take RocksDB as an Example 2025 VLDB 5.1258854e-05
9,747 Disco: A Compact Index for LSM-trees 2025 SIGMOD 5.1177772e-05
10,073 LavaStore: ByteDance's Purpose-built, High-performance, Cost-effective Local Storage Engine for Cloud Services 2024 VLDB 5.0732737e-05
10,172 Optimizing Time Series Queries with Versions 2024 SIGMOD 5.0559291e-05
10,264 From FASTER to F2: Evolving Concurrent Key-Value Store Designs for Large Skewed Workloads 2025 VLDB 5.0380426e-05
10,434 A Multi-tenant Relational OLTP Database at Salesforce 2026 CIDR 4.9605343e-05
10,519 Dynamic Flat Filter: A Unified Framework for Scalable and Stable Fingerprint-Based Filters 2026 SIGMOD 4.9605343e-05
10,687 Aeris Filter: A Strongly and Monotonically Adaptive Range Filter 2026 SIGMOD 4.9605343e-05
10,724 Improving Range Scan Performance in LSM-trees with Group Caching 2026 SIGMOD 4.9605343e-05
10,730 Making LSM-Tree-based Key-Value Store Practical and Efficient for Multi-Tenant Serverless Cloud Databases 2026 SIGMOD 4.9605343e-05
10,985 Reaching the Pinnacle of TPC-DS: Co-design of Architecture, Executor, and Storage in TDSQL 2026 VLDB 4.9605343e-05
11,787 A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams 2023 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 26 of 26 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
238 LinkBench: a Database Benchmark Based on the Facebook Social Graph 2013 SIGMOD 0.00023594951
261 bLSM: A General Purpose Log Structured Merge Tree 2012 SIGMOD 0.00022862412
316 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021238056
402 Monkey: Optimal Navigable Key-Value Store 2017 SIGMOD 0.00019070605
438 Optimizing Space Amplification in RocksDB 2017 CIDR 0.00018259155
515 Tree Indexing on Solid State Drives 2010 VLDB 0.00016989841
761 Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging 2018 SIGMOD 0.00014191047
791 Don't Thrash: How to Cache Your Hash on Flash 2012 VLDB 0.00013927839
814 SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data 2017 VLDB 0.00013697533
860 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.00013382689
861 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013374869
923 AsterixDB: A Scalable, Open Source BDMS 2014 VLDB 0.00013034457
969 Incremental Organization for Data Recording and Warehousing 1997 VLDB 0.00012755618
1,310 Realtime Data Processing at Facebook 2016 SIGMOD 0.00011065568
1,429 The Log-Structured Merge-Bush & the Wacky Continuum 2019 SIGMOD 0.00010685393
1,900 Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn 2019 CIDR 9.3926585e-05
2,011 Pregelix: Big(ger) Graph Analytics on A Dataflow Engine 2015 VLDB 9.1800407e-05
2,905 Rose: Compressed, log-structured replication 2008 VLDB 7.871271e-05
3,012 Accordion: Better Memory Organization for LSM Key-Value Stores 2018 VLDB 7.7414696e-05
3,090 Persistent Data Sketching 2015 SIGMOD 7.6420011e-05
3,181 Answering Range Queries Under Local Differential Privacy 2019 VLDB 7.5427645e-05
4,738 Practical Private Range Search Revisited 2016 SIGMOD 6.4295783e-05
4,796 LogKV: Exploiting Key-Value Stores for Event Log Processing 2013 CIDR 6.3990791e-05
5,119 Persistent Bloom Filter: Membership Testing for the Entire History 2018 SIGMOD 6.2541554e-05
7,062 Coconut Palm: Static and Streaming Data Series Exploration Now in your Palm 2019 SIGMOD 5.593733e-05
7,411 GeckoFTL: Scalable Flash Translation Techniques For Very Large Flash Devices 2016 SIGMOD 5.5164757e-05
Previous Page 1 / 1 Next

Semantically Similar Papers