TALE: A Tool for Approximate Large Graph Matching. Large graph datasets are common in many emerging database applications, and most notably in large-scale scientific applications. To fully exploit the wealth of information encoded in graphs, effective and efficient graph matching tools are critical. Due to the noisy and incomplete nature of real graph datasets, approximate, rather than exact, graph matching is required. Furthermore, many modern applications need to query large graphs, each of which has hundreds to thousands of nodes and edges. This paper presents a novel technique for approximate matching of large graph queries. We propose a novel indexing method that incorporates graph structural information in a hybrid index structure. This indexing technique achieves high pruning power and the index size scales linearly with the database size. In addition, we propose an innovative matching paradigm to query large graphs. This technique distinguishes nodes by their importance in the graph structure. The matching algorithm first matches the important nodes of a query and then progressively extends these matches. Through experiments on several real datasets, this paper demonstrates the effectiveness and efficiency of the proposed method.
Keywords for this software
References in zbMATH (referenced in 8 articles )
Showing results 1 to 8 of 8.
- Li, Guanfeng; Yan, Li; Ma, Zongmin: An approach for approximate subgraph matching in fuzzy RDF graph (2019)
- Wang, Hongzhi; Li, Ning; Li, Jianzhong; Gao, Hong: Parallel algorithms for flexible pattern matching on big graphs (2018)
- Pal, Dipali; Rao, Praveen; Slavov, Vasil; Katib, Anas: Fast processing of graph queries on a large database of small and medium-sized data graphs (2016)
- Kostakis, Orestis: Classy: fast clustering streams of call-graphs (2014) ioport
- Lee, Chun-Hee; Chung, Chin-Wan: Efficient search in graph databases using cross filtering (2014)
- Ma, Shuai; Cao, Yang; Fan, Wenfei; Huai, Jinpeng; Wo, Tianyu: Strong simulation: capturing topology in graph pattern matching (2014)
- Zheng, Weiguo; Zou, Lei; Lian, Xiang; Zhang, Huaming; Wang, Wei; Zhao, Dongyan: SQBC: an efficient subgraph matching method over large and dense graphs (2014)
- Zhu, Linhong; Ng, Wee Keong; Cheng, James: Structure and attribute index for approximate graph matching in large graphs (2011) ioport