Accelerate MaxBRkNN Search by kNN estimation

Chen, X; Cao, X; Xu, Z; Zhang, Y; Shang, S; Zhang, W

Accelerate MaxBRkNN Search by kNN estimation

Chen, X Cao, X Xu, Z Zhang, Y

Shang, S Zhang, W

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2019, 2019-April pp. 1730 - 1733
Issue Date:: 2019-04-01

Closed Access

	Filename	Description	Size
	ICDE_2019_BRkNN.pdf	Published version	341.88 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Chen, X	en_US
dc.contributor.author	Cao, X	en_US
dc.contributor.author	Xu, Z	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Shang, S	en_US
dc.contributor.author	Zhang, W	en_US
dc.date.issued	2019-04-01	en_US
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2019, 2019-April pp. 1730 - 1733	en_US
dc.identifier.isbn	9781538674741	en_US
dc.identifier.issn	1084-4627	en_US
dc.identifier.uri	http://hdl.handle.net/10453/136283
dc.description.abstract	© 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.	en_US
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation.ispartof	Proceedings - International Conference on Data Engineering	en_US
dc.relation.isbasedon	10.1109/ICDE.2019.00184	en_US
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Accelerate MaxBRkNN Search by kNN estimation	en_US
dc.type	Conference Proceeding
utslib.citation.volume	2019-April	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access	*
pubs.publication-status	Published	en_US
pubs.volume	2019-April	en_US

Abstract:

© 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:

http://hdl.handle.net/10453/136283