Back to papers
Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation
Summary: Column Sketches use lossy, fixed-width codes to map values, enabling predicate evaluation with most results from compressed data. Works across column/row/hybrid layouts and delivers gains: 3x-6x numeric, 2.7x categorical, and 1.4-4.8x vs prior accelerators.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 5558
- Venue
- SIGMOD
- Year
- 2018
- Pagerank
- 6.9178844e-05
- Overall Rank
- 3,611 | 74.91%
- DOI
-
10.1145/3183713.3196911
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 19 of 19 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 2,619 |
Decomposed Bounded Floats for Fast Compression and Queries |
2021 |
VLDB |
8.4427442e-05 |
| 2,868 |
Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations |
2019 |
SIGMOD |
7.9856878e-05 |
| 3,923 |
Pushing Data-Induced Predicates Through Joins in Big-Data Clusters |
2020 |
VLDB |
6.6232068e-05 |
| 4,157 |
Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput |
2019 |
VLDB |
6.3935343e-05 |
| 4,516 |
An Empirical Evaluation of Columnar Storage Formats |
2024 |
VLDB |
6.1146215e-05 |
| 5,316 |
Cuckoo Index: A Lightweight Secondary Index Structure |
2020 |
VLDB |
5.5688295e-05 |
| 5,571 |
A Deep Dive into Common Open Formats for Analytical DBMSs |
2023 |
VLDB |
5.4279553e-05 |
| 5,762 |
BinDex: A Two-Layered Index for Fast and Robust Scans |
2020 |
SIGMOD |
5.3367636e-05 |
| 6,971 |
Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses |
2024 |
SIGMOD |
4.8738633e-05 |
| 7,465 |
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees |
2025 |
SIGMOD |
4.7186055e-05 |
| 7,482 |
RTScan: Efficient Scan with Ray Tracing Cores |
2024 |
VLDB |
4.7135369e-05 |
| 7,837 |
CUBIT: Concurrent Updatable Bitmap Indexing |
2025 |
VLDB |
4.6342964e-05 |
| 8,221 |
Sieve: A Learned Data-Skipping Index for Data Analytics |
2023 |
VLDB |
4.5511941e-05 |
| 8,424 |
Tree-Encoded Bitmaps |
2020 |
SIGMOD |
4.5111681e-05 |
| 8,439 |
Cabin: a Compressed Adaptive Binned Scan Index |
2024 |
SIGMOD |
4.5058812e-05 |
| 8,499 |
Conditional Cuckoo Filters |
2021 |
SIGMOD |
4.4929219e-05 |
| 9,203 |
F3: The Open-Source Data File Format for the Future |
2026 |
SIGMOD |
4.3701616e-05 |
| 10,105 |
RABIT: Efficient Range Queries with Bitmap Indexing |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,179 |
LiveBin: A Localized and Version-Aware Binned Scan Index |
2026 |
SIGMOD |
4.1905499e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 22 of 22 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 121 |
Improved Query Performance with Variant Indexes |
1997 |
SIGMOD |
0.00045429472 |
| 132 |
Integrating Compression and Execution in Column-Oriented Database Systems |
2006 |
SIGMOD |
0.00043697853 |
| 167 |
The Snowflake Elastic Data Warehouse |
2016 |
SIGMOD |
0.00039408116 |
| 241 |
DB2 with BLU Acceleration: So Much More than Just a Column Store |
2013 |
VLDB |
0.00031314629 |
| 307 |
SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units |
2009 |
VLDB |
0.00028226342 |
| 310 |
The Vertica Analytic Database: C-Store 7 Years Later |
2012 |
VLDB |
0.0002815547 |
| 343 |
Implementing Database Operations Using SIMD Instructions |
2002 |
SIGMOD |
0.00026756534 |
| 367 |
Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing |
1998 |
VLDB |
0.00025518228 |
| 476 |
Impala: A Modern, Open-Source SQL Engine for Hadoop |
2015 |
CIDR |
0.00022216002 |
| 539 |
Shark: SQL and Rich Analytics at Scale |
2013 |
SIGMOD |
0.00020615453 |
| 959 |
Rethinking SIMD Vectorization for In-Memory Databases |
2015 |
SIGMOD |
0.00015034808 |
| 1,134 |
Dictionary-based Order-preserving String Compression for Main Memory Column Stores |
2009 |
SIGMOD |
0.00013751593 |
| 1,267 |
BitWeaving: Fast Scans for Main Memory Data Processing |
2013 |
SIGMOD |
0.00012917585 |
| 1,473 |
Fine-grained Partitioning for Aggressive Data Skipping |
2014 |
SIGMOD |
0.00011786148 |
| 1,622 |
Row-wise Parallel Predicate Evaluation |
2008 |
VLDB |
0.00011104582 |
| 1,993 |
Column Imprints: A Secondary Index Structure |
2013 |
SIGMOD |
9.8403548e-05 |
| 2,390 |
ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout |
2015 |
SIGMOD |
8.9006978e-05 |
| 2,442 |
Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries |
2008 |
VLDB |
8.8067249e-05 |
| 2,890 |
Database Compression on Graphics Processors |
2010 |
VLDB |
7.9586083e-05 |
| 4,160 |
Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? |
2017 |
SIGMOD |
6.3886736e-05 |
| 5,541 |
A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew |
2015 |
SIGMOD |
5.4501856e-05 |
| 6,807 |
Adaptive Data Skipping in Main-Memory Systems |
2016 |
SIGMOD |
4.915939e-05 |
Semantically Similar Papers