Progressive Top-K Nearest Neighbors Search in Large Road Networks

Ouyang, D; Wen, D; Qin, L; Chang, L; Zhang, Y; Lin, X

Progressive Top-K Nearest Neighbors Search in Large Road Networks

Ouyang, D Wen, D

Qin, L

Chang, L Zhang, Y Lin, X

Permalink

Publisher:: ACM
Publication Type:: Conference Proceeding
Citation:: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2020, pp. 1781-1795
Issue Date:: 2020-06-14

Closed Access

	Filename	Description	Size
	main.pdf	Accepted version	1.43 MB	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	Ouyang, D
dc.contributor.author	Wen, D https://orcid.org/0000-0002-0903-1503
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Chang, L
dc.contributor.author	Zhang, Y
dc.contributor.author	Lin, X
dc.contributor.editor	Maier, D
dc.contributor.editor	Pottinger, R
dc.contributor.editor	Doan, A
dc.contributor.editor	Tan, W-C
dc.contributor.editor	Alawini, A
dc.contributor.editor	Ngo, HQ
dc.date.accessioned	2021-03-03T02:14:49Z
dc.date.available	2021-03-03T02:14:49Z
dc.date.issued	2020-06-14
dc.identifier.citation	Proceedings of the ACM SIGMOD International Conference on Management of Data, 2020, pp. 1781-1795
dc.identifier.isbn	9781450367356
dc.identifier.issn	0730-8078
dc.identifier.uri	http://hdl.handle.net/10453/146671
dc.description.abstract	© 2020 Association for Computing Machinery. Computing top-k nearest neighbors (kNN) is a fundamental problem in road networks. Existing solutions either need a complicated parameter configuration in index construction or incur high costs when scanning an unbounded number of vertices in query processing. In this paper, we propose a novel parameter-free index-based solution for the kNN query based on the concept of tree decomposition in large road networks. Based on our index structure, we propose an efficient and progressive algorithm that returns each result in a bounded delay. We also optimize the index structure, which improves the efficiency of both index construction and index maintenance in large road networks. We conduct extensive experiments to show the efficiency of our proposed algorithms and the effectiveness of our optimization techniques in real-world road networks from ten regions.
dc.language	en
dc.publisher	ACM
dc.relation	http://purl.org/au-research/grants/arc/DP160101513
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation.ispartof	Proceedings of the ACM SIGMOD International Conference on Management of Data
dc.relation.ispartof	SIGMOD/PODS '20: International Conference on Management of Data
dc.relation.hasversion	Accepted Manuscript Version	en
dc.relation.isbasedon	10.1145/3318464.3389746
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Progressive Top-K Nearest Neighbors Search in Large Road Networks
dc.type	Conference Proceeding
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2021-03-03T02:14:47Z
pubs.publication-status	Published

Abstract:

© 2020 Association for Computing Machinery. Computing top-k nearest neighbors (kNN) is a fundamental problem in road networks. Existing solutions either need a complicated parameter configuration in index construction or incur high costs when scanning an unbounded number of vertices in query processing. In this paper, we propose a novel parameter-free index-based solution for the kNN query based on the concept of tree decomposition in large road networks. Based on our index structure, we propose an efficient and progressive algorithm that returns each result in a bounded delay. We also optimize the index structure, which improves the efficiency of both index construction and index maintenance in large road networks. We conduct extensive experiments to show the efficiency of our proposed algorithms and the effectiveness of our optimization techniques in real-world road networks from ten regions.

Please use this identifier to cite or link to this item:

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