Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
High-dimensional nearest neighbor search with remote data centers
Wang C., Wang X. Knowledge and Information Systems4 (4):440-465,2002.Type:Article
Date Reviewed: May 30 2003

A new strategy for nearest neighbor search is presented by the authors that offers fast and early-terminated query evaluation in a network environment, where the data is located remotely, and the search process is supposed to be shared by local, remote, and possibly some intermediate hosts. The strategy involves a multi-level approximation scheme. Each level receives a candidate set of items from its predecessor, and refines the set by applying a more accurate approximation to filter out undesired items. In addition to this process, each level also returns an item along with a number, M, with the guarantee that the item is one of the M nearest neighbors, with M being strictly reduced level after level. Thus, a user might stop whenever he or she feels satisfied, or when M=1.

The approximation is done by mathematically estimating the lower and upper bounds for the measured neighborhood distances of the candidates. The gaps between these bounds are managed, to be reduced quickly after each level, resulting in an efficient filtering algorithm.

Its combination of early termination and low-cost refinement makes this strategy interesting. The analysis and experiments show the superiority of the strategy compared to conventional methods. It would be better if the authors explained in more detail how to apply the technique to distances other than Euclidean. I think the appendix could probably be made shorter by applying Cauchy’s inequality.

Reviewer:  Ngoc Minh Review #: CR127685 (0309-0934)
Bookmark and Share
 
Distributed Systems (H.3.4 ... )
 
 
Data Mining (H.2.8 ... )
 
 
Modeling Techniques (C.4 ... )
 
 
Web-Based Services (H.3.5 ... )
 
 
Distributed Systems (C.2.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Distributed Systems": Date
Document replication and distribution in extensible geographically distributed Web servers
Zhuo L., Wang C., Lau F. Journal of Parallel and Distributed Computing 63(10): 927-944, 2003. Type: Article
Jun 18 2004
Collectives and the design of complex systems
Tumer K., Wolpert D., Turner K., Springer-Verlag, London, UK, 2004.  321, Type: Book (9780387401652)
Jul 27 2004
Network distributed computing: fitscapes and fallacies
Goff M., Prentice Hall Professional Technical Reference, Upper Saddle River, NJ, 2003.  240, Type: Book (9780131001527)
Sep 1 2004
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy