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
- 5557
- Venue
- SIGMOD
- Year
- 2018
- Pagerank
- 6.924272e-05
- Overall Rank
- 3,608 | 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,613 |
Decomposed Bounded Floats for Fast Compression and Queries |
2021 |
VLDB |
8.4503824e-05 |
| 2,865 |
Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations |
2019 |
SIGMOD |
7.9862595e-05 |
| 3,922 |
Pushing Data-Induced Predicates Through Joins in Big-Data Clusters |
2020 |
VLDB |
6.6291079e-05 |
| 4,158 |
Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput |
2019 |
VLDB |
6.3994318e-05 |
| 4,514 |
An Empirical Evaluation of Columnar Storage Formats |
2024 |
VLDB |
6.1204636e-05 |
| 5,315 |
Cuckoo Index: A Lightweight Secondary Index Structure |
2020 |
VLDB |
5.5723424e-05 |
| 5,562 |
A Deep Dive into Common Open Formats for Analytical DBMSs |
2023 |
VLDB |
5.4331334e-05 |
| 5,749 |
BinDex: A Two-Layered Index for Fast and Robust Scans |
2020 |
SIGMOD |
5.3418923e-05 |
| 6,972 |
Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses |
2024 |
SIGMOD |
4.8785237e-05 |
| 7,467 |
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees |
2025 |
SIGMOD |
4.7218691e-05 |
| 7,483 |
RTScan: Efficient Scan with Ray Tracing Cores |
2024 |
VLDB |
4.7180617e-05 |
| 7,831 |
CUBIT: Concurrent Updatable Bitmap Indexing |
2025 |
VLDB |
4.6387445e-05 |
| 8,222 |
Sieve: A Learned Data-Skipping Index for Data Analytics |
2023 |
VLDB |
4.5555621e-05 |
| 8,430 |
Tree-Encoded Bitmaps |
2020 |
SIGMOD |
4.5154973e-05 |
| 8,447 |
Cabin: a Compressed Adaptive Binned Scan Index |
2024 |
SIGMOD |
4.5102052e-05 |
| 8,502 |
Conditional Cuckoo Filters |
2021 |
SIGMOD |
4.4972336e-05 |
| 9,201 |
F3: The Open-Source Data File Format for the Future |
2026 |
SIGMOD |
4.3743539e-05 |
| 10,105 |
RABIT: Efficient Range Queries with Bitmap Indexing |
2026 |
SIGMOD |
4.1945683e-05 |
| 10,179 |
LiveBin: A Localized and Version-Aware Binned Scan Index |
2026 |
SIGMOD |
4.1945683e-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.00045447517 |
| 131 |
Integrating Compression and Execution in Column-Oriented Database Systems |
2006 |
SIGMOD |
0.0004370331 |
| 167 |
The Snowflake Elastic Data Warehouse |
2016 |
SIGMOD |
0.00039180521 |
| 241 |
DB2 with BLU Acceleration: So Much More than Just a Column Store |
2013 |
VLDB |
0.00031420034 |
| 305 |
SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units |
2009 |
VLDB |
0.00028248614 |
| 310 |
The Vertica Analytic Database: C-Store 7 Years Later |
2012 |
VLDB |
0.00028132402 |
| 343 |
Implementing Database Operations Using SIMD Instructions |
2002 |
SIGMOD |
0.00026768139 |
| 368 |
Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing |
1998 |
VLDB |
0.000254931 |
| 476 |
Impala: A Modern, Open-Source SQL Engine for Hadoop |
2015 |
CIDR |
0.00022226941 |
| 542 |
Shark: SQL and Rich Analytics at Scale |
2013 |
SIGMOD |
0.00020595648 |
| 958 |
Rethinking SIMD Vectorization for In-Memory Databases |
2015 |
SIGMOD |
0.00015045316 |
| 1,134 |
Dictionary-based Order-preserving String Compression for Main Memory Column Stores |
2009 |
SIGMOD |
0.00013761456 |
| 1,270 |
BitWeaving: Fast Scans for Main Memory Data Processing |
2013 |
SIGMOD |
0.00012926086 |
| 1,477 |
Fine-grained Partitioning for Aggressive Data Skipping |
2014 |
SIGMOD |
0.00011770865 |
| 1,618 |
Row-wise Parallel Predicate Evaluation |
2008 |
VLDB |
0.00011114015 |
| 1,989 |
Column Imprints: A Secondary Index Structure |
2013 |
SIGMOD |
9.8478437e-05 |
| 2,390 |
ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout |
2015 |
SIGMOD |
8.9084657e-05 |
| 2,444 |
Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries |
2008 |
VLDB |
8.8076551e-05 |
| 2,882 |
Database Compression on Graphics Processors |
2010 |
VLDB |
7.9661218e-05 |
| 4,161 |
Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? |
2017 |
SIGMOD |
6.3938006e-05 |
| 5,532 |
A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew |
2015 |
SIGMOD |
5.4548897e-05 |
| 6,809 |
Adaptive Data Skipping in Main-Memory Systems |
2016 |
SIGMOD |
4.9206606e-05 |
Semantically Similar Papers