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

Paolo CiacciaMarco PatellaPavel Zezula

article1997VLDB1,974 citations

Presents the M-tree, a dynamic and balanced indexing structure designed for metric spaces that optimizes both disk I/O and distance computations during range and k-nearest neighbor similarity searches.

Listen

Modern database systems increasingly manage complex multimedia formats, such as audio, images, video, and text sequences, that require similarity search based on intricate distance functions. Existing spatial access methods rely heavily on vector representations and standard coordinate metrics, failing when features cannot be mapped to vector spaces or when distance evaluations are computationally expensive. Conversely, traditional metric trees handle general distance metrics but remain static, requiring costly periodic reorganizations and ignoring disk access costs. The article introduces and evaluates the M-tree, a dynamic, balanced access method designed to support similarity search across generic metric spaces while optimizing both computational distance operations and disk input-output costs.

To evaluate the system, the authors implemented the M-tree within the Generalized Search Tree framework and conducted extensive experiments on synthetic clustered datasets ranging up to fifty dimensions and up to 100,000 objects. They evaluated range and nearest neighbor search algorithms, tested various node-split strategies, and benchmarked performance against standard R*-trees.

Key findings show that the M-tree scales logarithmically during similarity searches as datasets grow from 10,000 to 100,000 objects, maintaining balance dynamically without structural degradation. In contrast to balanced node partitioning, unbalanced generalized hyperplane partitioning produced significantly smaller tree volumes and reduced processing costs, avoiding volume inflation of up to 4.6 times seen in low dimensions. Implementing triangle inequality pruning optimizations saved up to 40% of distance computations during range and nearest neighbor queries. Non-confirmed split policies, which re-evaluate parent routing objects during node splits, outperformed confirmed policies by saving up to 25% of disk reads in high dimensions. Finally, comparative evaluations demonstrated that the M-tree achieved lower disk access costs and fewer distance computations than the established R*-tree, even in traditional vector environments.

These results establish that multimedia databases can support fast similarity searching without sacrificing dynamic insertions or database scalability. System architects can select node-split policies based on specific workload constraints, trading off build-time computational complexity for runtime query speed. For high-capacity nodes and computationally expensive distance functions, sophisticated split policies minimize query overhead, whereas cheaper random or sampling policies minimize initial construction costs.

Organizations developing multimedia retrieval platforms should adopt the M-tree framework to enable dynamic indexing of non-vector data. Future implementations should explore variable-size node designs, load parallelization across processors and storage, and testing on real-world applications such as protein matching and biometric identification. While findings demonstrate high confidence under the evaluated synthetic distributions, practitioners should note that node size was held constant at 4 kilobytes and real-world performance will depend on the computational intensity and overlap characteristics of domain-specific distance metrics.

CNUCE-CNR DEIS - CSITE-CNR high dimensional data k-nearest neighbors metric spaces similarity search M-tree metric spaces

Ciaccia et al (1997).pdf

Paper: R-trees: a dynamic index structure for spatial searching, Antonin Guttman (1984). Introduces the foundational dynamic, height-balanced spatial index tree that M-tree directly adapts and generalizes to non-vector metric spaces.
Paper: The R*-tree: an efficient and robust access method for points and rectangles, Norbert Beckmann et al. (1990). Provides key principles of dynamic node splitting and overflow management that inspired the balancing heuristics in M-tree.
Paper: Comparing Images Using the Hausdorff Distance, Daniel P. Huttenlocher et al. (1993). Presents a classic complex metric space distance function that motivates the need for general metric indexing structures like the M-tree.

Paper: Similarity Search in High Dimensions via Hashing, A. Gionis et al. (1999). Introduces locality-sensitive hashing to overcome performance limitations and the curse of dimensionality inherent in tree-based high-dimensional similarity search.
Paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, Yu. A. Malkov et al. (2016). Advances metric and high-dimensional nearest neighbor search beyond tree structures using hierarchical navigable small-world graphs for scalable approximate queries.
Paper: The Earth Mover's Distance as a Metric for Image Retrieval, YOSSI RUBNER et al. (2000). Formulates the Earth Mover's Distance for image retrieval, providing a prominent non-vector metric space application directly suited for metric indexing structures.
Paper: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, Suhas Jayaram Subramanya et al. (2019). Extends scalable disk-resident nearest neighbor indexing architectures to billion-scale datasets using graph-based representations.
Paper: Efficient algorithms for mining outliers from large data sets, S. Ramaswamy et al. (2000). Applies multi-dimensional and metric nearest-neighbor search mechanisms to the problem of scalable distance-based outlier detection.

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

