Accelerate MaxBRkNN Search by kNN estimation
- Publication Type:
- Conference Proceeding
- Proceedings - International Conference on Data Engineering, 2019, 2019-April pp. 1730 - 1733
- Issue Date:
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 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: