TY - GEN
T1 - Indexing uncertain data for supporting range queries
AU - Zhu, Rui
AU - Wang, Bin
AU - Wang, Guoren
PY - 2014
Y1 - 2014
N2 - Probabilistic range query is a typical and a fundamental problem in probabilistic DBMS. Although the existing solutions provide a good performance, there are some shortages that are needed to be overcomed. In this paper, we firstly propose a novel structure called MRST to approximately capture the probability density function of uncertain object. Through considering the gradient of the probability density function, MRST could provide uncertain object with strong pruning power and consume fewer space cost. Based on characters of MRST, we also design an efficient algorithm to access MRST. We propose a novel index named R-MRST to efficiently support range query on multidimensional uncertain data. Its has a strong pruning power. At the same time, it has a lower cost both in space and dynamic update. Theoretical analysis and extensive experimental results demonstrate the effectiveness of the proposed algorithms.
AB - Probabilistic range query is a typical and a fundamental problem in probabilistic DBMS. Although the existing solutions provide a good performance, there are some shortages that are needed to be overcomed. In this paper, we firstly propose a novel structure called MRST to approximately capture the probability density function of uncertain object. Through considering the gradient of the probability density function, MRST could provide uncertain object with strong pruning power and consume fewer space cost. Based on characters of MRST, we also design an efficient algorithm to access MRST. We propose a novel index named R-MRST to efficiently support range query on multidimensional uncertain data. Its has a strong pruning power. At the same time, it has a lower cost both in space and dynamic update. Theoretical analysis and extensive experimental results demonstrate the effectiveness of the proposed algorithms.
UR - http://www.scopus.com/inward/record.url?scp=84958553180&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-08010-9_10
DO - 10.1007/978-3-319-08010-9_10
M3 - Conference contribution
AN - SCOPUS:84958553180
SN - 9783319080093
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 72
EP - 83
BT - Web-Age Information Management - 15th International Conference, WAIM 2014, Proceedings
PB - Springer Verlag
T2 - 15th International Conference on Web-Age Information Management, WAIM 2014
Y2 - 16 June 2014 through 18 June 2014
ER -