TY - GEN
T1 - Randomized approaches for nearest neighbor search in metric space when computing the pairwise distance is extremely expensive
AU - Wang, Lusheng
AU - Yang, Yong
AU - Lin, Guohui
PY - 2010
Y1 - 2010
N2 - Finding the closest object for a query in a database is a classical problem in computer science. For some modern biological applications, computing the similarity between two objects might be very time consuming. For example, it takes a long time to compute the edit distance between two whole chromosomes and the alignment cost of two 3D protein structures. In this paper, we study the nearest neighbor search problem in metric space, where the pair-wise distance between two objects in the database is known and we want to minimize the number of distances computed on-line between the query and objects in the database in order to find the closest object. We have designed two randomized approaches for indexing metric space databases, where objects are purely described by their distances with each other. Analysis and experiments show that our approaches only need to compute O(log n) objects in order to find the closest object, where n is the total number of objects in the database. © Springer-Verlag Berlin Heidelberg 2010.
AB - Finding the closest object for a query in a database is a classical problem in computer science. For some modern biological applications, computing the similarity between two objects might be very time consuming. For example, it takes a long time to compute the edit distance between two whole chromosomes and the alignment cost of two 3D protein structures. In this paper, we study the nearest neighbor search problem in metric space, where the pair-wise distance between two objects in the database is known and we want to minimize the number of distances computed on-line between the query and objects in the database in order to find the closest object. We have designed two randomized approaches for indexing metric space databases, where objects are purely described by their distances with each other. Analysis and experiments show that our approaches only need to compute O(log n) objects in order to find the closest object, where n is the total number of objects in the database. © Springer-Verlag Berlin Heidelberg 2010.
UR - https://www.scopus.com/pages/publications/79956307641
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-79956307641&origin=recordpage
U2 - 10.1007/978-3-642-14355-7_25
DO - 10.1007/978-3-642-14355-7_25
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3642143547
SN - 9783642143540
VL - 6124 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 243
EP - 252
BT - Algorithmic Aspects in Information and Management
PB - Springer Verlag
T2 - 6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010
Y2 - 19 July 2010 through 21 July 2010
ER -