Back to papers

Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases

Summary: tau-monotonic graph (tau-MG) for ANN in multi-dimensional databases; exploits a tau-monotonic property to guarantee exact NN when dist(q,NN) ≤ tau and to beat existing PG-based search times. Approximate tau-monotonic neighborhood graph (tau-MNG) lowers construction cost by restricting monotonicity to neighborhoods and adds a distance-reduction optimization; experiments on real datasets show gains over prior PG-based ANN methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID

6558

Venue

SIGMOD

Year

2023

Pagerank

9.8258191e-05

Overall Rank

2,002 | 86.09%

DOI

10.1145/3588908