請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50133完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 廖世偉 | |
| dc.contributor.author | Li-Yuan Hung | en |
| dc.contributor.author | 洪立遠 | zh_TW |
| dc.date.accessioned | 2021-06-15T12:30:33Z | - |
| dc.date.available | 2016-08-24 | |
| dc.date.copyright | 2016-08-24 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-08-04 | |
| dc.identifier.citation | [1]Ian Robinson, Jim Webber & Emil Eifrem Graph Databases, Second Edition NeoTechnology, Inc. 2015.
[2]Marek Ciglan, Alex Averbuch, Ladialav Hluchy Benchmarking traversal operations over graph databases, Slovakia Swedish Institute of Computer Science Stockholm, Sweden, 2012. [3]Robert McColl, David Ediger, Jason Poovey, Dan Campbell, David A. Bader A Per-formance Evaluation of Open Source Graph Databases. Georgia Institute of Technol-ogy, 2014. [4]K. Andreev and H. Racke. Balanced graph partitions. Theory of Computing Systems39:929–939, 2006. [5]G.KarypisandV.Kumar.MultilevelgraphpartitioningschemesInICPP,pages113–122, 1995 [6]S.Barnard.PMRSB:Parallelmultilevelrecursivespectralbisection.InSupercomput-ing, 1995 [7]B. Hendrickson and R. Leland A multilevel algorithm for partitioning graphs. In Su-percomputing, 1995 [8]Isabelle Stanton, Gabriel Kliot Streaming Graph Partitioning for Large DistributedGraphs University of California Berkeley, Microsoft Research, 2012 [9]Do, L., and Ram, P., , State of the Art of Asynchronous Transaction Mgt. BoeingTech. Report SSGTECH 98-016. [10]Lyman Do, Prabhu Ram, and Pamela Drew The Need for Distributed AsynchronousTransactions Boeing Phantom Works, Mathematics and Computing Technologies,1999. [11]David Kempe1, Jon Kleinberg, and Eva Tardos Influential Nodes in a DiffusionModelforSocialNetworksDepartmentof ComputerScience, UniversityofSouthernCalifornia Department of Computer Science, Cornell University [12]SNAP, egonets-Facebookhttp://snap.stanford.edu/data/egonets-Facebook.htmlJune, 2014 [13]SNAP, email-Enronhttp://snap.stanford.edu/data/email-Enron.htmlJune,2014 [14]SNAP, cit-HepThhttp://snap.stanford.edu/data/cit-HepTh.htmlJune, 2014 [15]SNAP, web-Stanfordhttp://snap.stanford.edu/data/web-Stanford.htmlJune,2014 [16]Titan Graph Databasehttp://titan.thinkaurelius.com [17]Apache Cassandra.http://incubator.apache.org/cassandra/ [18]Apache HBase.http://hadoop.apache.org/hbase/ [19]Oracle Berkeley DBhttp://www.oracle.com/us/products/database/berkeley-db/overview/index.html [20]S. Gilbert and N. Lynch. Brewer’s Conjecture and the Feasibility of Consistent,Available, Partition-TolerantWebServicesACMSIGACTNews, 33(2):51–59, 2002 [21]Salim Jouili, Valentin Vansteenberghe An empirical comparison of graph databasesEura Nova R&D, Universite Catholique de Louvain, 2013 [22]graphdb-benchmarkshttps://github.com/socialsensor/graphdb-benchmarks [23]Marko A. Rodriguez. The Gremlin Graph Traversal Machine agnd Language (In-vited Talk) In Proceedings of the 15th Symposium on Database Programming Lan-guages, DBPL 2015, pages 1–10, New York, NY, USA, 2015. ACM. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50133 | - |
| dc.description.abstract | 在本篇論文中，我們提出了一個在分散式圖資料庫系統中，藉由非同步交易的方式，延遲交易時間的概念，而採用這樣子的概念與方式可以搜集到更多的資訊，去更好地解決串流圖切割的問題，進而使得搜尋的速度加快。在利用非同步交易所得來的資訊上，我們提出了三種策略：『全局最大機率』，『連通組件最大機率』以及『獨立層遞』。與現行默認的隨機分配策略相比，我們所提出的策略中，『連通組件最大機率』策略為最佳，可以在搜尋的測試情境下，達到平均起來的搜尋加速。而搜尋加速的效果，在『鄰居的鄰居』以及『最短路徑』這兩種搜尋情境下為最顯著，我們認為其原因是這兩種搜尋情境中，有較多的圖上遍歷，所以我們提出的策略所帶來的資料在地性，就使得網路傳輸開銷較少，造成較顯著的加速。 | zh_TW |
| dc.description.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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T12:30:33Z (GMT). No. of bitstreams: 1 ntu-105-R03922096-1.pdf: 434209 bytes, checksum: f9485fd9fe2a9ce2e78dc6150245ac69 (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 致謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .i
摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .ii Abstract. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .iii 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 2 Related Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 3 Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 3.1 Transaction Commit . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 3.2 Streaming Graph Partitioning Strategy . . . . . . . . . . . . . . . . . . .9 4 Experiment Setup. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 4.1 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 4.2 Stream Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 4.3 Transaction Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13 4.4 Query Workload . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13 4.5 Graph Database Environment . . . . . . . . . . . . . . . . . . . . . . . .15 4.6 Hardware Environment . . . . . . . . . . . . . . . . . . . . . . . . . . .15 5 Experiment Results. . . . . . . . . . . . . . . . . . .16 5.1 Time improvement of asynchronous transaction commit . . . . . . . . .16 5.2 Default Partitioning Strategy . . . . . . . . . . . . . . . . . . . . . . . .17 5.3 Experiment Detail on Facebook Dataset . . . . . . . . . . . . . . . . . .18 5.4 Experiment Detail on cit-HepTh Dataset . . . . . . . . . . . . . . . . . .19 5.5 Experiment Detail of CCMP on Each Computer on Facebook Dataset . .20 6 Conclusion. . . . . . . . . . . . . . . . . . .21 7 Future Work. . . . . . . . . . . . . . . . . . .22 Bibliography. . . . . . . . . . . . . . . . . . .24 | |
| dc.language.iso | en | |
| dc.subject | 圖資料庫 | zh_TW |
| dc.subject | 串流圖切接 | zh_TW |
| dc.subject | 非同步交易 | zh_TW |
| dc.subject | asynchronous transaction | en |
| dc.subject | graph database | en |
| dc.subject | streaming graph partitioning | en |
| dc.title | 以非同步交易資訊來決定串流圖切接問題之分散式圖資料庫的搜尋速度優化 | zh_TW |
| dc.title | The Query Speed Improvement on Distributed Graph Database Using Streaming Graph Partitioning Strategy with Asynchronous Transaction Information | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 蘇中才,黃維中 | |
| dc.subject.keyword | 串流圖切接,非同步交易,圖資料庫, | zh_TW |
| dc.subject.keyword | streaming graph partitioning,asynchronous transaction,graph database, | en |
| dc.relation.page | 26 | |
| dc.identifier.doi | 10.6342/NTU201601879 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-08-05 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf 未授權公開取用 | 424.03 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。