Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors

Boris Aronov, Matthew J. Katz

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We describe a dynamic data structure for approximate nearest neighbor (ANN) queries with respect to multiplicatively weighted distances with additive offsets. Queries take polylogarithmic time, while the cost of updates is amortized polylogarithmic. The data structure requires near-linear space and construction time. The approach works not only for the Euclidean norm, but for other norms in Rd, for any fixed d. We employ our ANN data structure to construct a faster dynamic structure for approximate SINR queries, ensuring polylogarithmic query and polylogarithmic amortized update for the case of non-uniform power transmitters, thus closing a gap in previous state of the art. To obtain the latter result, we needed a data structure for dynamic approximate halfplane range counting in the plane. Since we could not find such a data structure in the literature, we also show how to dynamize one of the known static data structures.

    Original languageEnglish (US)
    Title of host publication18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022
    EditorsArtur Czumaj, Qin Xin
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959772365
    DOIs
    StatePublished - Jun 1 2022
    Event18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 - Torshavn, Faroe Islands
    Duration: Jun 27 2022Jun 29 2022

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume227
    ISSN (Print)1868-8969

    Conference

    Conference18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022
    Country/TerritoryFaroe Islands
    CityTorshavn
    Period6/27/226/29/22

    Keywords

    • Approximate nearest neighbors
    • Dynamic data structures
    • Nearest neighbor queries
    • Nearest neighbors
    • SINR queries
    • Weighted nearest neighbors

    ASJC Scopus subject areas

    • Software

    Fingerprint

    Dive into the research topics of 'Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors'. Together they form a unique fingerprint.

    Cite this