Effective graph indexing model for graph containment search
Cheng Guang-hua · Journal of Computer Applications · 2008
Due to the wide use of graph models,fast containment search of graph data finds many applications in various domains.Given a set of model graphs D and a query graph q,in comparison to traditional graph search that retrieves all the graphs containing q(q■g),containment search has its own indexing characteristics that have not yet been examined.In this paper,we performed a systematic study on these characteristics and proposed a contrast subgraph-based indexing model,called csgIndex.Using a redundancy-aware feature selection process,csgIndex can sort out a set of significant and distinctive contrast subgraphs and maximize its indexing capability.Experimental results on real test data show that csgIndex achieves near-optimal pruning power on various containment search workloads,and demonstrates its obvious advantage over indices built for traditional graph search in this new scenario.