File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces
  • Basic View
  • Metadata View
  • XML View
TitleAn efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces
 
AuthorsTao, Y2
Zhang, J3
Papadias, D4
Mamoulis, N1
 
KeywordsInformation storage and retrieval
Selection process
 
Issue Date2004
 
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tkde
 
CitationIeee 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
 
AbstractExisting 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.
 
ISSN1041-4347
2013 Impact Factor: 1.815
2013 SCImago Journal Rankings: 1.763
 
DOIhttp://dx.doi.org/10.1109/TKDE.2004.48
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorTao, Y
 
dc.contributor.authorZhang, J
 
dc.contributor.authorPapadias, D
 
dc.contributor.authorMamoulis, N
 
dc.date.accessioned2007-03-23T04:50:47Z
 
dc.date.available2007-03-23T04:50:47Z
 
dc.date.issued2004
 
dc.description.abstractExisting 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.naturepublished_or_final_version
 
dc.format.extent1486069 bytes
 
dc.format.extent26624 bytes
 
dc.format.mimetypeapplication/pdf
 
dc.format.mimetypeapplication/msword
 
dc.identifier.citationIeee 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.doihttp://dx.doi.org/10.1109/TKDE.2004.48
 
dc.identifier.epage1184
 
dc.identifier.hkuros103327
 
dc.identifier.issn1041-4347
2013 Impact Factor: 1.815
2013 SCImago Journal Rankings: 1.763
 
dc.identifier.issue10
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-13844298845
 
dc.identifier.spage1169
 
dc.identifier.urihttp://hdl.handle.net/10722/43627
 
dc.identifier.volume16
 
dc.languageeng
 
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tkde
 
dc.publisher.placeUnited States
 
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineering
 
dc.relation.referencesReferences 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.rightsCreative Commons: Attribution 3.0 Hong Kong License
 
dc.subjectInformation storage and retrieval
 
dc.subjectSelection process
 
dc.titleAn efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces
 
dc.typeArticle
 
<?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
  1. The University of Hong Kong
  2. City University of Hong Kong
  3. Nanyang Technological University
  4. Hong Kong University of Science and Technology