Research On Reachability Index Of Social Network Graph Based NoSQL

With the rapid development of new technologies such as cloud computing,the rise of new Internet applications such as social networks,the scale of human acquisition and storage of data is increasing at an unprecedented rate.Technological changes associated with large graph have become a hot topic in academia and industry.For large graph,the reachable query is a basic query that is frequently used in graph analysis and processing.Some complex queries can be decomposed into a set of operations that contain multiple reachable queries,and its efficient handling is important.Existing reachable indexing methods present low query efficiency or excessive index cost in the face of large graphs.So this paper makes an in-depth study of the reachable query of large directed graphs.Firstly,a distributed reachability index and query framework for large graph based on NoSQL is proposed.This method divides the large graph into several subgraphs without destroying the reachability of the nodes as preprocessing and creates a connecting-edge set to preserve reachability information between sub-graphs.As it preserves the reachability information among the nodes in the subgraphs of the original graph by the sub-graph reachability preserving algorithm.Thus each subgraph can generates the reachability index in parallel.Secondly,a query processing algorithm based on the proposed framework is designed.The algorithm can judge the reachability information of the subgraphs to which the query node belongs,and can directly return some unreachable results.For general queries,up to twice the accessibility query within the subgraph can return query results.Finally,experiments with real data sets are compared to existing methods.It verifies that the framework proposed in this paper can reduce the time of creating indexes on large scale graphs and the size of the indexes,and have good query performance.