Bit-Sliced Index Arithmetic

Summary: Bit-Sliced Index Arithmetic defines Z = X+Y, V = X-Y, W = MIN(X,Y) on BSIs for efficient multisets via UNION ALL / EXCEPT ALL / INTERSECT ALL. Extends top-k BSI ranges and introduces BSTM, a fast index-based top-k document matcher by shared terms, competitive with IR. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3318
Venue: SIGMOD
Year: 2001
Pagerank: 7.2721197e-05
Overall Rank: 3,597 | 75.33%
DOI: 10.1145/375663.375669

Incoming Non-self Citations Over Time

Authors

1. Denis Rinfret (University of Massachusetts Boston)
2. Patrick O'Neil (Microsoft; University of Massachusetts Boston)
3. Elizabeth O'Neil (Microsoft; University of Massachusetts Boston)

BibTeX Citation

@inproceedings{rinfret_sigmod01,
        title = {{Bit-Sliced Index Arithmetic}},
        author = {Rinfret, Denis and O'Neil, Patrick and O'Neil, Elizabeth},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375669},
        url = {https://dl.acm.org/doi/10.1145/375663.375669},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
870	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.0001350293
2,206	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.957715e-05
4,798	Accelerating Generalized Linear Models with MLWeaving: A One-Size-Fits-All System for Any-Precision Learning	2019	VLDB	6.5024772e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
8,349	Tree-Encoded Bitmaps	2020	SIGMOD	5.4460774e-05
10,056	Rethinking the Encoding of Integers for Scans on Skewed Data	2023	SIGMOD	5.1676234e-05
11,288	Large-Scale Metric Computation in Online Controlled Experiment Platform	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
19	A Critique of ANSI SQL Isolation Levels	1995	SIGMOD	0.00058720861
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
794	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00013969303
1,464	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010689981
4,656	Query Optimization for Selections using Bitmaps	1999	SIGMOD	6.5834278e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	924	Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates	1992	SIGMOD
2	6,491	Two-dimensional Substring Indexing	2001	PODS
3	1,867	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
4	4,656	Query Optimization for Selections using Bitmaps	1999	SIGMOD
5	14,492	Bit-Sliced VLSI Algorithms for Search and Sort	1984	VLDB
6	1,464	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD
7	1,894	Optimizing Queries On Compressed Bitmaps	2000	VLDB
8	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
9	104	Improved Query Performance with Variant Indexes	1997	SIGMOD
10	794	Bitmap Index Design and Evaluation	1998	SIGMOD