Document Reordering for Faster Intersection

Summary: Document reordering for inverted indexes to speed up intersections, beyond compression. Introduces a cost-based model tied to query distribution, showing fundamental differences from size minimization and presenting a heuristic reordering that achieves large intersection-speedups over prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12168
Venue: VLDB
Year: 2019
Pagerank: 5.093636e-05
Overall Rank: 11,888 | 18.44%
DOI: 10.14778/3303753.3303755

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Qi Wang (New York University)
2. Torsten Suel (New York University)

BibTeX Citation

@article{wang_vldb19,
        title = {{Document Reordering for Faster Intersection}},
        author = {Wang, Qi and Suel, Torsten},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {5},
        pages = {475--487},
        doi = {10.14778/3303753.3303755},
        url = {https://doi.org/10.14778/3303753.3303755},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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,655	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	0.00010103504
1,717	Improving the Performance of List Intersection	2009	VLDB	9.9327227e-05
2,245	Fast Set Intersection in Memory	2011	VLDB	8.8734284e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,407	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB
2	2,245	Fast Set Intersection in Memory	2011	VLDB
3	10,315	Fast Indexing for Temporal Information Retrieval	2026	SIGMOD
4	1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
5	12,296	Efficient Indexing for Diverse Query Results	2013	VLDB
6	9,472	Indexing for Keyword Search with Structured Constraints	2023	PODS
7	2,948	Optimized Query Execution in Large Search Engines with Global Page Ordering	2003	VLDB
8	1,717	Improving the Performance of List Intersection	2009	VLDB
9	1,989	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD
10	8,201	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB