Categorical top-k spatial influence query

Yang, J; Zhang, W; Zhang, Y; Wang, X; Lin, X

Categorical top-k spatial influence query

Yang, J Zhang, W Zhang, Y

Wang, X Lin, X

Permalink

Publication Type:: Journal Article
Citation:: World Wide Web, 2017, 20 (2), pp. 175 - 203
Issue Date:: 2017-03-01

Closed Access

	Filename	Description	Size
	WWWJ_2016_topk.pdf	Published Version	1.92 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	Yang, J	en_US
dc.contributor.author	Zhang, W	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Wang, X	en_US
dc.contributor.author	Lin, X	en_US
dc.date.issued	2017-03-01	en_US
dc.identifier.citation	World Wide Web, 2017, 20 (2), pp. 175 - 203	en_US
dc.identifier.issn	1386-145X	en_US
dc.identifier.uri	http://hdl.handle.net/10453/44059
dc.description.abstract	© 2016, Springer Science+Business Media New York. The influence of a spatial facility object depicts the importance of the object in the whole data space. In this paper, we present a novel definition of object influence in applications where objects are of different categories. We study the problem of Spatial Influence Query which considers the contribution of an object in forming functional units consisting of a given set of objects with different categories designated by users. We first show that the problem of spatial influence query is NP-hard with respect to the number of object categories in the functional unit. To tackle the computational hardness, we develop an efficient framework following two main steps, possible participants finding and optimal functional unit computation. Based on this framework, for the first step, novel and efficient pruning techniques are developed based on the nearest neighbor set (NNS) approach. To find the optimal functional unit efficiently, we propose two algorithms, an exact algorithm and an efficient approximate algorithm with performance guarantee. Comprehensive experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of our techniques.	en_US
dc.relation.ispartof	World Wide Web	en_US
dc.relation.isbasedon	10.1007/s11280-016-0383-3	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Categorical top-k spatial influence query	en_US
dc.type	Journal Article
utslib.citation.volume	2	en_US
utslib.citation.volume	20	en_US
utslib.for	0805 Distributed Computing	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	0804 Data Format	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	2	en_US
pubs.publication-status	Published	en_US
pubs.volume	20	en_US

Abstract:

© 2016, Springer Science+Business Media New York. The influence of a spatial facility object depicts the importance of the object in the whole data space. In this paper, we present a novel definition of object influence in applications where objects are of different categories. We study the problem of Spatial Influence Query which considers the contribution of an object in forming functional units consisting of a given set of objects with different categories designated by users. We first show that the problem of spatial influence query is NP-hard with respect to the number of object categories in the functional unit. To tackle the computational hardness, we develop an efficient framework following two main steps, possible participants finding and optimal functional unit computation. Based on this framework, for the first step, novel and efficient pruning techniques are developed based on the nearest neighbor set (NNS) approach. To find the optimal functional unit efficiently, we propose two algorithms, an exact algorithm and an efficient approximate algorithm with performance guarantee. Comprehensive experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of our techniques.

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

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