Abstract

A new access method, called M-tree, is proposed to organize and search large data sets from a generic "metric space", i.e. where object proximity is only defined by a distance function satisfying the positivity, symmetry, and triangle inequality postulates. We detail algorithms for insertion of objects and split management, which keep the M-tree always balanced - several heuristic split alternatives are considered and experimentally evaluated. Algorithms for similarity (range and k-nearest neighbors) queries are also described. Results from extensive experimentation with a prototype system are reported, considering as the performance criteria the number of page I/O's and the number of distance computations. The results demonstrate that the M-tree indeed extends the domain of applicability beyond the traditional vector spaces, performs reasonably well in high-dimensional data spaces, and scales well in case of growing files.

Topics

high dimensional data k-nearest neighbors metric spaces triangle inequality tabu search parallel computation semantic similarity

Keywords

1 Introduction
2 Preliminaries
3 The M-tree
3.1 The Structure of M-tree Nodes
3.2 Processing Similarity Queries
3.2.1 Range Queries
3.2.2 Nearest Neighbor Queries
3.3 Building the M-tree
3.4 Split Management
4 Split Policies
4.1 Choosing the Routing Objects
4.2 Distribution of the Entries
5 Experimental Results
5.1 Comparing M-tree and R*-tree
6 Conclusions
Acknowledgements
References

Knowls

Knowl 1 — Structure and Node Organization of the M-tree
model/method
The M-tree is a balanced, paged, dynamic metric access method designed for secondary memory. It partitions indexed objects on the basis of their relative distances measured by a black-box metric distance function $d: \mathcal{D} \times \mathcal{D} \to \mathbb{R}^+$ defined over a feature domain $\mathcal{D}$ . An M-tree consists of fixed-size nodes organized into leaves and internal nodes:
1. Leaf Nodes: Contain entries of the form $[O_j, \text{oid}(O_j), d(O_j, P(O_j))]$ , where $O_j \in \mathcal{D}$ is the indexed object's feature key, $\text{oid}(O_j)$ is an identifier providing access to the database record, and $d(O_j, P(O_j))$ is the precomputed distance from $O_j$ to its parent routing object $P(O_j)$ in the parent node.
2. Internal Nodes: Contain routing object entries of the form $[O_r, \text{ptr}(T(O_r)), r(O_r), d(O_r, P(O_r))]$ , where $O_r \in \mathcal{D}$ is a promoted database object acting as a cluster representative, $\text{ptr}(T(O_r))$ points to the root of the covering subtree $T(O_r)$ , $r(O_r) > 0$ is the covering radius defining the bounding ball around $O_r$ , and $d(O_r, P(O_r))$ is the distance to its own parent routing object (undefined for root entries).
The covering radius guarantees that every object $O_j$ residing in the covering subtree $T(O_r)$ satisfies: $d(O_j, O_r) \le r(O_r)$
Knowl 2 — Metric Pruning Conditions Using Stored Parent Distances
theoretical result
Let $(\mathcal{D}, d)$ be a metric space, $Q \in \mathcal{D}$ be a query object, and $r(Q) \ge 0$ be the search radius. For any routing object $O_r$ stored in node $N$ with parent object $O_p = P(O_r)$ and covering radius $r(O_r)$ , the triangle inequality yields two pruning criteria:
1. Subtree Pruning Criterion: If $d(O_p, Q) > r(Q) + r(O_r)$ then for every object $O_j$ in the subtree $T(O_r)$ , $d(O_j, Q) > r(Q)$ . Consequently, the subtree $T(O_r)$ cannot contain qualifying objects and can be pruned.
2. Distance Computation Avoidance Criterion: If $|d(O_p, Q) - d(O_r, O_p)| > r(Q) + r(O_r)$ then $d(O_r, Q) > r(Q) + r(O_r)$ . This implies that the subtree $T(O_r)$ can be safely pruned without evaluating the metric distance $d(O_r, Q)$ , utilizing only the precomputed parent distance $d(O_r, O_p)$ and the already computed query-to-parent distance $d(O_p, Q)$ .
For a database object $O_j$ in a leaf node with parent $O_p = P(O_j)$ , if $|d(O_p, Q) - d(O_j, O_p)| > r(Q)$ , then $d(O_j, Q) > r(Q)$ , allowing $O_j$ to be pruned without computing $d(O_j, Q)$ .
Knowl 3 — M-tree Range Query Algorithm
algorithm
The range search algorithm RS retrieves all database objects $O_j$ such that $d(O_j, Q) \le r(Q)$ , traversing the M-tree starting at the root node. It exploits precomputed parent distances to avoid distance computations via the triangle inequality.
Algorithm RS(N, Q, r(Q))
Input: Node N, query object Q, search radius r(Q)
Output: Set of object identifiers qualifying for the range query
let O_p be the parent routing object of node N
if N is not a leaf then
    for each routing entry O_r in N do
        if |d(O_p, Q) - d(O_r, O_p)| <= r(Q) + r(O_r) then
            Compute d(O_r, Q)
            if d(O_r, Q) <= r(Q) + r(O_r) then
                RS(*ptr(T(O_r)), Q, r(Q))
