Article: An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces

File Download

103327.pdf

Links for fulltext
(May Require Subscription)

Publisher Website: 10.1109/TKDE.2004.48
Scopus: eid_2-s2.0-13844298845
Find via

Supplementary

Citations:
- Scopus:
- Web of Science:
- PubMed Central:
Item Statistics (The Hub)
Appears in Collections:
- Computer Centre: Journal/Magazine Articles

Title	An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces
Authors	Tao, Y2 Zhang, J3 Papadias, D4 Mamoulis, N1
Keywords	Information storage and retrieval Selection process
Issue Date	2004
Publisher	I E E E. The Journal's web site is located at http://www.computer.org/tkde
Citation	Ieee Transactions On Knowledge And Data Engineering, 2004, v. 16 n. 10, p. 1169-1184 [How to Cite?] DOI: http://dx.doi.org/10.1109/TKDE.2004.48
Abstract	Existing models for nearest neighbor search in multidimensional 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 nonuniform 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.
ISSN	1041-4347 2011 Impact Factor: 1.657 2011 SCImago Journal Rankings: 0.081
DOI	http://dx.doi.org/10.1109/TKDE.2004.48
References	References in Scopus

DC Field	Value
dc.contributor.author	Tao, Y
dc.contributor.author	Zhang, J
dc.contributor.author	Papadias, D
dc.contributor.author	Mamoulis, N
dc.date.accessioned	2007-03-23T04:50:47Z
dc.date.available	2007-03-23T04:50:47Z
dc.date.issued	2004
dc.description.abstract	Existing models for nearest neighbor search in multidimensional 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 nonuniform 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.
dc.description.nature	published_or_final_version
dc.format.extent	1486069 bytes
dc.format.extent	26624 bytes
dc.format.mimetype	application/pdf
dc.format.mimetype	application/msword
dc.identifier.citation	Ieee Transactions On Knowledge And Data Engineering, 2004, v. 16 n. 10, p. 1169-1184 [How to Cite?] DOI: http://dx.doi.org/10.1109/TKDE.2004.48
dc.identifier.doi	http://dx.doi.org/10.1109/TKDE.2004.48
dc.identifier.epage	1184
dc.identifier.hkuros	103327
dc.identifier.issn	1041-4347 2011 Impact Factor: 1.657 2011 SCImago Journal Rankings: 0.081
dc.identifier.issue	10
dc.identifier.openurl
dc.identifier.scopus	eid_2-s2.0-13844298845
dc.identifier.spage	1169
dc.identifier.uri	http://hdl.handle.net/10722/43627
dc.identifier.volume	16
dc.language	eng
dc.publisher	I E E E. The Journal's web site is located at http://www.computer.org/tkde
dc.publisher.place	United States
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering
dc.relation.references	References in Scopus
dc.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.
dc.rights	Creative Commons: Attribution 3.0 Hong Kong License
dc.subject	Information storage and retrieval
dc.subject	Selection process
dc.title	An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces
dc.type	Article

<?xml encoding="utf-8" version="1.0"?><item><contributor.author>Tao, Y</contributor.author><contributor.author>Zhang, J</contributor.author><contributor.author>Papadias, D</contributor.author><contributor.author>Mamoulis, N</contributor.author><date.accessioned>2007-03-23T04:50:47Z</date.accessioned><date.available>2007-03-23T04:50:47Z</date.available><date.issued>2004</date.issued><identifier.citation>Ieee Transactions On Knowledge And Data Engineering, 2004, v. 16 n. 10, p. 1169-1184</identifier.citation><identifier.issn>1041-4347</identifier.issn><identifier.uri>http://hdl.handle.net/10722/43627</identifier.uri><description.abstract>Existing models for nearest neighbor search in multidimensional 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 nonuniform 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.</description.abstract><format.extent>1486069 bytes</format.extent><format.extent>26624 bytes</format.extent><format.mimetype>application/pdf</format.mimetype><format.mimetype>application/msword</format.mimetype><language>eng</language><publisher>I E E E. The Journal&apos;s web site is located at http://www.computer.org/tkde</publisher><relation.ispartof>IEEE Transactions on Knowledge and Data Engineering</relation.ispartof><rights>&#169;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.</rights><rights>Creative Commons: Attribution 3.0 Hong Kong License</rights><subject>Information storage and retrieval</subject><subject>Selection process</subject><title>An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces</title><type>Article</type><identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=1041-4347&amp;volume=16&amp;issue=10&amp;spage=1169&amp;epage=1184&amp;date=2004&amp;atitle=An+efficient+cost+model+for+optimization+of+nearest+neighbor+search+in+low+and+medium+dimensional+spaces</identifier.openurl><description.nature>published_or_final_version</description.nature><identifier.doi>10.1109/TKDE.2004.48</identifier.doi><identifier.scopus>eid_2-s2.0-13844298845</identifier.scopus><identifier.hkuros>103327</identifier.hkuros><relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-13844298845&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references><identifier.volume>16</identifier.volume><identifier.issue>10</identifier.issue><identifier.spage>1169</identifier.spage><identifier.epage>1184</identifier.epage><publisher.place>United States</publisher.place><bitstream.url>http://hub.hku.hk/bitstream/10722/43627/1/103327.pdf</bitstream.url></item>

Author Affiliations

The University of Hong Kong
City University of Hong Kong
Nanyang Technological University
Hong Kong University of Science and Technology