Please use this identifier to cite or link to this item: https://doi.org/10.1109/ICDE.2011.5767892
Title: MaxFirst for MaxBRkNN
Authors: Zhou, Z.
Wu, W.
Li, X.
Lee, M.L. 
Hsu, W. 
Issue Date: 2011
Source: Zhou, Z.,Wu, W.,Li, X.,Lee, M.L.,Hsu, W. (2011). MaxFirst for MaxBRkNN. Proceedings - International Conference on Data Engineering : 828-839. ScholarBank@NUS Repository. https://doi.org/10.1109/ICDE.2011.5767892
Abstract: The MaxBRNN problem finds a region such that setting up a new service site within this region would guarantee the maximum number of customers by proximity. This problem assumes that each customer only uses the service provided by his/her nearest service site. However, in reality, a customer tends to go to his/her k nearest service sites. To handle this, MaxBRNN can be extended to the MaxBRkNN problem which finds an optimal region such that setting up a service site in this region guarantees the maximum number of customers who would consider the site as one of their k nearest service locations. We further generalize the MaxBRkNN problem to reflect the real world scenario where customers may have different preferences for different service sites, and at the same time, service sites may have preferred targeted customers. In this paper, we present an efficient solution called MaxFirst to solve this generalized MaxBRkNN problem. The algorithm works by partitioning the space into quadrants and searches only in those quadrants that potentially contain an optimal region. During the space partitioning, we compute the upper and lower bounds of the size of a quadrant's BRkNN, and use these bounds to prune the unpromising quadrants. Experiment results show that MaxFirst can be two to three orders of magnitude faster than the state-of-the-art algorithm. © 2011 IEEE.
Source Title: Proceedings - International Conference on Data Engineering
URI: http://scholarbank.nus.edu.sg/handle/10635/40907
ISBN: 9781424489589
ISSN: 10844627
DOI: 10.1109/ICDE.2011.5767892
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

30
checked on Dec 13, 2017

Page view(s)

45
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.