On Efficient Retrieval of Top Similarity Vectors

Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, Ping LiEMNLP 2019 · OpenReview

Abstract: Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, Ping Li. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).

2019.

Introduction

In modern artificial intelligence, entities such as words, users, and products are frequently represented as dense vectors in high-dimensional spaces. Finding the most similar item to a query vector typically involves Maximum Inner Product Search (MIPS). However, the inner product is a non-metric measure; unlike Euclidean distance, it does not satisfy the triangle inequality.

Most existing Approximate Nearest Neighbor Search (ANNS) tools are optimized for metric spaces. When applied to MIPS, these tools often suffer from efficiency bottlenecks or require complex mathematical transformations that limit performance. Researchers from Baidu have addressed this by developing the Inner Product Delaunay Graph (IPDG), a graph-based search method designed specifically for the unique geometry of inner products.

Methods

The IPDG approach introduces two primary innovations to optimize graph-based retrieval for non-metric spaces:

1. Inner Product-Specific Edge Selection

Traditional graph methods like HNSW add edges to maintain graph diversity based on distance. In contrast, IPDG employs a pruning rule tailored for MIPS: an edge to a candidate point $b$ is only retained if $b$ is not "hidden" by a superior point $a$. Specifically, if $b^T b \leq a^T b$, point $b$ is considered dispensable and the edge is discarded. This logic results in a sparser graph that prioritizes "extreme points" on the dataset's convex hull.

Inner product-specific edge selection logic: (a) shows the query relationship, while (b) illustrates the vector-based pruning rule.

2. Two-Round Construction

To ensure high graph quality regardless of point insertion order, the authors implement a two-round construction process. This allows the graph to refine its structure and globally discover the most effective extreme points, preventing early-inserted points from degrading the final search efficiency.

Key Insights: The Power of Extreme Points

A fundamental observation of this work is that for inner product search, only points residing on the convex hull (the outer boundary of the point cloud) can ever be the top-1 result for a query. Traditional metric-based methods often waste computational resources navigating through "internal" points that are mathematically incapable of being the optimal match.

MIPS geometry: The red points on the convex hull define the search regions; only these extreme points can be the maximum inner product for a given query.

By pruning edges that do not lead toward the convex hull, IPDG creates an efficient "highway" system. This sparsity directly translates to search speed without sacrificing accuracy.

Evaluation and Results

The authors evaluated IPDG across six datasets representing NLP (e.g., fastText, GloVe) and Recommendation Systems (e.g., Amazon Movie, Netflix).

  • Superior Efficiency: IPDG consistently outperformed state-of-the-art methods like HNSW-Wrapper and ip-NSW in "Recall vs. Time" benchmarks.
  • Reduced Computational Overhead: On the fastTextFr dataset, IPDG achieved 95% recall while examining only 0.07% of the total data, compared to 0.3% for the previous best method.
  • Robustness: IPDG maintained high performance across varying dimensions, proving more stable than baselines that struggled with high-dimensional word embeddings.
  • Graph Quality: Analysis confirmed that IPDG graphs have significantly fewer nodes with incoming edges, validating the strategy of ignoring non-extreme points.

Conclusion and Future Work

IPDG demonstrates that tailoring graph structures to the specific mathematical properties of the similarity measure—rather than forcing metric assumptions—yields significant performance gains. While currently optimized for top-1 retrieval, future research may extend these principles to top-$n$ search and hardware-accelerated (GPU) implementations for billion-scale datasets.

Summary updated

BibTeX
@inproceedings{tan2019efficient,
  author = {Shulong Tan and Zhixin Zhou and Zhaozhuo Xu and Ping Li},
  title = {{On Efficient Retrieval of Top Similarity Vectors}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=Q72m4gGILdT},
}
Figure