DSI: A Method for Indexing Large Graphs Using Distance Set
Recent years we have witnessed a great increase in modeling data as large graphs in multiple domains, such as XML, the semantic web, social network. In these circumstances, researchers are interested in querying the large graph like that: Given a large graph G, and a query Q, we report all the matches of Q in G. Since subgraph isomorphism check ing is proved to be NP-Complete1, it is infeasible to scan the whole large graph for answers, especially when the querys size is also large. Hence, the filter-verification approach is widely adopted. In this approach, re searchers first index the neighborhood of each vertex in the large graph, then filter vertexes, and finally perform subgraph matching algorithms. Previous techniques mainly focus on efficient matching algorithms, pay ing little attention to indexing techniques. However, appropriate indexing techniques could help improve the efficiency of query response by gen erating less candidates. In this paper we investigate indexing techniques on large graphs, and propose an index structure DSI(Distance Set In dex) to capture the neighborhood of each vertex. Through our distance set index, more vertexes could be pruned, resulting in a much smaller search space. Then a subgraph matching algorithm is performed in the search space. We have applied our index structure to real datasets and synthetic datasets. Extensive experiments demonstrate the efficiency and effectiveness of our indexing technique.
Graph Indexing Distance Set
Yubo Kou Yukun Li Xiaofeng Meng
Renmin University of China, Beijing, China
国际会议
11th International Conference,WAIM 2010(第十一届网络时代管理国际会议)
九寨沟
英文
297-308
2010-07-14（万方平台首次上网日期，不代表论文的发表时间）