Column Imprints: A Secondary Index Structure

Summary: Column imprint: a cache-conscious secondary index of many small bit-vectors per cacheline to prune data access and cut memory traffic. Robust to unclustered data with only a few-percent overhead, and it outperforms zonemaps and WAH bitmaps on range queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h71fc45524bd4948d
Venue: SIGMOD
Year: 2013
Pagerank: 0.00010344951
Overall Rank: 1,531 | 89.72%
DOI: 10.1145/2463676.2465306

Incoming Non-self Citations Over Time

Authors

1. Lefteris Sidirourgos (Centrum Wiskunde & Informatica)
2. Martin Kersten (Centrum Wiskunde & Informatica)

BibTeX Citation

@inproceedings{sidirourgos_sigmod13,
        title = {{Column Imprints: A Secondary Index Structure}},
        author = {Sidirourgos, Lefteris and Kersten, Martin},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465306},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465306},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015454197
1,506	BF-Tree: Approximate Tree Indexing	2014	VLDB	0.00010448376
2,237	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7738349e-05
2,954	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.8119682e-05
3,285	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.4525495e-05
3,445	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.2911896e-05
3,592	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.1807308e-05
3,597	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1759026e-05
3,810	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB	7.0064171e-05
3,983	Simplicity Done Right for Join Ordering	2021	CIDR	6.8722161e-05
4,755	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.4309508e-05
4,875	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.3699172e-05
5,619	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0602908e-05
6,240	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.8373399e-05
6,751	Progressive Indexes: Indexing for Interactive Data Analysis	2019	VLDB	5.6880934e-05
7,486	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5102404e-05
8,207	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3763264e-05
8,490	Provenance-based Data Skipping	2022	VLDB	5.3302146e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3286931e-05
8,541	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3190248e-05
8,559	F3: The Open-Source Data File Format for the Future	2026	SIGMOD	5.3141911e-05
9,213	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB	5.2056173e-05
9,984	Fingerprints for Compressed Columnar Data Search	2019	SIGMOD	5.0991805e-05
10,602	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9769913e-05
10,666	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.9769913e-05
12,076	Workload-Aware Column Imprints	2020	SIGMOD	4.9769913e-05
12,360	Database System Support of Simulation Data	2016	VLDB	4.9769913e-05
12,437	GIS Navigation Boosted by Column Stores	2015	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.0006897844
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00064013679
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033459417
207	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024976482
252	Database Cracking	2007	CIDR	0.00023101361
702	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.00014668058
1,148	Bit Transposed Files	1985	VLDB	0.00011809942
1,495	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010493769
1,631	Positional Update Handling in Column Stores	2010	SIGMOD	0.00010019069
2,803	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.9863094e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,839	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
2	2,954	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD
3	1,837	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
4	910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
5	61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD
6	769	Bitmap Index Design and Evaluation	1998	SIGMOD
7	4,755	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB
8	5,601	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
9	9,984	Fingerprints for Compressed Columnar Data Search	2019	SIGMOD
10	12,076	Workload-Aware Column Imprints	2020	SIGMOD