TY - GEN
T1 - Fast subgraph isomorphism detection for graph-based retrieval
AU - Weber, Markus
AU - Langenhan, Christoph
AU - Roth-Berghofer, Thomas
AU - Liwicki, Marcus
AU - Dengel, Andreas
AU - Petzold, Frank
PY - 2011
Y1 - 2011
N2 - In this paper we present a method for a graph-based retrieval and its application in architectural floor plan retrieval. The proposed method is an extension of a well-known method for subgraph matching. This extension significantly reduces the storage amount and indexing time for graphs where the nodes are labeled with a rather small amount of different classes. In order to reduce the number of possible permutations, a weight function for labeled graphs is introduced and a well-founded total order is defined on the weights of the labels. Inversions which violate the order are not allowed. A computational complexity analysis of the new preprocessing is given and its completeness is proven. Furthermore, in a number of practical experiments with randomly generated graphs the improvement of the new approach is shown. In experiments performed on random sample graphs, the number of permutations has been decreased to a fraction of 10 -18 in average compared to the original approach by Messmer. This makes indexing of larger graphs feasible, allowing for fast detection of subgraphs.
AB - In this paper we present a method for a graph-based retrieval and its application in architectural floor plan retrieval. The proposed method is an extension of a well-known method for subgraph matching. This extension significantly reduces the storage amount and indexing time for graphs where the nodes are labeled with a rather small amount of different classes. In order to reduce the number of possible permutations, a weight function for labeled graphs is introduced and a well-founded total order is defined on the weights of the labels. Inversions which violate the order are not allowed. A computational complexity analysis of the new preprocessing is given and its completeness is proven. Furthermore, in a number of practical experiments with randomly generated graphs the improvement of the new approach is shown. In experiments performed on random sample graphs, the number of permutations has been decreased to a fraction of 10 -18 in average compared to the original approach by Messmer. This makes indexing of larger graphs feasible, allowing for fast detection of subgraphs.
KW - Architecture
KW - graph theory
KW - retrieval
UR - http://www.scopus.com/inward/record.url?scp=84856830848&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-23291-6_24
DO - 10.1007/978-3-642-23291-6_24
M3 - Conference contribution
AN - SCOPUS:84856830848
SN - 9783642232909
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 319
EP - 333
BT - Case-Based Reasoning Research and Development - 19th International Conference on Case-Based Reasoning, ICCBR 2011, Proceedings
T2 - 19th International Conference on Case-Based Reasoning, ICCBR 2011
Y2 - 12 September 2011 through 15 September 2011
ER -