Finding Top k Most Influential Spatial Facilities over Uncertain Objects

Zhan, L; Zhang, Y; Zhang, W; Lin, X

Finding Top k Most Influential Spatial Facilities over Uncertain Objects

Zhan, L Zhang, Y

Zhang, W Lin, X

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2015, 27 (12), pp. 3289 - 3303
Issue Date:: 2015-12-01

Closed Access

	Filename	Description	Size
	2015_tkde_SpatialFacilities.pdf	Published Version	2.56 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	Zhan, L	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	2015-12-01	en_US
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2015, 27 (12), pp. 3289 - 3303	en_US
dc.identifier.issn	1041-4347	en_US
dc.identifier.uri	http://hdl.handle.net/10453/43246
dc.description.abstract	© 2015 IEEE. Due to a variety of reasons including data randomness and incompleteness, noise, privacy, etc., uncertainty is inherent in many important applications, such as location-based services (LBS), sensor network monitoring, and radio-frequency identification (RFID). Recently, considerable research efforts have been devoted into the field of uncertainty-aware spatial query processing such that the uncertainty of the data can be effectively and efficiently tackled. In this paper, we study the problem of finding top k most influential facilities over a set of uncertain objects, which is an important and fundamental spatial query in the above applications. Based on the maximal utility principle, we propose a new ranking model to identify the top k most influential facilities, which carefully captures influence of facilities on the uncertain objects. By utilizing two uncertain object indexing techniques, R-tree and U-Quadtree, effective and efficient algorithms are proposed following the filtering and verification paradigm, which significantly improves the performance of the algorithms in terms of CPU and I/O costs. To effectively support uncertain objects with a large number of instances, we also develop randomized algorithms with accuracy guarantee. Then, a hybrid algorithm is devised which effectively combines the randomized and exact algorithms. Comprehensive experiments on real datasets demonstrate the effectiveness and efficiency of our techniques.	en_US
dc.relation	http://purl.org/au-research/grants/arc/
dc.relation	http://purl.org/au-research/grants/arc/DP130103245
dc.relation	http://purl.org/au-research/grants/arc/DE140100679
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering	en_US
dc.relation.isbasedon	10.1109/TKDE.2015.2457899	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Finding Top k Most Influential Spatial Facilities over Uncertain Objects	en_US
dc.type	Journal Article
utslib.citation.volume	12	en_US
utslib.citation.volume	27	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	080109 Pattern Recognition and Data Mining	en_US
utslib.for	08 Information and Computing Sciences	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	12	en_US
pubs.publication-status	Published	en_US
pubs.volume	27	en_US

Abstract:

© 2015 IEEE. Due to a variety of reasons including data randomness and incompleteness, noise, privacy, etc., uncertainty is inherent in many important applications, such as location-based services (LBS), sensor network monitoring, and radio-frequency identification (RFID). Recently, considerable research efforts have been devoted into the field of uncertainty-aware spatial query processing such that the uncertainty of the data can be effectively and efficiently tackled. In this paper, we study the problem of finding top k most influential facilities over a set of uncertain objects, which is an important and fundamental spatial query in the above applications. Based on the maximal utility principle, we propose a new ranking model to identify the top k most influential facilities, which carefully captures influence of facilities on the uncertain objects. By utilizing two uncertain object indexing techniques, R-tree and U-Quadtree, effective and efficient algorithms are proposed following the filtering and verification paradigm, which significantly improves the performance of the algorithms in terms of CPU and I/O costs. To effectively support uncertain objects with a large number of instances, we also develop randomized algorithms with accuracy guarantee. Then, a hybrid algorithm is devised which effectively combines the randomized and exact algorithms. Comprehensive experiments on real 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/43246