Understanding and Generalizing Monotonic Proximity Graphs for Approximate Nearest Neighbor Search
Graph-based algorithms have shown great empirical potential for the approximate nearest neighbor (ANN) search problem. Currently, graph-based ANN search algorithms are designed mainly using heuristics, whereas theoretical analysis of such algorithms is quite lacking. In this paper, we study a fundamental model of proximity graphs used in graph-based ANN search, called Monotonic Relative Neighborhood Graph (MRNG), from a theoretical perspective. We use mathematical proofs to explain why proximity graphs that are built based on MRNG tend to have good searching performance. We also run experiments on MRNG and graphs generalizing MRNG to obtain a deeper understanding of the model. Our experiments give guidance on how to approximate and generalize MRNG to build proximity graphs on a large scale. In addition, we discover and study a hidden structure of MRNG called conflicting nodes, and we give theoretical evidence how conflicting nodes could be used to improve ANN search methods that are based on MRNG.
Code (0)
등록된 구현이 없습니다.
Tasks
Mathematical ProofsSimilar Papers 제목 키워드 기반
Proximity Graph Maintenance for Fast Online Nearest Neighbor Search
Approximate Nearest Neighbor (ANN) search is a fundamental technique for (e.g.,) the deployment of recommender systems. Recent studies bring proximity graph-based methods into practitioners' attention -- proximity graph-…
QuantizationRecommendation SystemsGeneralizing while preserving monotonicity in comparison-based preference learning models
If you tell a learning model that you prefer an alternative $a$ over another alternative $b$, then you probably expect the model to be monotone, that is, the valuation of $a$ increases, and that of $b$ decreases. Yet, pe…
Asymmetric Transitivity Preserving Graph Embedding
Graph embedding algorithms embed a graph into a vector space where the structure and the inherent properties of the graph are preserved. The existing graph embedding methods cannot preserve the asymmetric transitivity we…
Graph EmbeddingLink PredictionAutomated Lane Detection in Crowds using Proximity Graphs
Studying the behavior of crowds is vital for understanding and predicting human interactions in public areas. Research has shown that, under certain conditions, large groups of people can form collective behavior pattern…
Lane DetectionEfficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW). The proposed solution is fully graph-based, without any …