A Cost Model for Similarity Queries in Metric Spaces

The Problem

Cost Models for SAMs

A 2-dim Example (R-tree)

Cost Model for R-trees: window queries

Distance Distributions

An example

Using Distance Distributions

An Example (edit distance)

The M-Tree (VLDB '97)

Cost for a Range Query

Node-based and Level-based MCMs

Nearest Neighbors Queries

Experimental Results (synthetic dataset)

Experimental Results (real datasets)

Conclusions

Future Work

Contacting the Authors

Author: Marco Patella

E-mail: mpatella@deis.unibo.it

Home Page: http://www-db.deis.unibo.it/~mpatella