File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Efficient k-NN search on vertically decomposed data
Title | Efficient k-NN search on vertically decomposed data |
---|---|
Authors | |
Issue Date | 2002 |
Publisher | Association 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? |
Abstract | Applications 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 Identifier | http://hdl.handle.net/10722/93310 |
ISSN | 2020 SCImago Journal Rankings: 0.949 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | De Vries, AP | en_HK |
dc.contributor.author | Mamoulis, N | en_HK |
dc.contributor.author | Nes, N | en_HK |
dc.contributor.author | Kersten, M | en_HK |
dc.date.accessioned | 2010-09-25T14:57:14Z | - |
dc.date.available | 2010-09-25T14:57:14Z | - |
dc.date.issued | 2002 | en_HK |
dc.identifier.citation | Proceedings Of The Acm Sigmod International Conference On Management Of Data, 2002, p. 322-333 | en_HK |
dc.identifier.issn | 0730-8078 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93310 | - |
dc.description.abstract | Applications 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.language | eng | en_HK |
dc.publisher | Association for Computing Machinery, Inc. The Journal's web site is located at http://www.acm.org/sigmod | en_HK |
dc.relation.ispartof | Proceedings of the ACM SIGMOD International Conference on Management of Data | en_HK |
dc.title | Efficient k-NN search on vertically decomposed data | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Mamoulis, N:nikos@cs.hku.hk | en_HK |
dc.identifier.authority | Mamoulis, N=rp00155 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-0036373391 | en_HK |
dc.identifier.hkuros | 71424 | en_HK |
dc.identifier.spage | 322 | en_HK |
dc.identifier.epage | 333 | en_HK |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | De Vries, AP=7202909827 | en_HK |
dc.identifier.scopusauthorid | Mamoulis, N=6701782749 | en_HK |
dc.identifier.scopusauthorid | Nes, N=24176412900 | en_HK |
dc.identifier.scopusauthorid | Kersten, M=7005064657 | en_HK |
dc.identifier.issnl | 0730-8078 | - |