else
    for each leaf entry O_j in N do
        if |d(O_p, Q) - d(O_j, O_p)| <= r(Q) then
            Compute d(O_j, Q)
            if d(O_j, Q) <= r(Q) then
                add oid(O_j) to result
For the root node, $O_p$ is undefined, so distance evaluation to root routing objects cannot be bypassed using parent distance bounds.
Knowl 4 — M-tree k-Nearest Neighbor Query Algorithm
algorithm
The $k$ -nearest neighbors search algorithm finds the $k$ objects in the M-tree closest to a query object $Q$ using a branch-and-bound traversal with a priority queue PR and an array NN of size $k$ initialized with distances $\infty$ . The distance of the $k$ -th neighbor in NN acts as a dynamic search radius $d_k$ .

For each active subtree $T(O_r)$ , lower and upper bounds on the distance between $Q$ and any object in $T(O_r)$ are defined as: $d_{\min}(T(O_r)) = \max\{d(O_r, Q) - r(O_r), 0\}$ $d_{\max}(T(O_r)) = d(O_r, Q) + r(O_r)$
Algorithm k-NNSearch(T_root, Q, k)
Input: Root node T_root, query object Q, integer k >= 1
Output: Array NN containing the k nearest objects and their distances from Q
Initialize priority queue PR with [ptr(T_root), 0]
for i = 1 to k do
    NN[i] = [undefined, infinity]
while PR is not empty do
    Remove entry [ptr(N), d_min] with minimal d_min from PR
    k-NNNodeSearch(N, Q, k)
Algorithm k-NNNodeSearch(N, Q, k)
let O_p be the parent routing object of node N
if N is not a leaf then
    for each routing entry O_r in N do
        if |d(O_p, Q) - d(O_r, O_p)| <= d_k + r(O_r) then
            Compute d(O_r, Q)
            if d_min(T(O_r)) <= d_k then
                Add [ptr(T(O_r)), d_min(T(O_r))] to PR
                if d_max(T(O_r)) < d_k then
                    Insert [undefined, d_max(T(O_r))] into NN and update d_k
                    Remove from PR all entries with d_min(T(O_r)) > d_k
else
    for each leaf entry O_j in N do
        if |d(O_p, Q) - d(O_j, O_p)| <= d_k then
            Compute d(O_j, Q)
            if d(O_j, Q) <= d_k then
                Insert [oid(O_j), d(O_j, Q)] into NN and update d_k
                Remove from PR all entries with d_min(T(O_r)) > d_k
Knowl 5 — M-tree Object Insertion Algorithm
algorithm
The Insert algorithm traverses the M-tree top-down from the root to locate the best leaf node for inserting a new entry $O_n$ . At each internal node $N$ , it selects the child branch that minimizes routing region volume expansion:
Algorithm Insert(N, entry(O_n))
Input: Current node N, entry to insert entry(O_n)
if N is not a leaf then
    let N_in = {O_r in N | d(O_r, O_n) <= r(O_r)}
    if N_in is not empty then
        Find entry(O_r*) in N_in such that d(O_r*, O_n) is minimized
    else
        Find entry(O_r*) in N such that d(O_r*, O_n) - r(O_r*) is minimized
        r(O_r*) = d(O_r*, O_n)
    Insert(*ptr(T(O_r*)), entry(O_n))
