Approximate line nearest neighbor search speeds up matching along specific directions
Fast Approximate Line Nearest Neighbor Search
Databases
Summary
Finding closest matches to a point in a database is common, but sometimes you want to find matches that ignore differences along a certain direction, like lighting changes in images. The authors study a new way to do this by treating the query as a line instead of a single point, which is tricky because previous methods either are slow or miss some matches. They propose LinePG, a method that links different regions near that line effectively to find approximate nearest matches efficiently. Their tests show that LinePG works well compared to older methods.
What this means in practice
- •For graphics developers: Select images for photo-based animation by efficiently matching content while ignoring illumination changes specified by a line query.
- •For multimedia system engineers: Improve video synthesis tools by finding visual matches that vary along controlled aspects like lighting or pose.
Authors
Jiadong Xie, Jeffrey Xu Yu, Yingfan Liu
Abstract
Approximate nearest neighbor (ANN) search, which retrieves vectors close to a given query vector, is a fundamental operation in vector databases. However, emerging applications, such as selecting source images for photo-based animation and video synthesis, may require matching content while allowing a query-specified aspect contrast, such as an illumination change, to vary; a single query point does not directly express this requirement. In this paper, we study approximate line nearest neighbor (LANN) search, where an infinite query line removes the distance contribution along a specified direction while database records remain points. Prior approaches focus on top-$1$ search only for LANN and can incur high construction costs. Converting LANN into ordinary point ANN search through dimension lifting substantially increases index construction and query costs, while direct search on a proximity graph built for ordinary point ANN search can miss distinct regions close to a line. To address these issues, we propose LinePG, which enhances an existing proximity graph with pair edges to facilitate navigation between separated near-line regions. To find these pair edges efficiently, we first generate region pairs with spatial or graph separation, and near a line. We then score edges between the selected region pairs to guide the point endpoint selections. We conduct extensive performance studies and confirm the accuracy and efficiency of LinePG in comparison with the baseline approaches.