臺灣博碩士論文加值系統

　　由於現代科技的日新月異，資訊的收集不再受限於硬體限制，資料庫的資訊越來越詳盡。許多實際應用可能轉變成在不確定性環境使用，如何有效使用如此完善的資訊是重要的，我們應該要能在這當中找出有別於確定性環境下的結果。在先前研究中已經提出在不確定性環境下的天際線查詢，解決長久以來天際線查詢僅能適用於確定性環境的困境。然而在當中，我們發現到在這樣的機率模型底下，對於非屬於天際點的點是沒有差異性的；同理對於同屬於天際點也是沒有差異性。如此並不能完整的將資訊傳達給使用者做決策。
本篇論文提出了以期望值為基礎的分數計算方法，旨在提供給使用者更合理的回傳結果，每個物件都擁有足以代表自身狀態的分數，這個分數與其他物件息息相關，藉由測試自身與其他物件的支配關係來知曉可從每個物件當中獲取多少期望值，我們稱這個分數為競爭力（CP值）。
　　在我們的研究中，採用了以門檻為基礎的演算法來找到具有高競爭力的物件，並經由擴展來支援回傳特定數量物件的Top-K模式。藉由真實資料的實驗，結果也證明在這樣的計算下，高競爭力的物件的確是受人肯定的物件。

Because the improvement of technology, the collecting of information is no longer limited to hardware, and many real applications may turn out to be used in uncertain data environments. Therefore, how to compute the needed information in such an environment efficiently is a very important problem.
In this work, the idea of expected number of objects is introduced to represent as the scoring function of an object in the uncertain database. And the score associated with each object is called as CP value. By using the concept of CP value, we propose the efficient algorithms for finding the high-CP and Top-K objects. Simulation is performed on both syntactic and real datasets. The experimental results indicate that our approach is efficient and effective..

第一章 導論…………………………………………………………………………1
第二章 先備知識……………………………………………………………………9
第三章 問題定義…………………………………………………………………..15
第四章 演算法……………………………………………………………………..19
4.1　建立分割樹……………………………………………………………….20
4.2 精算少量元素…………………………………………………………….21
4.3 分層分割樹……………………………………………………………….23
4.4 整合物件競爭力………………………………………………………….24
4.5 遞迴運算………………………………………………………………….24
4.6 虛擬碼1………………………………………………………………......26
4.7 虛擬碼2…………………………………………………………………..30
第五章 實驗結果…………………………………………………………………..35
5.1 實驗規劃………………………………………………………………….35
5.2 實驗分析………………………………………………………………….35
第六章 結論及未來展望…………………………………………………………..43
參考文獻……………………………………………………………………………..45

[1] C. Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. Tung, and Z. Zhang. Finding k-dominant skylines in high dimensional space. In SIGMOD 2006 ,pp. 503-514.
[2] D.Kossmann , F.Ramsak , and S.Rost . Shooting stars in the sky: An online algorithm for skyline queries. In Proceedings of the Very Large Data Bases Conference 2002. pp. 275-285.
[3] P. Godfrey , R. Shipley , J. Gryz, Maximal vector computation in large data sets, Proceedings of the 31st international conference on Very large data bases 2005, pp. 229-240.
[4] G.P.C.Fung , W.Lu , X.Du , Dominant and k nearest probabilistic skylines. In: Proc. of the 14th International Conference on Database Systems for Advanced Applications(DASFAA 2009), pp. 263–277.
[5] J. Pei, B. Jiang, X. Lin and Y. Yuan, Probabilistic Skylines on Uncertain Data, Proc. 33rd Int',l Conf. Very Large Data Bases (VLDB 2007), pp. 15–26.
[6] J. Pei, A. W.-C. Fu, X. Lin, and H. Wang. Computing compressed multidimensional skyline cubes efficiently. ICDE 2007 , pp. 96–105.
[7] J.Chomicki , P.Godfrey , J.Gryz , and D.Liang , Skyline with presorting. In Proceedings of the IEEE International Conference on Data Engineering 2003 , pp. 717–719.
[8] K. C. K. Lee, B. Zheng, H. Li, and W.C. Lee, "Approaching the skyline in Z order," in VLDB, 2007, pp. 279-290.
[9] Z. Huang , C. S. Jensen , H. Lu , B.C. Ooi, Skyline Queries Against Mobile Lightweight Devices in MANETs, Proceedings of the 22nd International Conference on Data Engineering (ICDE 2006), p.66 .

[10] X. Lin , Y. Yuan , W. Wang , H. Lu, Stabbing the Sky: Efficient Skyline Computation over Sliding Windows, Proceedings of the 21st International Conference on Data Engineering (ICDE 2005), pp.502-513.
[11] D. Papadias , Y. Tao , G. Fu , B. Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data 2003, pp.467-478.
[12] R. Agrawal and R. Srikant "Fast algorithms for mining association rules", Proc. of the VLDB Conference1994, pp.487-499.
[13] S.Borzsonyi, D.Kossmann , K.Stocker , The Skyline Operator. ICDE 2001. pp. 275--286.
[14] W.Zhang , X.Lin , Y.Zhang , J.Pei , W.Wang : Threshold-based probabilistic top-k dominating queries. The VLDB Journal 19, 2010, pp. 283–305.
[15] W. Zhang , X. Lin , Y. Zhang , W. Wang , J. X. Yu, Probabilistic Skyline Operator over Sliding Windows, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1060-1071.
[16] Z. Zhang, X. Guo, H. Lu, A. Tung, and N. Wang. Discovering Strong Skyline Points in High Dimensional Spaces. In EDBT 2006, pages 478 -795