Effectively Indexing the Multidimensional Uncertain Objects

Publisher:
Institute of Electrical and Electronics Engineers
Publication Type:
Journal Article
Citation:
IEEE Transactions on Knowledge and Data Engineering, 2014, 26 (3), pp. 608 - 622
Issue Date:
2014-03
Full metadata record
Files in This Item:
Filename Description Size
ThumbnailTKDE14_uncertain.pdfPublished Version1.89 MB
Adobe PDF
As the uncertainty is inherent in a wide spectrum of applications such as radio frequency identification (RFID) networks and location-based services (LBS), it is highly demanded to address the uncertainty of the objects. In this paper, we propose a novel indexing structure, named U-Quadtree, to organize the uncertain objects in the multidimensional space such that the queries can be processed efficiently by taking advantage of U-Quadtree. Particularly, we focus on the range search on multidimensional uncertain objects since it is a fundamental query in a spatial database. We propose a cost model which carefully considers various factors that may impact the performance. Then, an effective and efficient index construction algorithm is proposed to build the optimal U-Quadtree regarding the cost model. We show that U-Quadtree can also efficiently support other types of queries such as uncertain range query and nearest neighbor query. Comprehensive experiments demonstrate that our techniques outperform the existing works on multidimensional uncertain objects.
Please use this identifier to cite or link to this item: