SQBC: An efficient subgraph matching method over large and dense graphs

Recent progress in biology and computer science have generated many complicated networks, most of which can be modeled as large and dense graphs. Developing effective and efficient subgraph match methods over these graphs is urgent, meaningful and necessary. Although some excellent exploratory approaches have been proposed these years, they show poor performances when the graphs are large and dense. This paper presents a novel Subgraph Query technique Based on Clique feature, called SQBC, which integrates the carefully designed clique encoding with the existing vertex encoding 1401 as the basic index unit to reduce the search space. Furthermore, SQBC optimizes the subgraph isomorphism test based on clique features. Extensive experiments over biological networks, RDF dataset and synthetic graphs have shown that SQBC outperforms the most popular competitors both in effectiveness and efficiency especially when the data graphs are large and dense. (C) 2013 Elsevier Inc. All rights reserved.