else
    if N is not full then
        Store entry(O_n) in N
    else
        Split(N, entry(O_n))
To identify entries belonging to $N_{\text{in}}$ without computing all distances, the condition $|d(O_n, O_p) - d(O_r, O_p)| > r(O_r)$ can be checked; if it holds, then $d(O_r, O_n) > r(O_r)$ , proving $O_r \notin N_{\text{in}}$ without evaluating $d(O_r, O_n)$ .
Knowl 6 — M-tree Node Split and Covering Radius Computation
algorithm
When an insertion overflows a node $N$ , the Split procedure partitions the entries of $N \cup \{E\}$ into two sets $N_1$ and $N_2$ allocated to $N$ and a new node $N'$ , and promotes two routing objects $O_{p_1}$ and $O_{p_2}$ to the parent node $N_p$ :
Algorithm Split(N, E)
Input: Overflown node N, new entry E
let N_set = entries of node N union {E}
Allocate new node N'
Promote(N_set, O_p1, O_p2)
Partition(N_set, O_p1, O_p2, N_1, N_2)
Store N_1 entries in N, and N_2 entries in N'
Compute covering radii r(O_p1) and r(O_p2)
if N is the root then
    Allocate new root node N_p
    Store entry(O_p1) and entry(O_p2) in N_p
else
    Replace entry(O_p) with entry(O_p1) in N_p
    if N_p is full then
        Split(N_p, entry(O_p2))
    else
        Store entry(O_p2) in N_p
The covering radius $r(O_{p_1})$ of a promoted object (and similarly for $r(O_{p_2})$ ) is updated depending on node type:
- If $N$ is a leaf node: $r(O_{p_1}) = \max_{O_j \in N_1} \{d(O_j, O_{p_1})\}$
- If $N$ is an internal node: $r(O_{p_1}) = \max_{O_r \in N_1} \{d(O_r, O_{p_1}) + r(O_r)\}$
Knowl 7 — Routing Object Promotion Policies for M-tree Node Splits
model/method
The Promote method chooses two routing objects $O_{p_1}, O_{p_2} \in \mathcal{N}$ during a node split. Promotion strategies are categorized by whether they confirm the existing parent object:
1. Confirmed vs. Non-Confirmed: A confirmed policy sets $O_{p_1} = O_p$ (the parent object of the split node) and only selects $O_{p_2}$ , reducing distance computation costs. Non-confirmed policies select both $O_{p_1}$ and $O_{p_2}$ freely from $\mathcal{N}$ .
2. Promotion Algorithms:
  - m_RAD: Evaluates all possible pairs of objects in $\mathcal{N}$ , partitions entries, and promotes the pair minimizing the sum of covering radii: $r(O_{p_1}) + r(O_{p_2})$ .
  - mM_RAD: Similar to m_RAD, but minimizes the maximum of the two covering radii: $\max\{r(O_{p_1}), r(O_{p_2})\}$ .
  - M_LB_DIST: Uses only precomputed stored distances without additional metric evaluations. In confirmed mode ( $O_{p_1} = O_p$ ), it chooses $O_{p_2}$ as the object farthest from $O_p$ : $d(O_{p_2}, O_p) = \max_j \{d(O_j, O_p)\}$
  - RANDOM: Selects routing object(s) uniformly at random from $\mathcal{N}$ .
  - SAMPLING: Samples a subset of size $s > 1$ (e.g., $s = \lfloor M/10 \rfloor$ where $M$ is node capacity), evaluates all pairs in the sample, and selects the pair minimizing $\max\{r(O_{p_1}), r(O_{p_2})\}$ .
