Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units

Summary: GPU-oriented inverted-list processing exploits empirically linear docID distributions: Linear Regression and Hash Segmentation tighten parallel intersection searches, while Linear Regression Compression enables parallel decompression. Experiments show higher query throughput than CPU-centric approaches. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h8a9e9f938bfe6817
Venue: VLDB
Year: 2011
Pagerank: 9.9310625e-05
Overall Rank: 1,671 | 88.77%
DOI: 10.14778/2002974.2002975

Incoming Non-self Citations Over Time

Authors

1. Naiyong Ao (Nankai University)
2. Fan Zhang (Nankai University)
3. Di Wu (Nankai University)
4. Douglas S. Stones (Monash University)
5. Gang Wang (Nankai University)
6. Xiaoguang Liu (Nankai University)
7. Jing Liu (Nankai University)
8. Sheng Lin (Nankai University)

BibTeX Citation

@article{ao_vldb11,
        title = {{Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units}},
        author = {Ao, Naiyong and Zhang, Fan and Wu, Di and Stones, Douglas S. and Wang, Gang and Liu, Xiaoguang and Liu, Jing and Lin, Sheng},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {8},
        pages = {470--481},
        doi = {10.14778/2002974.2002975},
        url = {https://doi.org/10.14778/2002974.2002975},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
463	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017804544
771	The Yin and Yang of Processing Data Warehousing Queries on GPU Devices	2013	VLDB	0.00014085862
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
848	Benchmarking Learned Indexes	2021	VLDB	0.00013506188
2,019	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1750421e-05
3,289	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.4528818e-05
3,314	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.4380767e-05
5,467	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB	6.119722e-05
8,619	Accelerating Pathology Image Data Cross-Comparison on CPU-GPU Hybrid Systems	2012	VLDB	5.3016441e-05
10,474	LICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework	2026	SIGMOD	4.9793485e-05
11,070	Learned Static Function Data Structures	2026	VLDB	4.9793485e-05
12,188	Document Reordering for Faster Intersection	2019	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,769	Improving the Performance of List Intersection	2009	VLDB	9.6869284e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,786	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
2	2,035	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD
3	3,655	Tile-based Lightweight Integer Compression in GPU	2022	SIGMOD
4	12,188	Document Reordering for Faster Intersection	2019	VLDB
5	2,185	Database Compression on Graphics Processors	2010	VLDB
6	3,004	Optimized Query Execution in Large Search Engines with Global Page Ordering	2003	VLDB
7	3,375	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD
8	2,060	Similarity search in the blink of an eye with compressed indices	2023	VLDB
9	1,769	Improving the Performance of List Intersection	2009	VLDB
10	8,368	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB