Inverted linear quadtree: Efficient top k spatial keyword search

Zhang, C; Zhang, Y; Zhang, W; Lin, X

Inverted linear quadtree: Efficient top k spatial keyword search

Zhang, C Zhang, Y

Zhang, W Lin, X

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2013, pp. 901 - 912
Issue Date:: 2013-08-15

Closed Access

	Filename	Description	Size
	2013005452OK.pdf		458.19 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	Zhang, C	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-08-15	en_US
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2013, pp. 901 - 912	en_US
dc.identifier.isbn	9781467349086	en_US
dc.identifier.issn	1084-4627	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28945
dc.description.abstract	With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount of spatio-textual objects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study the problem of top k spatial keyword search (TOPK-SK), which is fundamental in the spatial keyword queries. Given a set of spatio-textual objects, a query location and a set of query keywords, the top k spatial keyword search retrieves the closest k objects each of which contains all keywords in the query. Based on the inverted index and the linear quadtree, we propose a novel index structure, called inverted linear quadtree (IL-Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. In addition, we show that the IL-Quadtree technique can also be applied to improve the performance of other spatial keyword queries such as the direction-aware top k spatial keyword search and the spatio-textual ranking query. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods. © 2013 IEEE.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP130103245
dc.relation.ispartof	Proceedings - International Conference on Data Engineering	en_US
dc.relation.isbasedon	10.1109/ICDE.2013.6544884	en_US
dc.title	Inverted linear quadtree: Efficient top k spatial keyword search	en_US
dc.type	Conference Proceeding
utslib.for	0806 Information Systems	en_US
dc.location.activity	Brisbane, Australia	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

Abstract:

With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount of spatio-textual objects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study the problem of top k spatial keyword search (TOPK-SK), which is fundamental in the spatial keyword queries. Given a set of spatio-textual objects, a query location and a set of query keywords, the top k spatial keyword search retrieves the closest k objects each of which contains all keywords in the query. Based on the inverted index and the linear quadtree, we propose a novel index structure, called inverted linear quadtree (IL-Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. In addition, we show that the IL-Quadtree technique can also be applied to improve the performance of other spatial keyword queries such as the direction-aware top k spatial keyword search and the spatio-textual ranking query. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods. © 2013 IEEE.

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

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