PAC Nearest Neighbor Queries: Approximate and Controlled Search in High-Dimensional and Metric Spaces
Contents
The Problem of Similarity Search
Correct Algorithms (C-NN)
Approximate NN Search
Index-based AC-NN Search
But, in High-Dim Spaces...
Why?
The PAC-NN Approach
PAC = AC + Probabilistic Bound
The NN Distance Distribution
How PAC Search Works (e=0)
How PAC Search Works (e>=0)
PAC-NN Sequential Algorithm
What about the Error?
PAC-NN Index-based Algorithm
Synthetic Data-sets
Cost and Quality of Result
Real datasets: Cost vs. Error
Example: Image DB (1)
Example: Image DB (2)
Example: Image DB (3)
Quality Control
Conclusions and Future Work
Contacting the Authors
Author: Marco Patella
E-mail: mpatella@deis.unibo.it
Home Page: http://www-db.deis.unibo.it/~mpatella