(3.236.222.124) 您好!臺灣時間:2021/05/08 06:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:Goodwill Wandile Nkabinde
研究生(外文):Goodwill Wandile Nkabinde
論文名稱:在不確定資料流上機率性頂端k物件查詢問題
論文名稱(外文):Probabilistic Top-K Query Processing on Uncertain Data Streams
指導教授:劉傳銘劉傳銘引用關係
口試委員:王正豪, 陳震宇, 劉傳銘
口試日期:2016-07-15
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:資訊工程系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
中文關鍵詞:Probabilistic Top-kUncertain DataData Streamssliding window
外文關鍵詞:Probabilistic Top-kUncertain DataData Streamssliding window
相關次數:
  • 被引用被引用:0
  • 點閱點閱:43
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
Top-k queries rank results according to some user defined score. Uncertain data is inconsistent data that is imprecise and contains a lot of errors. Uncertain data is inherent in many applications due to various factors such as limitation of measuring equipment and delays, these uncertain data arrive in streaming fashion, i.e. data streams, resulting in uncertain data streams. Data streams are unbounded, continuous, high speed, high volume and sometimes in real time. The probabilistic top-k query not only retrieves the k most preferred object from a data stream according to a given preference function but objects with a certain probability of existence. These queries are important for a number of applications such as web-based advertising, network traffic monitoring, financial analysis and hazardous weather monitoring. In this research we study a problem of returning probabilistic top-k results over uncertain data streams that meet a certain scoring function, the scoring function can be a manipulation of more than one conditions simultaneously. We then use an aR-tree to effectively and prune the search space for multi-dimensional data. The sliding window model over uncertain data streams will be used to retrieve the most recent and more relevant objects with a certain time-stamp. In the end simulation experiments will be done to determine the performance of the top-k query for different parameter k, different value for the threshold and varying sliding window size.
Top-k queries rank results according to some user defined score. Uncertain data is inconsistent data that is imprecise and contains a lot of errors. Uncertain data is inherent in many applications due to various factors such as limitation of measuring equipment and delays, these uncertain data arrive in streaming fashion, i.e. data streams, resulting in uncertain data streams. Data streams are unbounded, continuous, high speed, high volume and sometimes in real time. The probabilistic top-k query not only retrieves the k most preferred object from a data stream according to a given preference function but objects with a certain probability of existence. These queries are important for a number of applications such as web-based advertising, network traffic monitoring, financial analysis and hazardous weather monitoring. In this research we study a problem of returning probabilistic top-k results over uncertain data streams that meet a certain scoring function, the scoring function can be a manipulation of more than one conditions simultaneously. We then use an aR-tree to effectively and prune the search space for multi-dimensional data. The sliding window model over uncertain data streams will be used to retrieve the most recent and more relevant objects with a certain time-stamp. In the end simulation experiments will be done to determine the performance of the top-k query for different parameter k, different value for the threshold and varying sliding window size.
ABSTRACT i
Acknowledgement iii
Table of Contents iv
Chapter 1 Introduction 1
1.1 Preliminary 1
1.2 Contributions 6
1.3 Structure of thesis 6
Chapter 2 Background 8
2.1 Definitions 8
2.2 Problem Statement 10
2.3 Motivation 10
2.4 Sliding windows 12
2.5 Augmented R-tree (aR-tree) 14
Chapter 3 Literature review 18
3.1 Top-k Queries 18
3.2 Related Work 23
Chapter 4 Probabilistic Top-k Query 26
Chapter 5 Proposed Algorithms 29
5.1 Terms and abbreviations 29
5.2 Methods 30
5.2.1 Base algorithm 31
5.2.2 Inserting an Object 32
5.2.3 Deleting an Object 34
5.2.4 Computing Top-k objects 35
Chapter 6 Experiments and Results 36
6.1. Threshold 37
6.2 Sliding Window Size 39
6.3 k-value 41
6.4 Discussion of results 42
Chapter 7 Conclusion 43
Bibliography 44
[1]C. Liu and S. Tang, “An Effective Probabilistic Skyline Query Process on Uncertain Data Streams,” in Procedia - Procedia Computer Science, 2015, vol. 63, no. Euspn, pp. 40–47.
[2]W. Zhang, X. Lin, J. Pei, and Y. Zhang, “Managing Uncertain Data : Probabilistic Approaches,” in Web-Age Information Management 9th conference, 2008, pp. 405–412.
[3]T. Minh, N. Le, J. Cao, and Z. He, “Top-k best probability queries and semantics ranking properties on probabilistic databases,” in Procedia Computer Science, 2012, vol. 00, pp. 1–21.
[4]W. Zhang, X. Lin, Y. Zhang, W. Wang, and J. X. Yu, “Probabilistic Skyline Operator over Sliding Windows,” in IEEE International Conference on Data Engineering, 2009, pp. 1060–1071.
[5]H. Z. Su, E. T. Wang, and A. L. P. Chen, “Continuous Probabilistic Skyline Queries over Uncertain Data Streams,” in DEXA, PART I, LNCS 6261, 2010, pp. 105–121.
[6]Y. Wang, X. Li, X. Li, and Y. Wang, “A survey of queries over uncertain data,” Knowledge Information System, vol. 37, no. 3, pp. 485–530, 2013.
[7]I. F. Ilyas, G. Beskales, and M. A. Soliman, “A Survey of Top- k Query Processing Techniques in Relational Database Systems,” ACM Computing Survey, vol. 40, no. 4, pp. 1–61, 2008.
[8]M. Kontaki, “Continuous processing of preference queries in data streams,” SOFSEM 2010 Theory Pract. Comput. Sci., vol. 5901, pp. 47–60, 2010.
[9]G. H. C. Han, L. Xu, “Mining Recent Frequent Itemset in Sliding Windows Over Data Streams Lijun Xu Guoping He,” Comput. Informatics, vol. 27, pp. 315–339, 2008.
[10]D. Papadias, G. Fu, and B. Seeger, “An Optimal and Progressive Algorithm for Skyline Queries,” in International Conference on Management of Data, 2003, pp. 467–478.
[11]M. L. Yiu, D.- Aalborg, and N. Mamoulis, “Efficient Processing of Top- k Dominating Queries on Multi-Dimensional Data ∗,” in 33rd international conference on Very Large Databases (VLDB), 2007, pp. 483–494.
[12]N. Mamoulis, S. Bakiras, and P. Kalnis, “Evaluation of Top-k OLAP Queries Using Aggregate R – Trees,” in 9th international conference in Advances in Spatial and Temporal databases, 2005, pp. 236–253.
[13]E. Ciceri, P. Fraternali, D. Martinenghi, and M. Tagliasacchi, “Crowdsourcing for Top-K Query Processing over Uncertain Data,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 1, pp. 41–53, 2016.
[14]N. Xiao, T. Chen, L. Chen, and M. O. Tamer, “Optimizing Multi-Top-k Queries over Uncertain Data Streams,” IEEE Int. Conf. Data Eng., vol. 25, no. 8, pp. 1814–1829, 2013.
[15]A. Vlachou, C. Doulkeridis, K. Nørv, and Y. Kotidis, “Identifying the Most Influential Data Objects with Reverse Top-k Queries,” in 36th International Conference on Very Large Data Bases, 2010, vol. 3, no. 1, pp. 364–372.
[16]C. Jin, K. Yi, L. Chen, and J. Xu, “Sliding-window top- k queries on uncertain streams,” VLDB J., vol. 19, no. 3, pp. 411–435, 2010.
[17]T. S. Venkatesh, E. R. Kumar, and S. S. Reddy, “Dispensation of Probabilistic Top-k Queries in Distributed Wireless Sensor Network,” Int. J. Res. Comput. Appl. Robot., vol. 2, no. 8, pp. 64–73, 2014.
[18]K. Yi, F. Li, G. Kollios, and D. Srivastava, “Efficient Processing of Top- k Queries in Uncertain Databases,” in IEEE Transaction on Knowledge and Data Engineering, 2008, pp. 1669–1682.
[19]K. Tangwongsan and M. Hirzel, “General Incremental Sliding-Window Aggregation,” in Proceding of The VLDB Endowment, 2015, pp. 702–713.
[20]O. Papapetrou, M. Garofalakis, and A. Deligiannakis, “Sketch-based Querying of Distributed Sliding-Window Data Streams,” in 38th Conference on Vry Large Data Bases, 2012, pp. 992–1003.
[21]M. Kontaki, A. N. Papadopoulos, and Y. Manolopoulos, “Continuous Top- k Dominating Queries,” IEEE Trans. Knowl. Data Eng., vol. 24, no. 5, pp. 840–853, 2012.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