請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50133
標題: | 以非同步交易資訊來決定串流圖切接問題之分散式圖資料庫的搜尋速度優化 The Query Speed Improvement on Distributed Graph Database Using Streaming Graph Partitioning Strategy with Asynchronous Transaction Information |
作者: | Li-Yuan Hung 洪立遠 |
指導教授: | 廖世偉 |
關鍵字: | 串流圖切接,非同步交易,圖資料庫, streaming graph partitioning,asynchronous transaction,graph database, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | 在本篇論文中,我們提出了一個在分散式圖資料庫系統中,藉由非同步交易的方式,延遲交易時間的概念,而採用這樣子的概念與方式可以搜集到更多的資訊,去更好地解決串流圖切割的問題,進而使得搜尋的速度加快。在利用非同步交易所得來的資訊上,我們提出了三種策略:『全局最大機率』,『連通組件最大機率』以及『獨立層遞』。與現行默認的隨機分配策略相比,我們所提出的策略中,『連通組件最大機率』策略為最佳,可以在搜尋的測試情境下,達到平均起來的搜尋加速。而搜尋加速的效果,在『鄰居的鄰居』以及『最短路徑』這兩種搜尋情境下為最顯著,我們認為其原因是這兩種搜尋情境中,有較多的圖上遍歷,所以我們提出的策略所帶來的資料在地性,就使得網路傳輸開銷較少,造成較顯著的加速。 In this research, we propose an idea to delay the commit time in a dis-tributed graph database by the asynchronous transaction. In this way, moreinformation can be gathered to make better streaming graph partitioning de-cision and that will lead to faster query speed afterwards. We propose threestrategies: global max-probability, connected-component max-probability,and independent cascade. Compared with default random graph partitioning strategy,our best connected-component max-probability strategy can have an positive average query speed improvement.The query speed improvement is most effective in query FNoN and FSPand we conclude that’s because the intensive traversal in these two queriesbenefit more from the data locality. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50133 |
DOI: | 10.6342/NTU201601879 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 424.03 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。