•Similarity Search:
•Part I, Chapter 1
•‹#›
SIMILARITY SEARCH
The Metric Space Approach
Pavel Zezula, Giuseppe Amato,
Vlastislav Dohnal, Michal Batko

•Similarity Search:
•Part I, Chapter 1
•‹#›
•Similarity Search:
•Part I, Chapter 1
•2
Table of Content
nPart I: Metric searching in a nutshell
nFoundations of metric space searching
nSurvey of exiting approaches
n
nPart II: Metric searching in large collections
nCentralized index structures
nApproximate similarity search
nParallel and distributed indexes

•Similarity Search:
•Part I, Chapter 1
•‹#›
•Similarity Search:
•Part I, Chapter 1
•3
Approximate Similarity Search
1.relative error approximation
2.good fraction approximation
3.small chance improvement approximation
4.proximity-based approximation
5.PAC nearest neighbor searching
6.performance trials