臺灣博碩士論文加值系統

不確定性資料有別於傳統的確定性資料，由於不確定性資料的不確定特性，造成了在資料管理以及運算上，增加了計算上的複雜度和龐大的計算量，因此對於不確定性資料的管理、分析和索引是個重要的研究議題。常用的索引空間資料的索引結構，如R-tree，亦可用來索引不確定性資料，但其效能會隨著資料量的成長而趨於劣化，且當資料維度增加時，索引的效能也令人無法滿意。在這篇論文中筆者提出了一個新的索引不確定性資料的架構—S-Index (Sphere Index)，在進行資料查詢時擁有較佳的效率，另一方面在高維度的資料集上，亦能有好的表現。S-Index可支援多種查詢型態，如：單點查詢(Point Query)、機率性範圍查詢(Probabilistic Range Query)和機率性最近相鄰者查詢(Probabilistic Nearest Neighbor Query)。最後，實驗使用模擬的不確定性資料集來進行，以記憶體存取數和CUP花費時間的角度，來觀察、分析、與驗證S-Index索引結構之效率，其結果合乎預期目的。

The uncertain datum is more difficult than certain datum in process. It need more huge calculate and more complex compute. Because the relation of uncertain in uncertain datum. The uncertain may be an estimates, statistics or probability value. And there have several importance issues of analysis, management and index in uncertain data. The R-Trees[6] is general index used in spate data. Also the R-Trees could apply in uncertain data. But, it has a fatal defect in nature. The index efficiency will degraded when data grow up. It is poor performance for each query, because the index will index more invalid space in internal node. And spend more unnecessary memory accesses and CUP times. Thus, here propose a new index structure Sphere-Index in this paper. It is shortest call for S-Index. There were not exit overlay between index MBRs of each internal in S-Index. So it will be improve and effect for query processing. In the other hand, S-Index has better performance than R-Trees in high dimensional data. S-Index supply more type of query processing (pint query, probabilistic range query and probabilistic Nearest Neighbor query). The other issue of update will be discussed in the paper, too. The simulation experiment is the end of this paper. Experiment is use simulation data set, and use the evaluate criterion by memory accesses and CUP times. The Experiment will be prove and verify the effective of S-Index.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章 前言 1
第二章 問題定義 3
2.1 不確定性資料定義 3
2.2 查詢定義 3
第三章 相關背景 6
3.1 R-Trees 7
3.2 US+-Trees 9
第四章 Sphere-Index 11
4.1 結構 11
4.2 查詢 14
4.2.1 單點查詢 14
4.2.2 機率性範圍查詢 17
4.2.3 機率性最近相鄰者查詢 20
4.3 更新 23
4.3.1 插入 24
4.3.2 刪除 27
第五章 實驗 30
5.1 單點查詢 31
5.2 機率性範圍查詢 34
5.3 機率性最近相鄰者查詢 40
5.4 分支度的變化 50
5.5 Filter的成效 54
5.6 物件更新 55
第六章 結論 57
參考文獻 58

[1] Aggarwal C.C. and Yu P.S. "A Survey of Uncertain Data Algorithms and Applica-tions". Published of the Knowledge and Data Engineering, IEEE Transactions, 21(4): pp.609-623, 2009.
[2] Bo-Song Jian, Fan-Ya Kao, and Chuan-Ming Liu, "Effective Methods for Indexing Uncertain Data", Published of the 15th Mobile Computing Workshop, 2010.
[3] Beckmann N., Kriegel H. P., Schneider R. and Seeger B. "The R*-tree: an efficient and robust access method for points and rectangles". Proceedings of the ACM SIG-MOD international conference on Management of data, 19(2): pp. 322-331, 1990.
[4] David A. White and Ramesh Jain, "Similarity Indexing with the SS-tree", Proceed-ings of the Twelfth International Conference on Data Engineering,pp. 516-523, 1996.
[5] Fan-Ya Kao and Chuan-Ming Liu, "Enhancing querying performance for nearest neighbors on uncertain data using US+-Trees", Published of the 16th Mobile Compu-ting Workshop, 2011.
[6] Guttman A, "R-Trees: A Dynamic Index Structure for Spatial Searching". Proceed-ings of the ACM SIGMOD international conference on Management of data, 14(2): pp.47-57, 1984.
[7] G′sli R. Hjaltason and Hanan Samet, "Distance Browsing in Spatial Databases", Proceedings of the ACM Transactions on Database Systems, 24(2): pp. 265–318, 1999.
[8] John T. Robinson, "KDB Tree: A Search Structure for Large Multidimensional Dy-namic Indexes", ACM SIGMOD international conference on Management of data, 1981.
[9] King-ip Lin, H. V. Jagadish and Christos Faloutsos, "The TV-tree: An index structure for high-dimensional data", Proceedings of the Very Large Data Bases - Spatial Da-tabase Systems, 3(4): pp.517-542, 1994.
[10] Norio Katayama and Shin''ichi Satoh, "The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries", Proceedings of the ACM SIGMOD international conference on Management of data, 26(2): pp.369-380, 1997.
[11] Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel, "The X-tree: An Index Structure for High-Dimensional Data", Proceedings of the 22th International Con-ference on Very Large Data Bases, pp.28-39, 1996.
[12] Simonas Saltenis , Christian S. Jensen , Scott T. Leutenegger and Mario A. Lopez, "Indexing the Positions of Continuously Moving Objects", Proceedings of the ACM SIGMOD international conference on Management of data, 29(2): pp.331-342, 2000.
[13] Timos K. Sellis, Nick Roussopoulos and Christos Faloutsos, "The R+-Tree: A Dy-namic Index for Multi-Dimensional Objects", Proceedings of the 13th International Con-ference on Very Large Data Bases, pp.507-518, 1987.
[14] Tufei Tao, Dimitris Papadias and Jimeng Sun, "The TPR*-Tree: An Optimized Spatio-Temporal", Proceedings of the 29th international conference on Very large data bases, 29: pp.790-801, 2003.
[15] Volker Gaede and Oliver Gunther, "Multidimensional Access Methods", Proceed-ings of the ACM Computing Surveys, 30(2): pp.170-231, 1998.
[16] Yasushi Sakurai, Masatoshi Yoshikawa, Shunsuke Uemura and Haruhiko Kojima, " The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Ap-proximation", Proceedings of the 26th International Conference on Very Large Data Bases, pp.516-526, 2000.
[17] Ying Zhang, Wenjie Zhang, Qianlu Lin and Xuemin Lin, "Effectively Indexing the Multi-Dimensional Uncertain Objects for Range Searching", Proceedings of the 15th International Conference on Extending Database Technology, pp.504-515, 2012.
[18] Yuni Xia, Sunil Prabhakar, Shan Lei, Reynold Cheng and Rahul Shah, "Indexing continuously changing data with mean-variance tree", Proceedings of the ACM symposium on Applied computing, pp.1125-1132, 2005.
[19] Yinian Qi, Rohit Jain, Sarvjeet Singh and Sunil Prabhakar, "Threshold query opti-mization for uncertain data", Proceedings of the ACM SIGMOD International Con-ference on Management of data, pp.315-326, 2010.