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: 9371
Venue: VLDB
Year: 2004
Pagerank: 7.0231849e-05
Overall Rank: 3,912 | 73.17%
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,225	Processing a Trillion Cells per Mouse Click	2012	VLDB	0.00011590013
5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.2058219e-05
7,629	Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search	2013	VLDB	5.5786605e-05
8,617	Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices	2022	VLDB	5.4002779e-05
10,666	HyperMR: Efficient Hypergraph-enhanced Matrix Storage on Compute-in-Memory Architecture	2025	SIGMOD	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
31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00050347119
1,867	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.5903618e-05
6,715	Walking Through A Very Large Virtual Environment In Real-time	2001	VLDB	5.7959545e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,644	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB
2	5,985	Column Partition and Permutation for Run Length Encoding in Columnar Databases	2020	SIGMOD
3	8,349	Tree-Encoded Bitmaps	2020	SIGMOD
4	8,739	Biclustering and Boolean Matrix Factorization in Data Streams	2020	VLDB
5	1,336	Query Preserving Graph Compression	2012	SIGMOD
6	925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
7	610	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD
8	6,882	Rearranging Data to Maximize the Efficiency of Compression	1986	PODS
9	1,301	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
10	8,617	Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices	2022	VLDB