Anytime k-nearest neighbor search for database applications

被引:1
作者
Xu, Weijia [1 ]
Miranker, Daniel P. [2 ]
Mao, Rui [2 ]
Ramakrishnan, Smriti [2 ]
机构
[1] Univ Texas Austin, Texas Adv Comp Ctr, Austin, TX 78712 USA
[2] Univ Texas Austin, Dept Comp Sci, Austin, TX 78712 USA
来源
SISAP 2008: FIRST INTERNATIONAL WORKSHOP ON SIMILARITY SEARCH AND APPLICATIONS, PROCEEDINGS | 2008年
关键词
D O I
10.1109/SISAP.2008.11
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Many contemporary database applications require similarity-based retrieval of complex objects where the only usable knowledge of its domain is determined by a metric distance function. In support of these applications, we explored a search strategy for k-nearest neighbor searches with MVP-trees that greedily identifies k answers and then improves the answer set monotonically. The algorithm returns an approximate solution when terminated early, as determined by a limiting radius or an internal measure of progress. Given unbounded time the algorithm terminates with an exact solution. Approximate solutions to k-nearest neighbor search provide much needed speed improvement to hard nearest-neighbor problems. Our anytime approximate formulation is well suited for interactive search applications as well as applications where the distance function itself is an approximation. We evaluate the algorithm over a suite of workloads, including image retrieval, biological data and high-dimensional vector data. Experimental results demonstrate the practical applicability of our approach.
引用
收藏
页码:139 / +
页数:3
相关论文
共 50 条
[41]   CHROMATIC K-NEAREST NEIGHBOR QUERIES [J].
van der Horst, Thijs ;
Loffler, Maarten ;
Staals, Frank .
JOURNAL OF COMPUTATIONAL GEOMETRY, 2025, 16 (01)
[42]   Hybrid k-Nearest Neighbor Classifier [J].
Yu, Zhiwen ;
Chen, Hantao ;
Liu, Jiming ;
You, Jane ;
Leung, Hareton ;
Han, Guoqiang .
IEEE TRANSACTIONS ON CYBERNETICS, 2016, 46 (06) :1263-1275
[43]   Ultrasound k-nearest neighbor entropy imaging: Theory, algorithm, and applications [J].
Li, Sinan ;
Tsui, Po-Hsiang ;
Wu, Weiwei ;
Wu, Shuicai ;
Zhou, Zhuhuang .
ULTRASONICS, 2024, 138
[44]   Approximate direct and reverse nearest neighbor queries, and the k-nearest neighbor graph [J].
Figueroa, Karina ;
Paredes, Rodrigo .
SISAP 2009: 2009 SECOND INTERNATIONAL WORKSHOP ON SIMILARITY SEARCH AND APPLICATIONS, PROCEEDINGS, 2009, :91-+
[45]   Reverse k-Nearest Neighbor Search Based on Aggregate Point Access Methods [J].
Kriegel, Hans-Peter ;
Kroeger, Peer ;
Renz, Matthias ;
Zuefle, Andreas ;
Katzdobler, Alexander .
SCIENTIFIC AND STATISTICAL DATABASE MANAGEMENT, PROCEEDINGS, 2009, 5566 :444-460
[46]   Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search [J].
Iwasaki, Masajiro .
SIMILARITY SEARCH AND APPLICATIONS, SISAP 2016, 2016, 9939 :20-33
[47]   Full Text Search Engine as Scalable k-Nearest Neighbor Recommendation System [J].
Suchal, Jan ;
Navrat, Pavol .
ARTIFICIAL INTELLIGENCE IN THEORY AND PRACTICE III, 2010, 331 :165-173
[48]   A fast algorithm of k-nearest neighbor search in the similarity retrieval of image databases [J].
Washizawa, Teruyoshi ;
Yada, Toru ;
Yasuda, Yasuhiko .
NII Journal, 2001, (02) :27-37
[49]   General Distributed Hash Learning on Image Descriptors for k-Nearest Neighbor Search [J].
Cao, Yuan ;
Qi, Heng ;
Gui, Jie ;
Li, Shuai ;
Li, Keqiu .
IEEE SIGNAL PROCESSING LETTERS, 2019, 26 (05) :750-754
[50]   Supporting range queries on web data using k-nearest neighbor search [J].
Bae, Wan D. ;
Alkobaisi, Shayma ;
Kim, Seon Ho ;
Narayanappa, Sada ;
Shahabi, Cyrus .
WEB AND WIRELESS GEOGRAPHICAL INFORMATION SYSTEMS, PROCEEDINGS, 2007, 4857 :61-+