本文選題：大規(guī)模圖數(shù)據(jù) + NoSQL��； 參考：《沈陽航空航天大學(xué)》2017年碩士論文

【摘要】：隨著云計(jì)算等新技術(shù)的快速發(fā)展、社交網(wǎng)絡(luò)等新型互聯(lián)網(wǎng)應(yīng)用的興起,人類獲取和存儲數(shù)據(jù)的規(guī)模正以前所未有的速度爆炸式增長,與大規(guī)模圖數(shù)據(jù)相關(guān)的技術(shù)變革成為學(xué)術(shù)界和工業(yè)界的熱點(diǎn)問題。針對大規(guī)模圖數(shù)據(jù)的可達(dá)查詢是一項(xiàng)基礎(chǔ)性查詢,在圖分析及處理中被頻繁使用,將一些復(fù)雜的查詢分解成包含多個可達(dá)查詢的操作集合,其高效處理具有重要意義�，F(xiàn)有的可達(dá)索引機(jī)制在面對大規(guī)模圖時(shí)呈現(xiàn)查詢效率低或索引代價(jià)過大的問題,為此,本文對大規(guī)模有向圖的可達(dá)查詢進(jìn)行了深入的研究。首先,提出了一種基于NoSQL的面向大規(guī)模圖數(shù)據(jù)的分布式可達(dá)性索引與查詢框架,在不破壞原圖中節(jié)點(diǎn)可達(dá)性的前提下,將大規(guī)模圖進(jìn)行劃分成若干個子圖作為預(yù)處理,通過創(chuàng)建跨邊集來保留原圖中各子圖間的可達(dá)性信息。由于子圖可達(dá)性保持算法保留原圖中各子圖內(nèi)節(jié)點(diǎn)間的可達(dá)性信息,從而使各子圖可并行生成可達(dá)性索引。其次,設(shè)計(jì)了基于所提框架的查詢處理算法。算法預(yù)先判斷查詢節(jié)點(diǎn)所屬子圖的可達(dá)性信息,可直接返回一部分不可達(dá)結(jié)果。對于一般查詢,最多進(jìn)行兩次子圖內(nèi)部的可達(dá)性查詢即可返回查詢結(jié)果。最后,通過真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)與現(xiàn)有方法對比,驗(yàn)證了本文提出的基于NoSQL的面向大規(guī)模圖數(shù)據(jù)的分布式可達(dá)性索引與查詢框架在大規(guī)模稀疏圖和稠密圖上創(chuàng)建索引所需的時(shí)間短,生成的索引規(guī)模小,且具有良好的查詢性能。
[Abstract]:With the rapid development of new technologies such as cloud computing and the rise of new Internet applications such as social networks, the scale of human access to and storage of data is exploding at an unprecedented rate. The technological change related to large-scale map data has become a hot issue in academia and industry. The reachable query of large-scale graph data is a basic query, which is frequently used in graph analysis and processing. Some complex queries are decomposed into sets of operations containing multiple reachable queries, and its efficient processing is of great significance. The existing reachability indexing mechanism presents the problem of low query efficiency or excessive index cost in the face of large-scale graph. Therefore, this paper makes a deep research on the reachable query of large-scale directed graph. Firstly, a distributed reachability index and query framework for large-scale graph data based on NoSQL is proposed. Without destroying the reachability of nodes in the original graph, the large-scale graph is divided into several sub-graphs as preprocessing. By creating cross-edge sets, the reachability information between subgraphs in the original graph is preserved. Because the reachability preserving algorithm of subgraph preserves the reachability information between nodes in each subgraph of the original graph, each subgraph can generate reachability index in parallel. Secondly, the query processing algorithm based on the proposed framework is designed. The algorithm prejudges the reachability information of the subgraph of the query node and directly returns some unreachable results. For a general query, a maximum of two subgraphs within the reachability query can return the query results. Finally, the experiments of real data sets are compared with existing methods. It is verified that the proposed NoSQL based distributed reachability index and query framework for large scale graph data takes a short time to create indexes on large scale sparse graphs and dense graphs, and the generated indexes are small in size and have good query performance.
【學(xué)位授予單位】：沈陽航空航天大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 林宗振;;關(guān)于均勻錢幣投擲過程的可達(dá)性[J];暨南理醫(yī)學(xué)報(bào)(理科專版);1985年03期

2 許世蒙,張玉忠;有交易費(fèi)的折算資產(chǎn)優(yōu)化性質(zhì)和可達(dá)性[J];控制理論與應(yīng)用;2002年01期

3 李平華,陸玉麒;可達(dá)性研究的回顧與展望[J];地理科學(xué)進(jìn)展;2005年03期

4 賈鵬;劉瑞菊;楊忠振;;基于陸域和空域運(yùn)輸系統(tǒng)的空港可達(dá)性評價(jià)方法研究[J];經(jīng)濟(jì)地理;2013年06期

