Reverse Approximate Nearest Neighbor Queries

Arif Hidayat, Shiyu Yang, Muhammad Aamir Cheema, David Taniar

    Research output: Contribution to journalArticleResearchpeer-review

    1 Citation (Scopus)

    Abstract

    Given a set of facilities and a set of users, a reverse nearest neighbors (RNN) query retrieves every user u for which thequery facility q is its closest facility. Since q is the closest facility to u, the user u is said to be influenced by q. In this paper, we propose arelaxed definition of influence where a user u is said to be influenced by not only its closest facility but also every other facility that isalmost as close to u as its closest facility is. Based on this definition of influence, we propose reverse approximate nearest neighbors(RANN) queries. Formally, given a valuex 1, an RANN query q returns every user u for which distu; qbx NNDistub whereNNDistub denotes the distance between a user u and its nearest facility, i.e., q is an approximate nearest neighbor of u. In this paper,we study both snapshot and continuous versions of RANN queries. In a snapshot RANN query, the underlying data sets do not changeand the results of a query are to be computed only once. In the continuous version, the users continuously change their locations andthe results of RANN queries are to be continuously monitored. Based on effective pruning techniques and several non-trivialobservations, we propose efficient RANN query processing algorithms for both the snapshot and continuous RANN queries. Weconduct extensive experiments on both real and synthetic data sets and demonstrate that our algorithm for both snapshot andcontinuous queries are significantly better than the competitors.

    Original languageEnglish
    Article number8081813
    Pages (from-to)339-352
    Number of pages14
    JournalIEEE Transactions on Knowledge and Data Engineering
    Volume30
    Issue number2
    DOIs
    Publication statusPublished - 1 Feb 2018

    Keywords

    • continuous monitoring
    • influence detection
    • Reverse nearest neighbors
    • voronoi diagram

    Cite this

    @article{8d7823851f064feeaa4fa046b43c2431,
    title = "Reverse Approximate Nearest Neighbor Queries",
    abstract = "Given a set of facilities and a set of users, a reverse nearest neighbors (RNN) query retrieves every user u for which thequery facility q is its closest facility. Since q is the closest facility to u, the user u is said to be influenced by q. In this paper, we propose arelaxed definition of influence where a user u is said to be influenced by not only its closest facility but also every other facility that isalmost as close to u as its closest facility is. Based on this definition of influence, we propose reverse approximate nearest neighbors(RANN) queries. Formally, given a valuex 1, an RANN query q returns every user u for which distu; qbx NNDistub whereNNDistub denotes the distance between a user u and its nearest facility, i.e., q is an approximate nearest neighbor of u. In this paper,we study both snapshot and continuous versions of RANN queries. In a snapshot RANN query, the underlying data sets do not changeand the results of a query are to be computed only once. In the continuous version, the users continuously change their locations andthe results of RANN queries are to be continuously monitored. Based on effective pruning techniques and several non-trivialobservations, we propose efficient RANN query processing algorithms for both the snapshot and continuous RANN queries. Weconduct extensive experiments on both real and synthetic data sets and demonstrate that our algorithm for both snapshot andcontinuous queries are significantly better than the competitors.",
    keywords = "continuous monitoring, influence detection, Reverse nearest neighbors, voronoi diagram",
    author = "Arif Hidayat and Shiyu Yang and Cheema, {Muhammad Aamir} and David Taniar",
    year = "2018",
    month = "2",
    day = "1",
    doi = "10.1109/TKDE.2017.2766065",
    language = "English",
    volume = "30",
    pages = "339--352",
    journal = "IEEE Transactions on Knowledge and Data Engineering",
    issn = "1041-4347",
    publisher = "IEEE, Institute of Electrical and Electronics Engineers",
    number = "2",

    }

    Reverse Approximate Nearest Neighbor Queries. / Hidayat, Arif; Yang, Shiyu; Cheema, Muhammad Aamir; Taniar, David.

    In: IEEE Transactions on Knowledge and Data Engineering, Vol. 30, No. 2, 8081813, 01.02.2018, p. 339-352.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - Reverse Approximate Nearest Neighbor Queries

    AU - Hidayat, Arif

    AU - Yang, Shiyu

    AU - Cheema, Muhammad Aamir

    AU - Taniar, David

    PY - 2018/2/1

    Y1 - 2018/2/1

    N2 - Given a set of facilities and a set of users, a reverse nearest neighbors (RNN) query retrieves every user u for which thequery facility q is its closest facility. Since q is the closest facility to u, the user u is said to be influenced by q. In this paper, we propose arelaxed definition of influence where a user u is said to be influenced by not only its closest facility but also every other facility that isalmost as close to u as its closest facility is. Based on this definition of influence, we propose reverse approximate nearest neighbors(RANN) queries. Formally, given a valuex 1, an RANN query q returns every user u for which distu; qbx NNDistub whereNNDistub denotes the distance between a user u and its nearest facility, i.e., q is an approximate nearest neighbor of u. In this paper,we study both snapshot and continuous versions of RANN queries. In a snapshot RANN query, the underlying data sets do not changeand the results of a query are to be computed only once. In the continuous version, the users continuously change their locations andthe results of RANN queries are to be continuously monitored. Based on effective pruning techniques and several non-trivialobservations, we propose efficient RANN query processing algorithms for both the snapshot and continuous RANN queries. Weconduct extensive experiments on both real and synthetic data sets and demonstrate that our algorithm for both snapshot andcontinuous queries are significantly better than the competitors.

    AB - Given a set of facilities and a set of users, a reverse nearest neighbors (RNN) query retrieves every user u for which thequery facility q is its closest facility. Since q is the closest facility to u, the user u is said to be influenced by q. In this paper, we propose arelaxed definition of influence where a user u is said to be influenced by not only its closest facility but also every other facility that isalmost as close to u as its closest facility is. Based on this definition of influence, we propose reverse approximate nearest neighbors(RANN) queries. Formally, given a valuex 1, an RANN query q returns every user u for which distu; qbx NNDistub whereNNDistub denotes the distance between a user u and its nearest facility, i.e., q is an approximate nearest neighbor of u. In this paper,we study both snapshot and continuous versions of RANN queries. In a snapshot RANN query, the underlying data sets do not changeand the results of a query are to be computed only once. In the continuous version, the users continuously change their locations andthe results of RANN queries are to be continuously monitored. Based on effective pruning techniques and several non-trivialobservations, we propose efficient RANN query processing algorithms for both the snapshot and continuous RANN queries. Weconduct extensive experiments on both real and synthetic data sets and demonstrate that our algorithm for both snapshot andcontinuous queries are significantly better than the competitors.

    KW - continuous monitoring

    KW - influence detection

    KW - Reverse nearest neighbors

    KW - voronoi diagram

    UR - http://www.scopus.com/inward/record.url?scp=85032447827&partnerID=8YFLogxK

    U2 - 10.1109/TKDE.2017.2766065

    DO - 10.1109/TKDE.2017.2766065

    M3 - Article

    VL - 30

    SP - 339

    EP - 352

    JO - IEEE Transactions on Knowledge and Data Engineering

    JF - IEEE Transactions on Knowledge and Data Engineering

    SN - 1041-4347

    IS - 2

    M1 - 8081813

    ER -