Effectively indexing the multidimensional uncertain objects

Zhang, Ying, Zhang, Wenjie, Lin, Qianlu, Lin, Xuemin and Shen, Heng Tao (2014) Effectively indexing the multidimensional uncertain objects. IEEE Transactions on Knowledge and Data Engineering, 26 3: 608-622. doi:10.1109/TKDE.2013.21

Author Zhang, Ying
Zhang, Wenjie
Lin, Qianlu
Lin, Xuemin
Shen, Heng Tao
Title Effectively indexing the multidimensional uncertain objects
Journal name IEEE Transactions on Knowledge and Data Engineering   Check publisher's open access policy
ISSN 1041-4347
Publication date 2014-01-01
Year available 2013
Sub-type Article (original research)
DOI 10.1109/TKDE.2013.21
Open Access Status Not yet assessed
Volume 26
Issue 3
Start page 608
End page 622
Total pages 15
Place of publication Piscataway, NJ United States
Publisher Institute of Electrical and Electronics Engineers
Language eng
Subject 1703 Computational Theory and Mathematics
1710 Information Systems
1706 Computer Science Applications
Abstract 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.
Keyword Multidimensional uncertain objects
Nearest neighbor search
Range search
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2014 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 5 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 7 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 11 Mar 2014, 10:25:32 EST by System User on behalf of School of Information Technol and Elec Engineering