Knowl 8 — Entry Distribution Policies for Node Overflows
model/method
Given two promoted routing objects $O_{p_1}$ and $O_{p_2}$ , the Partition method assigns the remaining entries in $\mathcal{N}$ to $N_1$ and $N_2$ using one of two strategies:
1. Generalized Hyperplane Partitioning (Unbalanced): Assigns each entry $O_j \in \mathcal{N}$ to the closest routing object: $\text{Assign } O_j \text{ to } N_1 \iff d(O_j, O_{p_1}) \le d(O_j, O_{p_2}), \quad \text{otherwise to } N_2$ This approach allows unbalanced node sizes but yields smaller covering radii and less overlapping volume.
2. Balanced Partitioning: Computes $d(O_j, O_{p_1})$ and $d(O_j, O_{p_2})$ for all entries and alternates assigning the closest remaining entry in $\mathcal{N}$ to $N_1$ (closest to $O_{p_1}$ ) and $N_2$ (closest to $O_{p_2}$ ) until $\mathcal{N}$ is empty.
Because balanced splits enforce equal node occupancies in a metric space, they inflate the covering radii across all dimensions, resulting in significant volume overhead.

Knowl 9 — Performance Overhead of Balanced vs. Generalized Hyperplane Partitioning

data/table

Empirical evaluation of range queries with search radius $r(Q) = \frac{1}{2}\sqrt[\text{Dim}]{0.04}$ on synthetic clustered datasets ( $10^4$ objects, 10 clusters, variance $\sigma^2 = 0.1$ , $L_\infty$ metric) shows that the Balanced partition strategy introduces severe volume, CPU, and I/O overhead relative to the Generalized Hyperplane strategy:

Metric	RANDOM_1	SAMPLING_1	M_LB_DIST_1	RANDOM_2	m_RAD_2
Dim = 2
Volume overhead	4.60	4.38	3.90	4.07	1.69
Dist. overhead, I/O overhead	2.27, 2.11	1.97, 1.76	1.93, 1.57	2.09, 1.96	1.40, 1.30
Dim = 10
Volume overhead	1.63	1.31	1.49	2.05	2.40
Dist. overhead, I/O overhead	1.58, 1.18	1.38, 0.92	1.34, 0.91	1.55, 1.39	1.69, 1.12

In all cases (suffix _1 indicating confirmed and _2 non-confirmed policies), the volume overhead—defined as the ratio of total volume covered by routing objects in the Balanced tree to that in the Generalized Hyperplane tree—is significantly greater than 1 (up to 4.60 in 2D), which directly translates to 1.34 $\times$ to 2.27 $\times$ more distance computations and higher I/O page reads.

Knowl 10 — Scalability of M-tree and Performance Comparison with R*-tree
empirical result
Experiments evaluating M-tree scalability and comparing it to $R^*$ -tree across varying dataset sizes ( $10^4$ to $10^5$ objects) and dimensionalities ( $ext{Dim} = 2$ to $50$ ) using synthetic clustered distributions under $L_\infty$ demonstrate the following:
1. Scalability with Data Size: Average construction costs for 2-D data using the RANDOM_2 split policy scale smoothly from $45.0$ distance computations and $8.9$ I/Os per object at $10^4$ objects to $74.7$ distance computations and $9.8$ I/Os per object at $10^5$ objects. The 10-NN query costs in both I/O and distance computations grow logarithmically with the number of indexed objects.
2. Metric Pruning Savings: Using precomputed parent distances to avoid distance computations during search (via Lemma 3.2) saves up to $40\%$ of distance calculations in range and $k$ -NN queries across all split policies.
3. Comparison with $R^*$ -tree: When indexing vector spaces, M-tree achieves lower I/O search costs than $R^*$ -tree on square range queries. In CPU distance evaluations, M-tree with metric pruning substantially outperforms $R^*$ -tree, demonstrating that M-tree is competitive even on standard multi-dimensional vector data.

Coverage note — Deletions and node underflow handling algorithms were omitted because the paper itself explicitly omitted them due to space constraints.

References

1.R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. FODO'93, pp. 69-84, Chicago, IL, Oct. 1993. Springer LNCS, Vol. 730.
2.S. Berchtold, D.A. Keim, and H.-P. Kriegel. The X-tree: An index structure for high-dimensional data. 22nd VLDB, pp. 28-39, Mumbai (Bombay), India, Sept. 1996.
3.N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. ACM SIGMOD, pp. 322-331, Atlantic City, NJ, May 1990.
4.T. Bozkaya and M. Ozsoyoglu. Distance-based indexing for high-dimensional metric spaces. ACM SIGMOD, pp. 357-368, Tucson, AZ, May 1997.
5.S. Brin. Near neighbor search in large metric spaces. 21st VLDB, pp. 574-584, Zurich, Switzerland, Sept. 1995.
6.T. Chiueh. Content-based image indexing. 20th VLDB, pp. 582-593, Santiago, Chile, Sept. 1994.
7.C. Faloutsos, W. Equitz, M. Flickner, W. Niblack, D. Petkovic, and R. Barber. Efficient and effective querying by image content. J. of Intell. Inf. Sys., 3(3/4):231-262, July 1994.
8.C. Faloutsos and K.-I. Lin. FastMap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. ACM SIGMOD, pp. 163-174, San Jose, CA, June 1995.
9.C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. ACM SIGMOD, pp. 419-429, Minneapolis, MN, May 1994.
10.A. Guttman. R-trees: A dynamic index structure for spatial searching. ACM SIGMOD, pp. 47-57, Boston, MA, June 1984.
11.J.M. Hellerstein, J.F. Naughton, and A. Pfeffer. Generalized search trees for database systems. 21st VLDB, Zurich, Switzerland, Sept. 1995.
12.A.K. Jain and R.C. Dubes. Algorithms for Clustering Data. Prentice-Hall, 1988.
13.N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. ACM SIGMOD, pp. 71-79, San Jose, CA, May 1995.
14.T.K. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-tree: A dynamic index for multi-dimensional objects. 13th VLDB, pp. 507-518, Brighton, England, Sept. 1987.
15.J.K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Inf. Proc. Lett., 40(4):175-179, Nov. 1991.
16.M. Vassilakopoulos and Y. Manolopoulos. Dynamic inverted quadtree: A structure for pictorial databases. Inf. Sys., 20(6):483-500, Sept. 1995.
17.E. Wold, T. Blum, D. Keislar, and J. Wheaton. Content-based classification, search, and retrieval of audio. IEEE Multimedia, 3(3):27-36, 1996.
18.P. Zezula, P. Ciaccia, and F. Rabitti. M-tree: A dynamic index for similarity queries in multimedia databases. TR 7, HERMES ESPRIT LTR Project, 1996. Available at URL http://www.ced.tuc.gr/hermes/.

Citation

MLA

Ciaccia, P., et al. “M-tree: An Efficient Access Method for Similarity Search in Metric Spaces”. Very Large Data Bases, 1997, pp. 426–35, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1108.

APA

Ciaccia, P., Patella, M., & Zezula, P. (1997). M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. Very Large Data Bases, 426–435. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1108

Chicago

Ciaccia, P., M. Patella, and P. Zezula. 1997. “M-tree: An Efficient Access Method for Similarity Search in Metric Spaces”. Very Large Data Bases, 426–35. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1108.

Harvard

Ciaccia, P., Patella, M. and Zezula, P. (1997) “M-tree: An Efficient Access Method for Similarity Search in Metric Spaces”, Very Large Data Bases, pp. 426–435. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1108.

Vancouver

1. Ciaccia P, Patella M, Zezula P (1997) M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. Very Large Data Bases 426–435

BibTeX

@article{ciaccia1997tree,
  title = {M-tree: An Efficient Access Method for Similarity Search in Metric Spaces},
  author = {Ciaccia, Paolo and Patella, Marco and Zezula, Pavel},
  year = {1997},
  journal = {Very Large Data Bases},
  pages = {426-435},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1108}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Structure and Node Organization of the M-tree

Knowl 2 — Metric Pruning Conditions Using Stored Parent Distances

Knowl 3 — M-tree Range Query Algorithm

Knowl 4 — M-tree k-Nearest Neighbor Query Algorithm

Knowl 5 — M-tree Object Insertion Algorithm

Knowl 6 — M-tree Node Split and Covering Radius Computation

Knowl 7 — Routing Object Promotion Policies for M-tree Node Splits

Knowl 8 — Entry Distribution Policies for Node Overflows

Knowl 9 — Performance Overhead of Balanced vs. Generalized Hyperplane Partitioning

Knowl 10 — Scalability of M-tree and Performance Comparison with R*-tree

References

Citation

BibTeX

Access the Paper