Maximize spatial influence of facility bundle considering reverse k nearest neighbors

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

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


    Consider a two dimensional Euclidean space, let F be a set of points representing facilities and U be a set of points representing users. Spatial influence of a facility is the number of users who have this facility as one of their k nearest facilities. This is because that users normally prefer to go to their nearby facilities and are naturally influenced the most by their nearest facilities. Given a facility bundle of size t, spatial influence of the bundle is the number of distinct users influenced by any one of them. Existing works on facility selection problem find out top-t facilities with the highest spatial influence. However, the literature lacks study on this problem when the t facilities have the highest spatial influence as a bundle. We are the first to study the problem of Maximizing Bundled Reverse k Nearest Neighbors (MB-RkNN), where the spatial influence of a facility bundle of size t is maximized. We prove its NP-hardness, and propose a branch-and-bound best first search algorithm that greedily select the currently best facility until we get t facilities. We introduce the concept of kNN region such that a group of users have their kNN facilities all belong to the same kNN region. This sharing property of kNN region allows us to avoid redundant calculation with dynamic programming technique. We conduct experiments on real data sets and show that our algorithm is orders of magnitudes better than our baseline algorithm both in terms of CPU time and IO cost.

    Original languageEnglish
    Title of host publicationDatabase Systems for Advanced Applications
    Subtitle of host publication23rd International Conference, DASFAA 2018, Gold Coast, QLD, Australia, May 21-24, 2018, Proceedings, Part I
    EditorsJian Pei, Yannis Manolopoulos, Shazia Sadiq, Jianxin Li
    Place of PublicationCham Switzerland
    Number of pages17
    ISBN (Electronic)9783319914527
    ISBN (Print)9783319914510
    Publication statusPublished - 1 Jan 2018
    EventDatabase Systems for Advanced Applications 2018 - Gold Coast, Australia
    Duration: 21 May 201824 May 2018
    Conference number: 23rd (Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    ConferenceDatabase Systems for Advanced Applications 2018
    Abbreviated titleDASFAA 2018
    CityGold Coast
    Internet address

    Cite this