Approximate Distributed Metric-Space Search

GIL COSTA G. VERONICA; MAURICIO MARIN

Workshop; Large-Scale and Distributed Systems for Information Retrieval (LSDS-IR); 2011

This paper proposes approximate search algorithms for met-ric space search which are suitable for distributed searchengines. The desired level of approximation is a parame-ter that can be dynamically set in accordance with the ob-served query traffic. At steady state search engine operation,queries are responded with exact answers whereas at peaktraffic the proposed algorithms allow approximate answers.Our experimental results show that responding approximateanswers of very good quality reduces overall running time inabout 40%.