5 姜海寧;譚石柳;;軌道交通建設(shè)對金華城鎮(zhèn)可達(dá)性格局的影響[J];浙江師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期

6 劉俊;陸玉麒;;江蘇省公路交通網(wǎng)絡(luò)可達(dá)性評價(jià)研究[J];南京師大學(xué)報(bào)(自然科學(xué)版);2008年03期

7 劉志林;王茂軍;;北京市職住空間錯位對居民通勤行為的影響分析——基于就業(yè)可達(dá)性與通勤時(shí)間的討論[J];地理學(xué)報(bào);2011年04期

8 蔣曉威;曹衛(wèi)東;羅健;朱勝清;唐云云;;安徽省公路網(wǎng)絡(luò)可達(dá)性空間格局及其演化[J];地理科學(xué)進(jìn)展;2012年12期

9 劉俊;陸玉麒;孟德友;;基于不同指標(biāo)的公路交通網(wǎng)絡(luò)可達(dá)性評價(jià)——以江蘇省為例[J];工業(yè)技術(shù)經(jīng)濟(jì);2009年02期

10 袁立科;張宗益;;創(chuàng)新系統(tǒng)的區(qū)域可達(dá)性研究[J];科研管理;2007年01期

相關(guān)會議論文 前10條

1 苗梅;Gerhard Weber;;推廣可達(dá)性[A];第四屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會議論文集[C];2008年

2 呂斌;張純;陳天鳴;;城市低收入群體的就業(yè)可達(dá)性變化研究:以北京為例[A];多元與包容——2012中國城市規(guī)劃年會論文集(13.城市規(guī)劃管理)[C];2012年

3 裴玉龍;蓋春英;;公路網(wǎng)絡(luò)可達(dá)性研究[A];科技、工程與經(jīng)濟(jì)社會協(xié)調(diào)發(fā)展——中國科協(xié)第五屆青年學(xué)術(shù)年會論文集[C];2004年

4 尹海偉;徐建剛;祁毅;;上海公園空間可達(dá)性與公平性分析[A];中國地理學(xué)會2007年學(xué)術(shù)年會論文摘要集[C];2007年

5 張莉;陸玉麒;趙元正;;基于可達(dá)性的長江三角洲城市一日交流圈的動態(tài)變化研究[A];地理學(xué)核心問題與主線——中國地理學(xué)會2011年學(xué)術(shù)年會暨中國科學(xué)院新疆生態(tài)與地理研究所建所五十年慶典論文摘要集[C];2011年

6 孟德友;范況生;高超;;鐵路客運(yùn)提速前后省際可達(dá)性及空間格局分析[A];中國地理學(xué)會百年慶典學(xué)術(shù)論文摘要集[C];2009年

7 劉志林;王茂軍;;北京市職住空間錯位對居民通勤行為的影響分析——基于就業(yè)可達(dá)性與通勤時(shí)間的討論[A];中國地理學(xué)會百年慶典學(xué)術(shù)論文摘要集[C];2009年

8 張宇;張英杰;張曉東;鄭猛;;北京市區(qū)位可達(dá)性對房價(jià)影響分析[A];規(guī)劃創(chuàng)新：2010中國城市規(guī)劃年會論文集[C];2010年

9 朱琛;孫姍珊;;城市不同居住區(qū)位群體就業(yè)可達(dá)性差異研究——以上海市為例[A];城市時(shí)代，協(xié)同規(guī)劃——2013中國城市規(guī)劃年會論文集（07-居住區(qū)規(guī)劃與房地產(chǎn)）[C];2013年

10 楊育軍;;可達(dá)性評價(jià)方法的比較:一種基于GIS的實(shí)證方法[A];中國地理信息系統(tǒng)協(xié)會第八屆年會論文集[C];2004年

相關(guān)碩士學(xué)位論文 前10條

1 丁振;既有路網(wǎng)下基于中小城市的快速通道網(wǎng)布局研究[D];西南交通大學(xué);2015年

2 彭\~\~;基于區(qū)間標(biāo)記索引的可達(dá)性查詢設(shè)計(jì)及其在外包數(shù)據(jù)庫中的應(yīng)用[D];哈爾濱工業(yè)大學(xué);2014年

3 薛鵬;圖數(shù)據(jù)上可達(dá)性查詢關(guān)鍵技術(shù)研究[D];東北大學(xué);2014年

4 李建新;基于可達(dá)性的南昌市區(qū)域空間效應(yīng)研究[D];江西師范大學(xué);2015年

5 劉紅;基于老年人游憩特征的長沙市公園可達(dá)性研究[D];湖南師范大學(xué);2015年

6 王于楠;基于公路可達(dá)性的青海省人口時(shí)空格局演變研究[D];青海師范大學(xué);2016年

7 李U，

本文編號：1969820