File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Efficient k-NN search on vertically decomposed data

TitleEfficient k-NN search on vertically decomposed data
Authors
Issue Date2002
PublisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/sigmod
Citation
Proceedings Of The Acm Sigmod International Conference On Management Of Data, 2002, p. 322-333 How to Cite?
AbstractApplications like multimedia retrieval require efficient support for similarity search on large data collections. Yet, nearest neighbor search is a difficult problem in high dimensional spaces, rendering efficient applications hard to realize: index structures degrade rapidly with increasing dimensionality, while sequential search is not an attractive solution for repositories with millions of objects. This paper approaches the problem from a different angle. A solution is sought in an unconventional storage scheme, that opens up a new range of techniques for processing k-NN queries, especially suited for high dimensional spaces. The suggested (physical) database design accommodates well a novel variant of branch-and-bound search, that reduces the high dimensional space quickly to a small candidate set. The paper provides insight in applying this idea to k-NN search using two similarity metrics commonly encountered in image database applications, and discusses techniques for its implementation in relational database systems. The effectiveness of the proposed method is evaluated empirically on both real and synthetic data sets, reporting the significant improvements in response time yielded.
Persistent Identifierhttp://hdl.handle.net/10722/93310
ISSN

 

DC FieldValueLanguage
dc.contributor.authorDe Vries, APen_HK
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorNes, Nen_HK
dc.contributor.authorKersten, Men_HK
dc.date.accessioned2010-09-25T14:57:14Z-
dc.date.available2010-09-25T14:57:14Z-
dc.date.issued2002en_HK
dc.identifier.citationProceedings Of The Acm Sigmod International Conference On Management Of Data, 2002, p. 322-333en_HK
dc.identifier.issn0730-8078en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93310-
dc.description.abstractApplications like multimedia retrieval require efficient support for similarity search on large data collections. Yet, nearest neighbor search is a difficult problem in high dimensional spaces, rendering efficient applications hard to realize: index structures degrade rapidly with increasing dimensionality, while sequential search is not an attractive solution for repositories with millions of objects. This paper approaches the problem from a different angle. A solution is sought in an unconventional storage scheme, that opens up a new range of techniques for processing k-NN queries, especially suited for high dimensional spaces. The suggested (physical) database design accommodates well a novel variant of branch-and-bound search, that reduces the high dimensional space quickly to a small candidate set. The paper provides insight in applying this idea to k-NN search using two similarity metrics commonly encountered in image database applications, and discusses techniques for its implementation in relational database systems. The effectiveness of the proposed method is evaluated empirically on both real and synthetic data sets, reporting the significant improvements in response time yielded.en_HK
dc.languageengen_HK
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/sigmoden_HK
dc.relation.ispartofProceedings of the ACM SIGMOD International Conference on Management of Dataen_HK
dc.titleEfficient k-NN search on vertically decomposed dataen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-0036373391en_HK
dc.identifier.hkuros71424en_HK
dc.identifier.spage322en_HK
dc.identifier.epage333en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridDe Vries, AP=7202909827en_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridNes, N=24176412900en_HK
dc.identifier.scopusauthoridKersten, M=7005064657en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats