Practice With Graph-based ANN Algorithms On Sparse Data Chi-square Two-tower Model HNSW Sign Cauchy Projections | Awesome Learning to Hash Add your paper to Learning2Hash

Awesome Learning to Hash

A Webpage dedicated to the latest research on Hash Function Learning. Maintained by Sean Moran.

Contact Sean Moran about this survey or website. Made with Jekyll and Hyde.

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

Li Ping, Zhao Weijie, Wang Chao, Xia Qi, Wu Alice, Peng Lijun. Arxiv 2023

[Paper]    
ARXIV Graph Independent

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 theReLu’’ 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 thechi-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 ANN algorithms we can choose from, in this study, we focus on the graph-based ANN algorithm (e.g., HNSW-type). Sparse embeddings should help improve the efficiency of EBR. One benefit is the reduced memory cost for the embeddings. The other obvious benefit is the reduced computational time for evaluating similarities, because, for graph-based ANN algorithms such as HNSW, computing similarities is often the dominating cost. In addition to the effort on leveraging data sparsity for storage and computation, we also integratesign cauchy random projections’’ (SignCRP) to hash vectors to bits, to further reduce the memory cost and speed up the ANN search. In NIPS’13, SignCRP was proposed to hash the chi-square similarity, which is a well-adopted nonlinear kernel in NLP and computer vision. Therefore, the chi-square two-tower model, SignCRP, and HNSW are now tightly integrated.

Similar Work