Approximate similarity search in metric data by using region proximity

The problem of approximated similarity search for the range and nearest neighbor queries is investigated for generic metric spaces. The search speedup is achieved by ignoring data regions with a small, user dened, proximity with respect to the query. For zero proximity, exact similarity search is performed. The problem of proximity of metric regions is explained and a probabilistic approach is applied. Approximated algorithms use a small amount of auxiliary data that can easily be maintained in main memory. The idea is implemented in a metric tree environment and experimentally evaluated on real-life les using specic performance measures. Improvements of two orders of magnitude can be achieved for moderately approximated search results. It is also demon- strated that the precision of data regions' proximity measure signicantly influence approximated algorithms.