Approximate Distributed Metric-Space Search

This paper proposes an approximate search algorithm for metric space search which is suitable for distributed search engines. The desired level of approximation is a parameter that can be dynamically set in accordance with the observed query traffic. At steady state search engine operation, the proposed algorithm calculates exact answers to queries whereas at peak traffic it calculates approximate answers. The search algorithm outperforms previous approaches in quality of results, memory space usage and running time. Our experimental results show that responding approximate answers of very good quality reduces average running time per query in about 40%. © 2011 ACM.