基于NoSQL的社交网络图数据可达性索引技术研究

发布时间：2018-06-02 18:52

本文选题：大规模图数据 + NoSQL　；参考：《沈阳航空航天大学》2017年硕士论文

【摘要】：随着云计算等新技术的快速发展、社交网络等新型互联网应用的兴起,人类获取和存储数据的规模正以前所未有的速度爆炸式增长,与大规模图数据相关的技术变革成为学术界和工业界的热点问题。针对大规模图数据的可达查询是一项基础性查询,在图分析及处理中被频繁使用,将一些复杂的查询分解成包含多个可达查询的操作集合,其高效处理具有重要意义。现有的可达索引机制在面对大规模图时呈现查询效率低或索引代价过大的问题,为此,本文对大规模有向图的可达查询进行了深入的研究。首先,提出了一种基于NoSQL的面向大规模图数据的分布式可达性索引与查询框架,在不破坏原图中节点可达性的前提下,将大规模图进行划分成若干个子图作为预处理,通过创建跨边集来保留原图中各子图间的可达性信息。由于子图可达性保持算法保留原图中各子图内节点间的可达性信息,从而使各子图可并行生成可达性索引。其次,设计了基于所提框架的查询处理算法。算法预先判断查询节点所属子图的可达性信息,可直接返回一部分不可达结果。对于一般查询,最多进行两次子图内部的可达性查询即可返回查询结果。最后,通过真实数据集的实验与现有方法对比,验证了本文提出的基于NoSQL的面向大规模图数据的分布式可达性索引与查询框架在大规模稀疏图和稠密图上创建索引所需的时间短,生成的索引规模小,且具有良好的查询性能。
[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.
【学位授予单位】：沈阳航空航天大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】