Practice With Graph-based ANN Algorithms On Sparse Data: Chi-square Two-tower Model, HNSW, Sign Cauchy Projections

Abstract

Sparse data are common. The traditional ``handcrafted'' features are often sparse. Embedding vectors from trained models can also be very sparse, for example, embeddings trained via the ``ReLu'' activation function. In this paper, we report our exploration of efficient search in sparse data with graph-based ANN algorithms (e.g., HNSW, or SONG which is the GPU version of HNSW), which are popular in industrial practice, e.g., search and ads (advertising). We experiment with the proprietary ads targeting application, as well as benchmark public datasets. For ads targeting, we train embeddings with the standard ``cosine two-tower'' model and we also develop the ``chi-square two-tower'' model. Both models produce (highly) sparse embeddings when they are integrated with the ``ReLu'' activation function. In EBR (embedding-based retrieval) applications, after we the embeddings are trained, the next crucial task is the approximate near neighbor (ANN) search for serving. While there are many A

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyli2023practice

Related papers

• Efficient And Effective Retrieval Of Dense-sparse Hybrid Vectors Using Graph-based Approximate Nearest Neighbor Search (2024)0.00
• The Impacts Of Data, Ordering, And Intrinsic Dimensionality On Recall In Hierarchical Navigable Small Worlds (2024)5.24
• Down With The Hierarchy: The 'H' In HNSW Stands For "hubs" (2024)0.00
• Sparse Neighborhood Graph-based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis And Optimization (2025)0.00
• Operational Advice For Dense And Sparse Retrievers: HNSW, Flat, Or Inverted Indexes? (2024)0.00
• Lightsage: Graph Neural Networks For Large Scale Item Retrieval In Shopee's Advertisement Recommendation (2023)6.77
• Progressively Optimized Bi-granular Document Representation For Scalable Embedding Based Retrieval (2022)11.06
• Hyperformer: Learning Expressive Sparse Feature Representations Via Hypergraph Transformer (2023)7.50