Introduction
Modern recommendation systems rely on latent factor models where users and items are represented as dense vectors in a high-dimensional space. Retrieving the "top-k" items for a user involves calculating inner products against millions of candidates, a process that is computationally prohibitive for real-time applications. While inverted indexes offer a solution for fast retrieval, they require sparse input vectors. Standard techniques for inducing sparsity often fail to preserve the geometric relationships between similar items. This paper introduces a novel framework that transforms dense latent factors into high-dimensional sparse embeddings while maintaining locality through geometry-aware permutations.
Methodology: TessSparseMap
The proposed framework, termed TessSparseMap, bridges the gap between continuous dense embeddings and discrete sparse patterns using three primary steps:
- Directional Tessellation: The surface of a $k$-dimensional unit sphere is divided into regions or "tiles." Each tile is identified by a tessellating vector. The authors utilize a deterministic algorithm that identifies the nearest tile in $O(k \log k)$ time, eliminating the need for extensive storage of tile coordinates.
- Region-Specific Permutations: A unique permutation is assigned to each tile. Crucially, these permutations are designed such that neighboring tiles have similar permutations, ensuring that vectors in close proximity on the sphere are mapped to similar sparsity patterns.
- Sparse Mapping: The original $k$-dimensional dense vector is padded with zeros to a higher dimension $p$. The permutation corresponding to the vector's region on the sphere is then applied. This results in a high-dimensional sparse vector where the indices of non-zero entries are determined by the original vector's orientation.
Experimental Evaluation
The researchers evaluated TessSparseMap against common baselines, including Sign Random Projections (SRP-LSH), SuperBit-LSH, and PCA-Trees, using both synthetic datasets and the MovieLens 100k benchmark.
Key Results
- Efficiency and Speedup: The method achieved a 3-5x speedup compared to brute-force search by effectively discarding 70-80% of the search space with minimal impact on retrieval quality.
- Recovery Accuracy: At equivalent levels of data pruning, TessSparseMap consistently outperformed LSH-based methods in recovery accuracy. It is significantly more effective at retaining the true top-k items within the reduced candidate pool.
- Consistency: Unlike randomized hashing techniques which can exhibit high variance across different users, TessSparseMap showed a much tighter distribution in the percentage of items discarded, indicating more predictable performance.
Conclusion and Future Work
TessSparseMap demonstrates that geometry-aware mappings can significantly enhance the efficiency of latent factor retrieval. By leveraging the geometric properties of the unit sphere and the similarity of permutations, the framework provides a robust mechanism for generating locality-preserving sparse embeddings.
While the results are promising, the authors identify several areas for future exploration. The current mapping requires an increase in dimensionality ($p > k$), which may impact memory usage. Additionally, the current tessellation assumes a uniform distribution of factors; adapting the density of tiles to match data clusters could further improve performance. Finally, establishing formal theoretical bounds for the sparse mapping schema remains an open research objective.
Summary updated