More Web Proxy on the site http://driver.im/

article

Free access

Enhanced nearest neighbour search on the R-tree

Authors:

King Lum Cheung,

Ada Wai-Chee FuAuthors Info & Claims

ACM SIGMOD Record, Volume 27, Issue 3

Pages 16 - 21

https://doi.org/10.1145/290593.290596

Published: 01 September 1998 Publication History

Abstract

Multimedia databases usually deal with huge amounts of data and it is necessary to have an indexing structure such that efficient retrieval of data can be provided. R-Tree with its variations, is a commonly cited indexing method. In this paper we propose an improved nearest neighbor search algorithm on the R-tree and its variants. The improvement lies in the removal of two hueristics that have been used in previous R*-tree work, which we prove cannot improve on the pruning power during a search.

References

[1]

N. Beckmann, Hans-Peter Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proceedings of the ACM SIGMOD International Conference on the Management of Data, pages 322-331, May 1990.

Digital Library

[2]

S. Berchtold, C. Bohm, B. Braunmuller, D. Keim, and H. P. Kriegel. Fast Parallel Similarity Search in Multimedia Databases. In Proceedings of the ACM SIGMOD International Conference on the Management of Data, 1997.

Digital Library

[3]

S. Berchtold, C. Bohm, D. Keim, and H. P. Kriegel. A Cost Model for Nearest Neighbor Search in High Dimensional Data Space. In Proceedings of the ACM PODS Symposium on Principles of Database Systems, 1997.

Digital Library

[4]

S. Berchtold, D. A. Keim, and Hans-Peter Kriegel. The X-tree: an index structure for high-dimensional data. In Proceedings of the 22nd International Conference on VLDB, 1996.

Digital Library

[5]

S. Brin. Near neighbor search in large metric space. In Proceedings of the 21st International Conference on VLDB, pages 574-584. 1995.

Digital Library

[6]

A. Brink, S. Marcus, and V. S. Subrahmanian. Heterogeneous Multimedia Reasoning. IEEE Computer, 28(9), September 1995.

Digital Library

[7]

Tzi-cker Chiueh. Content-based image indexing. In Proceedings of the 20th VLDB Conference, pages 582-593, 1994.

[8]

M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: the QBIC system. IEEE Computer, 28(9):23-32, September 1995.

Digital Library

[9]

J. H. Friedman, J. L. Bentley, and R. A. Finkel. An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software, 3(3):209-226, September 1977.

Digital Library

[10]

A. Guttman. R-trees: a dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD International Conference on the Management of Data, pages 47-57, June 1984.

[11]

King-ip Lin and C. Faloutsos. Fastmap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In Proceedings of ACM SIGMOD, 1995.

Digital Library

[12]

King-ip Lin, H. V. Jagadish, and C. Faloutsos. The TV-tree - an index structure for high-dimensional data. VLDB Journal, 3:517-542, October 1994.

[13]

V. E. Ogle. "Chabot: Retrieval from a Relational Database of Images. IEEE Computer, 28(9), September 1995.

Digital Library

[14]

N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proceedings of the ACM SIGMOD International Conference on the Management of Data, pages 71-79, June 1995.

Digital Library

[15]

H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.

Digital Library

[16]

T. Sellis, N. Roussopoulos, and C. Faloutsos. The R<sup>+</sup>-tree: a dynamic index for multidimensional objects. In Proceedings of the 13th International Conference on VLDB, pages 507-518. 1987.

[17]

D. A. White and R. Jain. Similarity indexing with the SS-tree. In Proceedings of the 12th IEEE International Conference on Data Engineering, pages 516-523, February 1996.

Digital Library

Cited By

Gür Y(2024)Consumer Price Index Forecasting in Turkey: A Comparison of Deep Learning and Machine Learning ApproachesIğdır Üniversitesi Sosyal Bilimler Dergisi10.54600/igdirsosbilder.1386274Online publication date: 10-May-2024
https://doi.org/10.54600/igdirsosbilder.1386274
Kim JHong SJeong SPark SYu K(2024)SGIR-Tree: Integrating R-Tree Spatial Indexing as Subgraphs in Graph Database Management SystemsISPRS International Journal of Geo-Information10.3390/ijgi1310034613:10(346)Online publication date: 27-Sep-2024
https://doi.org/10.3390/ijgi13100346
Liu ZDeep SFariha APsallidas FTiwari AFloratou A(2024)Rapidash: Efficient Detection of Constraint ViolationsProceedings of the VLDB Endowment10.14778/3659437.365945417:8(2009-2021)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659454
Show More Cited By

