AVR-tree: Speeding up the NN and ANN queries on location data

Lin, Q; Zhang, Y; Zhang, W; Lin, X

AVR-tree: Speeding up the NN and ANN queries on location data

Lin, Q Zhang, Y

Zhang, W Lin, X

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7825 LNCS (PART 1), pp. 116 - 130
Issue Date:: 2013-12-01

Closed Access

	Filename	Description	Size
	2013005453OK.pdf		371.6 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	Lin, Q	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Zhang, W	en_US
dc.contributor.author	Lin, X	en_US
dc.date.issued	2013-12-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7825 LNCS (PART 1), pp. 116 - 130	en_US
dc.identifier.isbn	9783642374869	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28946
dc.description.abstract	In the paper, we study the problems of nearest neighbor queries (NN) and all nearest neighbor queries (ANN) on location data, which have a wide range of applications such as Geographic Information System (GIS) and Location based Service (LBS). We propose a new structure, termed AVR-Tree, based on the R-tree and Voronoi diagram techniques. Compared with the existing indexing techniques used for NN and ANN queries on location data, AVR-Tree can achieve a better tradeoff between the pruning effectiveness and the index size for NN and ANN queries. We also conduct a comprehensive performance evaluation for the proposed techniques based on both real and synthetic data, which shows that AVR-Tree based NN and ANN algorithms achieve better performance compared with their best competitors in terms of both CPU and I/O costs. © Springer-Verlag 2013.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-642-37487-6_11	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	AVR-tree: Speeding up the NN and ANN queries on location data	en_US
dc.type	Conference Proceeding
utslib.citation.volume	PART 1	en_US
utslib.citation.volume	7825 LNCS	en_US
utslib.for	0806 Information Systems	en_US
dc.location.activity	China	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.issue	PART 1	en_US
pubs.publication-status	Published	en_US
pubs.volume	7825 LNCS	en_US

Abstract:

In the paper, we study the problems of nearest neighbor queries (NN) and all nearest neighbor queries (ANN) on location data, which have a wide range of applications such as Geographic Information System (GIS) and Location based Service (LBS). We propose a new structure, termed AVR-Tree, based on the R-tree and Voronoi diagram techniques. Compared with the existing indexing techniques used for NN and ANN queries on location data, AVR-Tree can achieve a better tradeoff between the pruning effectiveness and the index size for NN and ANN queries. We also conduct a comprehensive performance evaluation for the proposed techniques based on both real and synthetic data, which shows that AVR-Tree based NN and ANN algorithms achieve better performance compared with their best competitors in terms of both CPU and I/O costs. © Springer-Verlag 2013.

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

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