SAPPER: subgraph indexing and approximate matching in large graphs. With the emergence of new applications, e.g., computational biology, new software engineering techniques, social networks, etc., more data is in the form of graphs. Locating occurrences of a query graph in a large database graph is an important research topic. Due to the existence of noise (e.g., missing edges) in the large database graph, we investigate the problem of approximate subgraph indexing, i.e., finding the occurrences of a query graph in a large database graph with (possible) missing edges. The SAPPER method is proposed to solve this problem. Utilizing the hybrid neighborhood unit structures in the index, SAPPER takes advantage of pre-generated random spanning trees and a carefully designed graph enumeration order. Real and synthetic data sets are employed to demonstrate the efficiency and scalability of our approximate subgraph indexing method.
Keywords for this software
References in zbMATH (referenced in 5 articles )
Showing results 1 to 5 of 5.
- Li, Guanfeng; Yan, Li; Ma, Zongmin: An approach for approximate subgraph matching in fuzzy RDF graph (2019)
- Cuzzocrea, Alfredo; Cosulschi, Mirel; de Virgilio, Roberto: An effective and efficient MapReduce algorithm for computing BFS-based traversals of large-scale RDF graphs (2016)
- 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)
- Lee, Chun-Hee; Chung, Chin-Wan: Efficient search in graph databases using cross filtering (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)