Index Terms

Enhanced nearest neighbour search on the R-tree
1. Information systems
  1. Information retrieval

Recommendations

Confirmation Sampling for Exact Nearest Neighbor Search
Similarity Search and Applications
Abstract
Locality-sensitive hashing (LSH), introduced by Indyk and Motwani in STOC ’98, has been an extremely influential framework for nearest neighbor search in high-dimensional data sets. While theoretical work has focused on the approximate nearest ...
Quality and efficiency in high dimensional nearest neighbor search
SIGMOD '09: Proceedings of the 2009 ACM SIGMOD International Conference on Management of data

Nearest neighbor (NN) search in high dimensional space is an important problem in many applications. Ideally, a practical solution (i) should be implementable in a relational database, and (ii) its query cost should grow sub-linearly with the dataset ...
Large scale nearest neighbor search -- theories, algorithms, and applications

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 27, Issue 3

Sept. 1, 1998

76 pages

ISSN:0163-5808

DOI:10.1145/290593

Editor:
Michael Franklin
Univ. of Maryland, College Park

Issue’s Table of Contents

Copyright © 1998 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1998

Published in SIGMOD Volume 27, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

139
Total Citations
View Citations
1,671
Total Downloads

Downloads (Last 12 months)309
Downloads (Last 6 weeks)50

Reflects downloads up to 02 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gür Y(2024)Consumer Price Index Forecasting in Turkey: A Comparison of Deep Learning and Machine Learning ApproachesIğdır Üniversitesi Sosyal Bilimler Dergisi10.54600/igdirsosbilder.1386274Online publication date: 10-May-2024
https://doi.org/10.54600/igdirsosbilder.1386274
Kim JHong SJeong SPark SYu K(2024)SGIR-Tree: Integrating R-Tree Spatial Indexing as Subgraphs in Graph Database Management SystemsISPRS International Journal of Geo-Information10.3390/ijgi1310034613:10(346)Online publication date: 27-Sep-2024
https://doi.org/10.3390/ijgi13100346
Liu ZDeep SFariha APsallidas FTiwari AFloratou A(2024)Rapidash: Efficient Detection of Constraint ViolationsProceedings of the VLDB Endowment10.14778/3659437.365945417:8(2009-2021)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659454
Li MWang HDai HLi MChai CGu RChen FChen ZLi SLiu QChen G(2024)A Survey of Multi-Dimensional Indexes: Past and Future TrendsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336418336:8(3635-3655)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3364183
Huang LGong YSui YZang XYuan B(2024)MOPED: Efficient Motion Planning Engine with Flexible Dimension Support2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00043(483-497)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00043
Li PDai HChen YLi BYang G(2023)Efficient Multi-source Contact Event Query Processing for Moving Objects2023 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM58522.2023.00132(1109-1114)Online publication date: 1-Dec-2023
https://doi.org/10.1109/ICDM58522.2023.00132
Wen ZLiang MHe BXia Z(2023)A High-Performance Index for Real-Time Matrix Retrieval (Extended Abstract)2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00305(3757-3758)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00305
Lu JZhao YWang ZWang G(2023)Skyline Micro-Cluster Query: A Novel and Practical Spatial Query2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00206(2686-2698)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00206
Liu JYinchai WWei FHan QTao YZhao LLi XSun H(2023)Secure Cloud-Aided Approximate Nearest Neighbor Search on High-Dimensional DataIEEE Access10.1109/ACCESS.2023.332145711(109027-109037)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3321457
Ma WZhao XIslam SNarkhede AWang K(2023)Efficient solution of bimaterial Riemann problems for compressible multi-material flow simulationsJournal of Computational Physics10.1016/j.jcp.2023.112474493(112474)Online publication date: Nov-2023
https://doi.org/10.1016/j.jcp.2023.112474
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents