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 topt 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 (MBRkNN), where the spatial influence of a facility bundle of size t is maximized. We prove its NPhardness, and propose a branchandbound 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 2124, 2018, Proceedings, Part I 
Editors  Jian Pei, Yannis Manolopoulos, Shazia Sadiq, Jianxin Li 
Place of Publication  Cham Switzerland 
Publisher  Springer 
Pages  684700 
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/9783319914527 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  10827 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
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 
