Database Paper Browser

Back to papers

M-tree: An Efficient Access Method for Similarity Search in Metric Spaces

Summary: Proposes M-tree, a metric-space access method using distance bounds to organize data and support insertions and splits. Provides range and kNN queries; experiments show scalable, high-dimensional performance with reduced I/O and distance computations. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8443
Venue
VLDB
Year
1997
Pagerank
0.0005181666
Overall Rank
91 | 99.37%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 97 citing papers.

Rank Citing Paper Year Venue Pagerank
79 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056242144
155 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00040637896
270 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00029505642
358 On The Marriage of Lp-norms and Edit Distance 2004 VLDB 0.0002599481
598 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00019474545
802 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00016502317
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
1,776 Distributed Trajectory Similarity Search 2017 VLDB 0.00010593716
1,811 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010467197
1,816 Incremental Clustering for Mining in a Data Warehousing Environment 1998 VLDB 0.0001045313
1,854 Distance-based Outlier Detection in Data Streams 2016 VLDB 0.00010317762
2,115 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 9.5257379e-05
2,324 RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search 2024 SIGMOD 9.0326444e-05
2,477 Identifying Similarities, Periodicities and Bursts for Online Search Queries 2004 SIGMOD 8.6941234e-05
2,495 STRG-Index: Spatio-Temporal Region Graph Indexing for Large Video Databases 2005 SIGMOD 8.6488427e-05
2,740 String Similarity Joins: An Experimental Evaluation 2014 VLDB 8.1980628e-05
2,784 Approximate XML Joins 2002 SIGMOD 8.128931e-05
2,811 High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations 2023 SIGMOD 8.0806307e-05
2,933 Answering Top-k Queries Using Views 2006 VLDB 7.8679669e-05
2,971 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7970531e-05
3,012 NETS: Extremely Fast Outlier Detection from a Data Stream via Set-Based Processing 2019 VLDB 7.7153586e-05
3,183 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 7.4228241e-05
3,225 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 7.3463484e-05
3,300 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2516103e-05
3,400 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 7.1405533e-05
3,468 Real-Time Distance-Based Outlier Detection in Data Streams 2021 VLDB 7.0686044e-05
3,510 Inter-Media Hashing for Large-scale Retrieval from Heterogeneous Data Sources 2013 SIGMOD 7.0258619e-05
3,629 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 6.902069e-05
3,664 FALCON: Feedback Adaptive Loop for Content-Based Retrieval 2000 VLDB 6.8636265e-05
3,774 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7757301e-05
3,920 Continuous Outlier Detection in Data Streams: An Extensible Framework and State-Of-The-Art Algorithms 2013 SIGMOD 6.6309693e-05
4,070 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.4784181e-05
4,278 Similarity Query Processing for High-Dimensional Data 2020 VLDB 6.2953764e-05
4,501 TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data 2022 SIGMOD 6.137686e-05
4,551 iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search 2024 SIGMOD 6.092287e-05
4,564 Learning User Preferences By Adaptive Pairwise Comparison 2015 VLDB 6.0819005e-05
4,598 Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search 2025 SIGMOD 6.0586236e-05
4,652 On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection 2021 VLDB 6.0228549e-05
4,985 Pivot-based Metric Indexing 2017 VLDB 5.7856648e-05
5,184 SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search 2025 SIGMOD 5.6406991e-05
5,310 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 5.5753015e-05
5,328 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 5.5665496e-05
5,344 FeedbackBypass: A New Approach to Interactive Similarity Query Processing 2001 VLDB 5.5576339e-05
5,508 Fast Large-Scale Trajectory Clustering 2020 VLDB 5.4713696e-05
5,738 Hercules Against Data Series Similarity Search 2022 VLDB 5.3478528e-05
5,758 Top-k Nearest Neighbor Search In Uncertain Data Series 2015 VLDB 5.339397e-05
6,074 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 5.2242306e-05
6,360 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.0961051e-05
6,376 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 5.0916875e-05
6,464 Reference-Based Indexing of Sequence Databases 2006 VLDB 5.0532607e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
65 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00062029383
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
242 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00031110894
471 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00022364776
575 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00019882723
708 Near Neighbor Search in Large Metric Spaces 1995 VLDB 0.00017772684
1,293 Content-Based Image Indexing 1994 VLDB 0.00012783639
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,807 Indexing for Subtree Similarity-Search using Edit Distance 2013 SIGMOD 4.9217776e-05
1,945 Multidimensional Access Methods: Trees Have Grown Everywhere 1997 VLDB 0.00010001003
8,123 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 4.5801104e-05
10,180 LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces 2026 SIGMOD 4.1945683e-05
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
3,199 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3927291e-05
9,283 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 4.3631652e-05
708 Near Neighbor Search in Large Metric Spaces 1995 VLDB 0.00017772684
575 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00019882723
1,811 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010467197