Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding

Summary: Lazy RID-list intersection forms lists on demand during conjunction, cutting IO/sort costs and reducing fragility to misestimates on skewed data. An adaptive set-intersection method replaces AND-tree, robust to cardinality errors; experiments show efficiency and predictability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3961
Venue: SIGMOD
Year: 2007
Pagerank: 7.3448437e-05
Overall Rank: 3,524 | 75.83%
DOI: 10.1145/1247480.1247566

Incoming Non-self Citations Over Time

Authors

1. Vijayshankar Raman (IBM)
2. Lin Qiao (IBM)
3. Wei Han (IBM)
4. Inderpal S. Narang (IBM)
5. Ying-Lin Chen (IBM)
6. Kou-Horng Yang (IBM)
7. Fen-Lin Ling (IBM)

BibTeX Citation

@inproceedings{raman_sigmod07,
        title = {{Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding}},
        author = {Raman, Vijayshankar and Qiao, Lin and Han, Wei and Narang, Inderpal S. and Chen, Ying-Lin and Yang, Kou-Horng and Ling, Fen-Lin},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247566},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247566},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,717	Improving the Performance of List Intersection	2009	VLDB	9.9327227e-05
1,804	Authenticated Join Processing in Outsourced Databases	2009	SIGMOD	9.7171985e-05
2,224	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.9183396e-05
6,791	MILC: Inverted List Compression in Memory	2017	VLDB	5.7723936e-05
7,492	Scalable Distributed Inverted List Indexes in Disaggregated Memory	2024	SIGMOD	5.6047664e-05
7,842	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	5.5333985e-05
9,082	An Application-Specific Instruction Set for Accelerating Set-Oriented Database Primitives	2014	SIGMOD	5.3251649e-05
12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00069513174
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
100	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034385207
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013846487

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,689	Adaptive Index Structures	2002	VLDB
2	8,625	QPPT: Query Processing on Prefix Trees	2013	CIDR
3	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
4	11,888	Document Reordering for Faster Intersection	2019	VLDB
5	12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
6	694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
7	11,453	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
8	10,612	Index Intersection for High-Dimensional Range Queries	2026	VLDB
9	1,811	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
10	1,717	Improving the Performance of List Intersection	2009	VLDB