The structure-mapping engine: Algorithm and examples

This paper describes the structure-mapping engine (SME), a program for studying analogical processing. SME has been built to explore Gentner's structure-mapping theory of analogy, and provides a “tool kit” for constructing matching algorithms consistent with this theory. Its flexibility enhances cognitive simulation studies by simplifying experimentation. Furthermore, SME is very efficient, making it a useful component in machine learning systems as well. We review the structure-mapping theory and describe the design of the engine. We analyze the complexity of the algorithm, and demonstrate that most of the steps are polynomial, typically bounded by O(N2).