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: 10467
Venue: VLDB
Year: 2011
Pagerank: 0.00010103504
Overall Rank: 1,655 | 88.65%
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
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
823	The Yin and Yang of Processing Data Warehousing Queries on GPU Devices	2013	VLDB	0.00013792901
847	Benchmarking Learned Indexes	2021	VLDB	0.0001365768
2,112	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1514258e-05
3,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.6328776e-05
3,686	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.2029305e-05
5,709	GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons	2018	VLDB	6.1142154e-05
8,580	Accelerating Pathology Image Data Cross-Comparison on CPU-GPU Hybrid Systems	2012	VLDB	5.4082911e-05
10,261	LICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework	2026	SIGMOD	5.093636e-05
10,624	Learned Static Function Data Structures	2026	VLDB	5.093636e-05
11,888	Document Reordering for Faster Intersection	2019	VLDB	5.093636e-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,717	Improving the Performance of List Intersection	2009	VLDB	9.9327227e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,157	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD
2	1,989	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD
3	4,144	Tile-based Lightweight Integer Compression in GPU	2022	SIGMOD
4	11,888	Document Reordering for Faster Intersection	2019	VLDB
5	2,232	Database Compression on Graphics Processors	2010	VLDB
6	2,948	Optimized Query Execution in Large Search Engines with Global Page Ordering	2003	VLDB
7	3,378	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD
8	2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB
9	1,717	Improving the Performance of List Intersection	2009	VLDB
10	8,201	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB