Efficiently computing reverse k furthest neighbors

Shenlu Wang, Muhammad Aamir Cheema, Xuemin Lin, Ying Zhang, Dongxi Liu

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    13 Citations (Scopus)

    Abstract

    Given a set of facilities F, a set of users U and a query facility q, a reverse k furthest neighbors (RkFN) query retrieves every user u∈U for which q is one of its k-furthest facilities. RkFN query is the natural complement of reverse k-nearest neighbors (RkNN) query that returns every user u for which q is one of its k-nearest facilities. While RkNN query returns the users that are highly influenced by a query q, RkFN query aims at finding the users that are least influenced by a query q. RkFN query has many applications in location-based services, marketing, facility location, clustering, and recommendation systems etc. While there exist several algorithms that answer RkFN query for k = 1, we are the first to propose a solution for arbitrary value of k. Based on several interesting observations, we present an efficient algorithm to process the RkFN queries. We also present a rigorous theoretical analysis to study various important aspects of the problem and our algorithm. An extensive experimental study is conducted using both real and synthetic data sets, demonstrating that our algorithm outperforms the state-of-the-art algorithm even for k = 1. The accuracy of our theoretical analysis is also verified by the experiments.
    Original languageEnglish
    Title of host publicationProceedings of the 2016 IEEE International Conference on Data Engineering (ICDE 2016)
    EditorsMei Hsu, Alfons Kemper, Timos Sellis
    PublisherIEEE, Institute of Electrical and Electronics Engineers
    Pages1110-1121
    Number of pages12
    ISBN (Print)9781509020195, 9781509020218
    DOIs
    Publication statusPublished - 22 Jun 2016
    EventIEEE International Conference on Data Engineering 2016 - Aalto University School of Business, Helsinki, Finland
    Duration: 16 May 201620 May 2016
    Conference number: 32nd
    http://icde2016.fi/

    Conference

    ConferenceIEEE International Conference on Data Engineering 2016
    Abbreviated titleICDE 2016
    CountryFinland
    CityHelsinki
    Period16/05/1620/05/16
    OtherThe annual ICDE conference addresses research issues in designing, building, managing, and evaluating advanced data systems and applications. It is a leading forum for researchers, practitioners, developers, and users to explore cutting-edge ideas and to exchange techniques, tools, and experiences.
    Internet address

    Cite this