Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search

Summary: Bitlist presents a compact full-text index encoding a set of document IDs into a single number, enabling extremely low space. Boolean search via bitwise ops; 36.7% less space and 61.9% faster than inverted-list compression, with similar runtime and much lower space than prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10829
Venue: VLDB
Year: 2013
Pagerank: 5.5786605e-05
Overall Rank: 7,629 | 47.66%
DOI: 10.14778/2536258.2536264

Incoming Non-self Citations Over Time

Authors

1. Weixiong Rao (Tongji University; University of Helsinki)
2. Lei Chen (Hong Kong University of Science and Technology)
3. Pan Hui (Hong Kong University of Science and Technology; Telekom Innovation Laboratories)
4. Sasu Tarkoma (University of Helsinki)

BibTeX Citation

@article{rao_vldb13,
        title = {{Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search}},
        author = {Rao, Weixiong and Chen, Lei and Hui, Pan and Tarkoma, Sasu},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {13},
        pages = {1522--1533},
        doi = {10.14778/2536258.2536264},
        url = {https://doi.org/10.14778/2536258.2536264},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,879	Capsule*: An Out-of-Core Training Mechanism for Colossal GNNs	2025	SIGMOD	5.2040783e-05
12,128	ConfSeer: Leveraging Customer Support Knowledge Bases for Automated Misconfiguration Detection	2015	VLDB	5.093636e-05

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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
2,245	Fast Set Intersection in Memory	2011	VLDB	8.8734284e-05
3,912	Compressing Large Boolean Matrices Using Reordering Techniques	2004	VLDB	7.0231849e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,897	Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files	1993	VLDB
2	2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB
3	1,407	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB
4	9,472	Indexing for Keyword Search with Structured Constraints	2023	PODS
5	4,988	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD
6	1,655	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB
7	1,587	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB
8	1,989	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD
9	8,201	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB
10	2,224	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD