Compressing Large Boolean Matrices Using Reordering Techniques

Summary: Losslessly compresses large Boolean matrices by reordering columns to minimize Hamming-distance transitions, reducing storage and access costs. Scalable partitioning and sampling adaptations of TSP heuristics handle high-dimensional instances beyond in-memory solvers. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h433e52159f555149
Venue: VLDB
Year: 2004
Pagerank: 6.8721548e-05
Overall Rank: 3,987 | 73.20%
DOI: 10.1016/B978-012088469-8.50005-X

Incoming Non-self Citations Over Time

Authors

1. David Johnson (AT&T)
2. Shankar Krishnan (AT&T)
3. Subodh Kumar (Johns Hopkins University)
4. Jatin Chhugani (Johns Hopkins University)
5. Suresh Venkatasubramanian (AT&T)

BibTeX Citation

@article{johnson_vldb04,
        title = {{Compressing Large Boolean Matrices Using Reordering Techniques}},
        author = {Johnson, David and Krishnan, Shankar and Kumar, Subodh and Chhugani, Jatin and Venkatasubramanian, Suresh},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {13},
        doi = {10.1016/B978-012088469-8.50005-X},
        url = {https://doi.org/10.1016/B978-012088469-8.50005-X},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,210	Processing a Trillion Cells per Mouse Click	2012	VLDB	0.00011527605
5,600	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.0709132e-05
7,780	Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search	2013	VLDB	5.4537563e-05
8,773	Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices	2022	VLDB	5.2804275e-05
11,107	HyperMR: Efficient Hypergraph-enhanced Matrix Storage on Compute-in-Memory Architecture	2025	SIGMOD	4.9793485e-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
32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00049737458
1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.4099587e-05
6,842	Walking Through A Very Large Virtual Environment In Real-time	2001	VLDB	5.6665639e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	900	Query Optimization In Compressed Database Systems	2001	SIGMOD
2	6,095	Column Partition and Permutation for Run Length Encoding in Columnar Databases	2020	SIGMOD
3	8,500	Tree-Encoded Bitmaps	2020	SIGMOD
4	8,901	Biclustering and Boolean Matrix Factorization in Data Streams	2020	VLDB
5	1,375	Query Preserving Graph Compression	2012	SIGMOD
6	910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
7	621	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD
8	7,024	Rearranging Data to Maximize the Efficiency of Compression	1986	PODS
9	1,329	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
10	8,773	Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices	2022	VLDB