Improvements of two orders of magnitude were achieved for moderately approximated search results. A unique approximation approach has been applied to the similarity range and the nearest neighbours queries in metric data files. Previous designs have only considered the nearest neighbours search, sometimes even restricted to one neighbour. The approximation level is parametric, and precise response to similarity queries is achieved by specifying zero proximity threshold. The approach to computation of proximity keeps the approximated results probabilistically bound.
Experimental results demonstrate high precision and improvements of efficiency.
We have experimentally demonstrated the importance of precise proximity measures, the application of which can lead to effective and efficient approximations of similarity search. Though implementation is demonstrated by extending the M-tree, the approach is also applicable to other similarity search trees at small implementation costs. In the future, we plan to properly compare all existing approaches to approximation in uniform environment. We also hope to develop a system-user interface and apply the approach to real image and video archives. Finally, we intend to study the cases of iterative similarity search and complex approximated similarity search.