Abstract
Traditional database systems struggle with the subjective and non-metric nature of music similarity. This paper introduces "fuzzy song sets" and a specialized algebra to manage these complex relationships within a Music Warehouse (MW). By employing optimized data structures such as Word Aligned Hybrid (WAH) bitmaps and relative-encoded arrays, the proposed system achieves significant storage efficiency. Our evaluation shows that WAH bitmaps, particularly when compressed, offer a scalable solution for warehouses containing millions of tracks, reducing storage requirements by nearly an order of magnitude compared to standard relational tables.
Introduction
The rise of music recommendation systems has highlighted a backend bottleneck: the inherent "fuzziness" of musical similarity. Unlike "crisp" data—where a song either belongs to a genre or it does not—similarity is subjective and often fails to satisfy mathematical metric properties like the triangle inequality. This failure breaks standard database indexing techniques. As collections grow, managing these nuanced relationships without excessive storage overhead becomes a critical challenge.
The Music Warehouse Architecture
The authors propose the Music Warehouse (MW), a system built on two core innovations: a fuzzy song set algebra and multidimensional data cubes.
Fuzzy Song Set Algebra
In a fuzzy song set, each member is assigned a membership degree between 0 and 1. The authors extend fuzzy logic with operators tailored for music discovery:
- Reduction ($\alpha$): Filters songs below a similarity threshold.
- $Top_k$: Retrieves the $k$ most similar songs.
- Average: Aggregates multiple fuzzy sets to find songs similar to a collection (e.g., an artist's catalog).
Multidimensional Cubes
The MW utilizes cubes to organize data across various dimensions. The Closest Songs Cube maps a seed song and a similarity function to a fuzzy set of neighbors, while the User Feedback Cube tracks user-graded recommendations in different contexts.
Storage Strategies and Evaluation
To handle the high overhead of traditional relational tables—where metadata can exceed the actual payload—three storage strategies were evaluated: traditional Tables, one-dimensional Arrays, and Word Aligned Hybrid (WAH) Bitmaps.
The system was tested using a dataset of 51,574 songs from Intelligent Sound and Music Brainz, with each song described by 15 similarity attributes.
Key Results
The evaluation revealed a "compression paradox." While theoretical estimates favored arrays, real-world implementation in PostgreSQL showed that WAH bitmaps, combined with Lempel-Ziv (LZ) compression, were superior. This is largely due to their compatibility with internal database storage mechanisms like TOAST tables.
For 15 attributes, LZ-compressed WAH bitmaps required only 2.9 GB, compared to over 21 GB for a standard table approach. The study suggests this approach can scale to 16 million songs within a 140 GB footprint, demonstrating that fuzzy sets can bypass the limitations of strict mathematical metrics while remaining storage-efficient.
Conclusion
Fuzzy song sets provide a robust framework for scaling music discovery. While storage efficiency is well-addressed by WAH bitmaps, future work will focus on optimizing query performance to ensure that fuzzy logical operations remain computationally efficient as data volumes continue to grow.
Summary updated