HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2274
Title: An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces
Authors: Tao, Yufei
Zhang, Jun
Papadias, Dimitris
Mamoulis, Nikos
Keywords: Database
Spatial database
Nearest neighbor
Cost model
Issue Date: Oct-2004
Citation: IEEE transactions on knowledge and data engineering, v. 16, no. 10, October 2004, p. 1169-1184
Abstract: Existing models for nearest neighbor search in multi-dimensional spaces are not appropriate for query optimization because they either lead to erroneous estimation, or involve complex equations that are expensive to evaluate in real-time. This paper proposes an alternative method that captures the performance of nearest neighbor queries using approximation. For uniform data, our model involves closed formulae that are very efficient to compute and accurate for up to 10 dimensions. Further, the proposed equations can be applied on non-uniform data with the aid of histograms. We demonstrate the effectiveness of the model by using it to solve several optimization problems related to nearest neighbor search.
Rights: © 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
URI: http://hdl.handle.net/1783.1/2274
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
papaTKDEKNN.pdfpre-published version499KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.