Accelerate MaxBRkNN Search by kNN estimation

Publication Type:
Conference Proceeding
Proceedings - International Conference on Data Engineering, 2019, 2019-April pp. 1730 - 1733
Issue Date:
Filename Description Size
ICDE_2019_BRkNN.pdfPublished version341.88 kB
Adobe PDF
Full metadata record
© 2019 IEEE. Given a set of server points (e.g., locations) P and a set of client points (e.g., users) O, the problem of maximizing bichromatic reverse k-nearest neighbor (MaxBRkNN) aims to find a region for setting up a new service site such that it can influence the most clients, i.e., it is in the kNN results of most client points. All existing studies first compute the kNN of client points and then perform the MaxBRkNN search. However, computing kNN for all clients is extremely time consuming especially on large datasets. Observing this, we develop an approach which computes kNN for only promising clients by utilising a two-level grid index (ADPGI) to reduce the cost substantially. Empirical studies on both real and synthetic datasets show that our proposed exact algorithm is 3 to 5 times faster than two state-of-the-art MaxBRkNN algorithms.
Please use this identifier to cite or link to this item: