2016/02/29 by Yihan Gao, Aditya Parameswaran · 15 citations
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Artificial intelligence #Compression (physics) #Computer science #Data Mining Algorithms and Applications #Data compression #Data mining #Information retrieval #Relational database #Table (database) #cs.DB
paper · pdf · doi:10.1145/2939672.2939867
arxiv created 2016/06/19 · arxiv updated 2016/06/21 · openalex created_date 2016/06/24 · openalex publication_date 2016/08/08 · openalex updated_date 2026/08/06
Relational datasets are being generated at an alarmingly rapid rate across organizations and industries. Compressing these datasets could significantly reduce storage and archival costs. Traditional compression algorithms, e.g., gzip, are suboptimal for compressing relational datasets since they ignore the table structure and relationships between attributes. We study compression algorithms that leverage the relational structure to compress datasets to a much greater extent. We develop Squish, a system that uses a combination of Bayesian Networks and Arithmetic Coding to capture multiple kinds of dependencies among attributes and achieve near-entropy compression rate. Squish also supports user-defined attributes: users can instantiate new data types by simply implementing five functions for a new class interface. We prove the asymptotic optimality of our compression algorithm and conduct experiments to show the effectiveness of our system: Squish achieves a reduction of over 50% in storage size relative to systems developed in prior work on a variety of real datasets.