Norm Adjusted Proximity Graph for Fast Inner Product Retrieval

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

View graph of relations

Author(s)

  • Shulong Tan
  • Zhaozhuo Xu
  • Weijie Zhao
  • Hongliang Fei
  • Ping Li

Detail(s)

Original languageEnglish
Title of host publicationKDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining
PublisherAssociation for Computing Machinery
Pages1552–1560
ISBN (Electronic)9781450383325
Publication statusPublished - Aug 2021
Externally publishedYes

Conference

Title27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2021)
LocationVirtual
PlaceSingapore
Period14 - 18 August 2021

Abstract

Efficient inner product search on embedding vectors is often the vital stage for online ranking services, such as recommendation and information retrieval. Recommendation algorithms, e.g., matrix factorization, typically produce latent vectors to represent users or items. The recommendation services are conducted by retrieving the most relevant item vectors given the user vector, where the relevance is often defined by inner product. Therefore, developing efficient recommender systems often requires solving the so-called maximum inner product search (MIPS) problem. In the past decade, there have been many studies on efficient MIPS algorithms. This task is challenging in part because the inner product does not follow the triangle inequality of metric space.

Compared with hash-based or quantization-based MIPS solutions, in recent years graph-based MIPS algorithms have demonstrated their strong empirical advantages in many real-world MIPS tasks. In this paper, we propose a new index graph construction method named norm adjusted proximity graph (NAPG), for efficient MIPS. With adjusting factors estimated on sampled data, NAPG is able to select more meaningful data points to connect with when constructing graph-based index for inner product search. Our extensive experiments on a variety of datasets verify that the improved graph-based index strategy provides another strong addition to the pool of efficient MIPS algorithms.

Research Area(s)

  • Recommendation, maximum inner product search, approximate near neighbor search, search on graph

Citation Format(s)

Norm Adjusted Proximity Graph for Fast Inner Product Retrieval. / Tan, Shulong; Xu, Zhaozhuo; Zhao, Weijie; Fei, Hongliang; Zhou, Zhixin; Li, Ping.

KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. Association for Computing Machinery, 2021. p. 1552–1560.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review