Abstract
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 language | English |
---|---|
Title of host publication | Database Systems for Advanced Applications |
Subtitle of host publication | 23rd International Conference, DASFAA 2018, Gold Coast, QLD, Australia, May 21-24, 2018, Proceedings, Part I |
Editors | Jian Pei, Yannis Manolopoulos, Shazia Sadiq, Jianxin Li |
Place of Publication | Cham Switzerland |
Publisher | Springer |
Pages | 684-700 |
Number of pages | 17 |
ISBN (Electronic) | 9783319914527 |
ISBN (Print) | 9783319914510 |
DOIs | |
Publication status | Published - 1 Jan 2018 |
Event | Database Systems for Advanced Applications 2018 - Gold Coast, Australia Duration: 21 May 2018 → 24 May 2018 Conference number: 23rd https://link.springer.com/book/10.1007/978-3-319-91452-7 (Proceedings) |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 10827 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | Database Systems for Advanced Applications 2018 |
---|---|
Abbreviated title | DASFAA 2018 |
Country | Australia |
City | Gold Coast |
Period | 21/05/18 → 24/05/18 |
Internet address |
|