High-Dimensional Nearest Neighbor Search with Remote Data Centers |
| |
Authors: | Changzhou Wang Xiaoyang Sean Wang |
| |
Affiliation: | (1) Mathematics and Computing Technology, The Boeing Company, Bellevue, WA, USA, US;(2) Department of Information and Software Engineering, George Mason University, Fairfax, VA, USA, US |
| |
Abstract: | Many data centers have archived a tremendous amount of data and begun to publish them on the Web. Due to limited resources
and large amount of service requests, data centers usually do not directly support high-cost queries. On the other hand, users
are often overwhelmed by the huge data volume and cannot afford to download the whole data sets and search them locally. To
support high-dimensional nearest neighbor searches in this environment, the paper develops a multi-level approximation scheme.
The coarsest-level approximations are stored locally and searched first. The result is then refined gradually via accesses
to remote data centers. Data centers need only to deliver data items or their precomputed finer level approximations by their
identifiers.
The searching process is usually long in this environment, since it involves remote sites. This paper describes an online
search process: the system periodically reports a data item and a positive integer M. The reported item is guaranteed to be one of the M nearest neighbors of the query one. The paper proposes two algorithms to minimize M in each period. Experiments show that one of them performs similarly as a theoretical a posteriori algorithm and significantly
outperforms the online extensions of two state-of-the-art nearest neighbor search methods.
Received 25 July 2000 / Revised 25 July 2001 / Accepted in revised form 16 October 2001
Correspondence and offprint requests to: Xiaoyang Sean Wang, Department of Information and Software Engineering, George Mason University, Fairfax, VA 22030, USA.
Email: xywang@gmu.eduau |
| |
Keywords: | : High-dimensional data Nearest neighbor search Online algorithm |
本文献已被 SpringerLink 等数据库收录! |
|