Approximate nearest neighbor algorithms for Hausdorff metrics via embeddings

Martin Farach-Colton, Piotr Indyk

    Research output: Contribution to journalConference articlepeer-review


    Hausdorff metrics are used in geometric settings for measuring the distance between sets of points. They have been used extensively in areas such as computer vision, pattern recognition and computational chemistry. While computing the distance between a single pair of sets under the Hausdorff metric has been well studied, no results were known for the Nearest Neighbor problem under Hausdorff metrics. Indeed, no results were known for the nearest neighbor problem for any metric without norm structure, of which the Hausdorff is one. We present the first nearest neighbor algorithm for the Hausdorff metric. We achieve our result by embedding Hausdorff metrics into l and using known nearest neighbor algorithms for this target metric. We give upper and lower bounds on the number of dimensions needed for such an l embedding. Our bounds require the introduction of new techniques based on superimposed codes and non-uniform sampling.

    Original languageEnglish (US)
    Pages (from-to)171-179
    Number of pages9
    JournalAnnual Symposium on Foundations of Computer Science - Proceedings
    StatePublished - 1999
    EventProceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA
    Duration: Oct 17 1999Oct 19 1999

    ASJC Scopus subject areas

    • Hardware and Architecture


    Dive into the research topics of 'Approximate nearest neighbor algorithms for Hausdorff metrics via embeddings'. Together they form a unique fingerprint.

    Cite this