|
ISCRIZIONE |
Similarity search: the metric space approach
Instructor: Prof. Pavel Zezula
Affiliation: Faculty of Informatics, Masaryk University in Brno, Czech Republic
Duration: 20 hours
Date: May 15 - May 19, 2006
Place: Dipartimento di Ingegneria dell'Informazione: Elettronica, Informatica, Telecomunicazioni, via Diotisalvi, meeting room
Contacts: Dott. Fausto Rabitti, Istituto di Scienza e Tecnologie dell’Informazione “A. Faedo” del CNR di Pisa
Contents
Part I: Metric searching in a nutshell
- Foundations of metric space searching (7 hours)
- distance searching problem in metric spaces
- metric distance measures
- similarity queries
- basic partitioning principles
- principles of similarity query execution
- policies to avoid distance computations
- metric space transformations
- principles of approximate similarity search
- advanced issues
- Survey of exiting approaches (3 hours)
- ball partitioning methods
- generalized hyper-plane partitioning approaches
- exploiting pre-computed distances
- hybrid indexing approaches
- approximated techniques
Part II: Metric searching in large collections of data
- Centralized index structures for large databases (4 hours)
- M-tree family
- hash-based metric indexing
- performance trials
- Approximate similarity search (2 hours)
- relative error approximation
- good fraction approximation
- small chance improvement approximation
- proximity-based approximation
- PAC nearest neighbor searching
- performance trials
- Parallel and distributed indexes (4 hours)
- preliminaries
- processing M-trees with parallel resources
- scalable and distributed similarity search
- performance trials
