首页 | 官方网站   微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号