Back to papers
Lightweight Cardinality Estimation in LSM-based Systems
Summary: Lightweight statistics for LSM stores; piggybacks on flush/merge to stay updated under high ingestion. Uses equi-width/equi-height histograms and wavelets for cardinality estimates, implemented on Apache AsterixDB with accuracy and overhead evaluation.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 5482
- Venue
- SIGMOD
- Year
- 2018
- Pagerank
- 5.4486922e-05
- Overall Rank
- 5,543 | 61.48%
- DOI
-
10.1145/3183713.3183761
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 12 of 12 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 4,835 |
MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions |
2019 |
SIGMOD |
5.8861112e-05 |
| 6,227 |
An LSM-based Tuple Compaction Framework for Apache AsterixDB |
2020 |
VLDB |
5.1408445e-05 |
| 6,394 |
Endure: A Robust Tuning Paradigm for LSM Trees Under Workload Uncertainty |
2022 |
VLDB |
5.0770427e-05 |
| 7,268 |
Comparing Synopsis Techniques for Approximate Spatial Data Analysis |
2019 |
VLDB |
4.7769096e-05 |
| 7,623 |
Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads |
2023 |
SIGMOD |
4.6890662e-05 |
| 8,011 |
CAMAL: Optimizing LSM-trees via Active Learning |
2024 |
SIGMOD |
4.6022693e-05 |
| 8,333 |
How to Grow an LSM-tree? Towards Bridging the Gap Between Theory and Practice |
2025 |
SIGMOD |
4.5390511e-05 |
| 8,804 |
ArceKV: Towards Workload-driven LSM-compactions for Key-Value Store Under Dynamic Workloads |
2026 |
VLDB |
4.4424232e-05 |
| 9,244 |
Determining Exact Quantiles with Randomized Summaries |
2024 |
SIGMOD |
4.3648789e-05 |
| 9,322 |
Are Joins over LSM-trees Ready? Take RocksDB as an Example |
2025 |
VLDB |
4.351469e-05 |
| 9,390 |
Rethinking The Compaction Policies in LSM-trees |
2025 |
SIGMOD |
4.341433e-05 |
| 10,399 |
Randomized Sketches for Quantile in LSM-tree based Store |
2025 |
SIGMOD |
4.1905499e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 24 of 24 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 1 |
Access Path Selection in a Relational Database Management System |
1979 |
SIGMOD |
0.0040465394 |
| 63 |
Improved Histograms for Selectivity Estimation of Range Predicates |
1996 |
SIGMOD |
0.00063595699 |
| 70 |
Hive - A Warehousing Solution Over a Map-Reduce Framework |
2009 |
VLDB |
0.00059744625 |
| 71 |
How Good Are Query Optimizers, Really? |
2016 |
VLDB |
0.00059446482 |
| 100 |
On the Propagation of Errors in the Size of Join Results |
1991 |
SIGMOD |
0.00050033475 |
| 126 |
Space-Efficient Online Computation of Quantile Summaries |
2001 |
SIGMOD |
0.00044753012 |
| 181 |
LEO - DB2's LEarning Optimizer |
2001 |
VLDB |
0.00036970794 |
| 223 |
Wavelet-Based Histograms for Selectivity Estimation |
1998 |
SIGMOD |
0.00032829841 |
| 328 |
Balancing Histogram Optimality and Practicality for Query Result Size Estimation |
1995 |
SIGMOD |
0.00027301497 |
| 344 |
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries |
2001 |
VLDB |
0.00026698826 |
| 369 |
Sequential Sampling Procedures For Query Size Estimation |
1992 |
SIGMOD |
0.00025502381 |
| 416 |
Approximate Query Processing Using Wavelets |
2000 |
VLDB |
0.00023773968 |
| 431 |
The Aqua Approximate Query Answering System |
1999 |
SIGMOD |
0.00023397171 |
| 454 |
An Overview of Query Optimization in Relational Systems |
1998 |
PODS |
0.00022796106 |
| 476 |
Impala: A Modern, Open-Source SQL Engine for Hadoop |
2015 |
CIDR |
0.00022216002 |
| 512 |
STHoles: A Multidimensional Workload-Aware Histogram |
2001 |
SIGMOD |
0.00021385343 |
| 527 |
Self-tuning Histograms: Building Histograms Without Looking at Data |
1999 |
SIGMOD |
0.00020862475 |
| 1,126 |
Dynamic Maintenance of Wavelet-Based Histograms |
2000 |
VLDB |
0.0001381102 |
| 1,437 |
AsterixDB: A Scalable, Open Source BDMS |
2014 |
VLDB |
0.00011973401 |
| 2,024 |
Storage Management in AsterixDB |
2014 |
VLDB |
9.7528344e-05 |
| 3,013 |
Cardinality Estimation Using Sample Views with Quality Assurance |
2007 |
SIGMOD |
7.7082045e-05 |
| 3,070 |
HAWQ: A Massively Parallel Processing SQL Engine in Hadoop |
2014 |
SIGMOD |
7.6157391e-05 |
| 5,269 |
SnappyData: A Hybrid Transactional Analytical Store Built On Spark |
2016 |
SIGMOD |
5.5926223e-05 |
| 7,414 |
Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g |
2008 |
SIGMOD |
4.7312542e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 3,797 |
Constructing and Analyzing the LSM Compaction Design Space |
2021 |
VLDB |
6.7552936e-05 |
| 8,727 |
Columnar Formats for Schemaless LSM-based Document Stores |
2022 |
VLDB |
4.4534547e-05 |
| 10,399 |
Randomized Sketches for Quantile in LSM-tree based Store |
2025 |
SIGMOD |
4.1905499e-05 |
| 7,217 |
Breaking Down Memory Walls in LSM-based Storage Systems |
2020 |
SIGMOD |
4.7936491e-05 |
| 5,801 |
Dissecting, Designing, and Optimizing LSM-based Data Stores |
2022 |
SIGMOD |
5.3217858e-05 |
| 11,358 |
Workload-Adaptive Filtering in Storage Engines |
2022 |
SIGMOD |
4.1905499e-05 |
| 5,920 |
Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems |
2021 |
VLDB |
5.2686888e-05 |
| 6,227 |
An LSM-based Tuple Compaction Framework for Apache AsterixDB |
2020 |
VLDB |
5.1408445e-05 |
| 4,920 |
On Performance Stability in LSM-based Storage Systems |
2020 |
VLDB |
5.8262404e-05 |
| 7,743 |
Efficient Data Ingestion and Query Processing for LSM-Based Storage Systems |
2019 |
VLDB |
4.6581858e-05 |