以非同步交易資訊來決定串流圖切接問題之分散式圖資料庫的搜尋速度優化

Abstract

在本篇論文中，我們提出了一個在分散式圖資料庫系統中，藉由非同步交易的方式，延遲交易時間的概念，而採用這樣子的概念與方式可以搜集到更多的資訊，去更好地解決串流圖切割的問題，進而使得搜尋的速度加快。在利用非同步交易所得來的資訊上，我們提出了三種策略：『全局最大機率』，『連通組件最大機率』以及『獨立層遞』。與現行默認的隨機分配策略相比，我們所提出的策略中，『連通組件最大機率』策略為最佳，可以在搜尋的測試情境下，達到平均起來的搜尋加速。而搜尋加速的效果，在『鄰居的鄰居』以及『最短路徑』這兩種搜尋情境下為最顯著，我們認為其原因是這兩種搜尋情境中，有較多的圖上遍歷，所以我們提出的策略所帶來的資料在地性，就使得網路傳輸開銷較少，造成較顯著的加速。

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.