Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Artificial Intelligence Review
Published in: Artificial Intelligence Review 7/2020

27-02-2020

An overview of distance and similarity functions for structured data

Author: Santiago Ontañón

Published in: Artificial Intelligence Review | Issue 7/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The notions of distance and similarity play a key role in many machine learning approaches, and artificial intelligence in general, since they can serve as an organizing principle by which individuals classify objects, form concepts and make generalizations. While distance functions for propositional representations have been thoroughly studied, work on distance functions for structured representations, such as graphs, frames or logical clauses, has been carried out in different communities and is much less understood. Specifically, a significant amount of work that requires the use of a distance or similarity function for structured representations of data usually employs ad-hoc functions for specific applications. Therefore, the goal of this paper is to provide an overview of this work to identify connections between the work carried out in different areas and point out directions for future work.
previous article Deep hashing for multi-label image retrieval: a survey
next article A deep granular network with adaptive unequal-length granulation strategy for long-term time series forecasting and its industrial applications

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
Notice that in the description logics notation, subsumption is written in the reverse order since it is seen as “set inclusion” of their interpretations. Here, \(x_1 \sqsubseteq x_2\) means that \(x_1\) is more general than \(x_2\), while in description logics it has the opposite meaning.
 
2
Interestingly, the Weisfeiler–Lehman test is related to the expressive power of Graph Neural Networks (discussed in Sect. 3.5), as it has been shown that a some classes of GNNs are at least as powerful as the Weisfeiler–Lehman in detecting graph isomorphism (Xu et al. 2018).
 
Literature
Aamodt A, Plaza E (1994) Case-based reasoning: foundational issues, methodological variations, and system approaches. Artif Intell Commun 7(1):39–59
Abu-Khzam FN, Samatova NF, Rizk MA, Langston MA (2007) The maximum common subgraph problem: faster solutions via vertex cover. In: IEEE/ACS international conference on computer systems and applications, 2007. AICCSA’07. IEEE, pp 367–373
Agrawal R, Faloutsos C, Swami A (1993) Efficient similarity search in sequence databases. In: International conference on foundations of data organization and algorithms. Springer, pp 69–84
Aha DW, Kibler D, Albert MK (1991) Instance-based learning algorithms. Mach Learn 6(1):37–66
Almohamad H, Duffuaa SO (1993) A linear programming approach for the weighted graph matching problem. IEEE Trans Pattern Anal Mach Intell 15(5):522–525
Armengol E, Plaza E (2001) Similarity assessment for relational cbr. In: International conference on case-based reasoning. Springer, pp 44–58
Armengol E, Plaza E (2002) Similarity of structured cases in CBR. In: Proceedings from the CCIA held in Castellon, Spain
Assali AA, Lenne D, Debray B (2009) Case retrieval in ontology-based cbr systems. In: Annual conference on artificial intelligence. Springer, pp 564–571
Baader F, Calvanese D, McGuinness DL, Nardi D, Patel-Schneider PF (eds) (2003) The description logic handbook: theory, implementation, and applications. Cambridge University Press, CambridgeMATH
Baader F, Horrocks I, Sattler U (2005) Description logics as ontology languages for the semantic web. In: Hutter D, Stephan W (eds) Mechanizing mathematical reasoning. Springer, pp 228–248
Babai L (2018) Groups, graphs, algorithms: the graph isomorphism problem. In: Proceedings of international congress of mathematicians 2018
Badea L, Nienhuys-Cheng SH (1999) A refinement operator for description logics. In: Cussens J, Frisch A (eds) Inductive logic programming, no. 1866 in Lecture notes in computer science. Springer, pp 40–59
Battaglia PW, Hamrick JB, Bapst V, Sanchez-Gonzalez A, Zambaldi V, Malinowski M, Tacchetti A, Raposo D, Santoro A, Faulkner R et al (2018) Relational inductive biases, deep learning, and graph networks. arXiv:180601261
Bellet A, Habrard A, Sebban M (2012) Good edit similarity learning by loss minimization. Mach Learn 89(1–2):5–35MathSciNetMATH
Bellet A, Habrard A, Sebban M (2013) A survey on metric learning for feature vectors and structured data. arXiv:13066709
Bergmann R, Stahl A (1998) Similarity measures for object-oriented case representations. In: Advances in case-based reasoning, pp 25–36
Bergmann R, Gil Y (2014) Similarity assessment and efficient retrieval of semantic workflows. Inf Syst 40:115–127
Bergmann R, Kolodner J, Plaza E (2005) Representation in case-based reasoning. Knowl Eng Rev 20(3):209–213
Bille P (2005) A survey on tree edit distance and related problems. Theor Comput Sci 337(1):217–239MathSciNetMATH
Bisson G (1990) Kbg: a knowledge based generalizer. In: Porter B, Mooney R (eds) Machine learning proceedings 1990. Elsevier, Amsterdam, pp 9–15
Bisson G (1992) Learing in FOL with a similarity measure. In: Proceedings of AAAI, vol 1992, pp 82–87
Borgida A, Walsh TJ, Hirsh H et al (2005) Towards measuring similarity in description logics. Descr Log 147
Bournaud I, Courtine M, Jean-Daniel Z (2002) Propositionalization for clustering symbolic relational descriptions. In: International conference on inductive logic programming. Springer, pp 1–16
Bunke H (1997) On a relation between graph edit distance and maximum common subgraph. Pattern Recogn Lett 18(8):689–694
Bunke H (1999) Error correcting graph matching: on the influence of the underlying cost function. IEEE Trans Pattern Anal Mach Intell 21(9):917–922
Bunke H (2000) Graph matching: theoretical foundations, algorithms, and applications. Proc Vis Interface 2000:82–88
Bunke H, Shearer K (1998) A graph distance metric based on the maximal common subgraph. Pattern Recogn Lett 19(3):255–259MATH
Carpenter B (1992) The logic of typed feature structures. Cambridge University Press, New YorkMATH
Champin PA, Solnon C (2003) Measuring the similarity of labeled graphs. In: International conference on case-based reasoning, ICCBR. Springer
Chen PPS (1988) The entity-relationship model—toward a unified view of data. Readings in artificial intelligence and databases. Elsevier, Amsterdam, pp 98–111
Collins M, Duffy N (2002) Convolution kernels for natural language. In: Becker S, Thrun S, Obermayer K (eds) Advances in neural information processing systems. Vancouver, Canada, pp 625–632
Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching in pattern recognition. Int J Pattern Recogn Artif Intell 18(03):265–298
Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE Trans Inf Theory 13(1):21–27MATH
d’Amato C, Fanizzi N, Esposito F (2006) A dissimilarity measure for alc concept descriptions. In: Proceedings of the 2006 ACM symposium on applied computing. ACM, pp 1695–1699
d’Amato C, Staab S, Fanizzi N (2008) On the influence of description logics ontologies on conceptual similarity. In: Proceedings of the 16th international conference on knowledge engineering. Lecture notes in computer science, vol 5268. Springer, pp 48–63
Datar M, Immorlica N, Indyk P, Mirrokni VS (2004) Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the twentieth annual symposium on computational geometry. ACM, pp 253–262
de Vries GKD, de Rooij S (2015) Substructure counting graph kernels for machine learning from rdf data. Web Semant Sci Serv Agents World Wide Web 35:71–84
Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. Journal R Stat Soc Ser B (Methodol) 39:1–38MathSciNetMATH
Dobrushin RL (1970) Prescribing a system of random variables by conditional distributions. Theory Probab Appl 15(3):458–486MathSciNetMATH
Doyle PG, Snell JL (1984) Random walks and electric networks, vol 22. American Mathematical Society, ProvidenceMATH
Emde W, Wettschereck D (1996) Relational instance based learning. In: Saitta L (ed) Machine learning—proceedings 13th international conference on machine learning. Morgan Kaufmann Publishers, pp 122–130
Emele MC, Zajac R (1990) Typed unification grammars. In: Proceedings of the 13th conference on computational linguistics, vol 3. Association for Computational Linguistics, pp 293–298
Emmert-Streib F, Dehmer M, Shi Y (2016) Fifty years of graph matching, network alignment and network comparison. Inf Sci 346:180–197MathSciNetMATH
Ester M, Kriegel HP, Sander J, Xu X et al (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. Kdd 96:226–231
Falkenhainer B, Forbus KD, Gentner D (1989) The structure-mapping engine: algorithm and examples. Artif intell 41(1):1–63MATH
Fanizzi N, d’Amato C (2006) A declarative kernel for $\cal{ALC}$ concept descriptions. In: International symposium on methodologies for intelligent systems. Springer, pp 322–331
Fanizzi N, d’Amato C, Esposito F (2008) Learning with kernels in description logics. In: Zelezny F, Lavrac N (eds) Inductive logic programming. Springer, pp 210–225
Fernández ML, Valiente G (2001) A graph distance metric combining maximum common subgraph and minimum common supergraph. Pattern Recognition Letters 22(6):753–758MATH
French RM (2002) The computational modeling of analogy-making. Trends Cogn Sci 6(5):200–205
Gao X, Xiao B, Tao D, Li X (2010) A survey of graph edit distance. Pattern Anal Appl 13(1):113–129MathSciNetMATH
Gärtner T (2003) A survey of kernels for structured data. ACM SIGKDD Explor Newsl 5(1):49–58
Gärtner T, Lloyd JW, Flach PA (2002) Kernels for structured data. Springer, BerlinMATH
Gärtner T, Flach P, Wrobel S (2003) On graph kernels: Hardness results and efficient alternatives. In: Schölkopf B, Warmuth MK (eds) Learning theory and kernel machines. Springer, Berlin, pp 129–143MATH
Gärtner T, Lloyd JW, Flach PA (2004) Kernels and distances for structured data. Mach Learn 57(3):205–232MATH
Gentner D (1983) Structure-mapping: a theoretical framework for analogy. Cogn Sci 7(2):155–170
Getoor L, Taskar B (2007) Introduction to statistical relational learning. MIT Press, CambridgeMATH
Göker MH, Roth-Berghofer T (1999) The development and utilization of the case-based help-desk support system homer. Eng Appl Artif Intell 12(6):665–680
Goldstone RL, Medin DL, Gentner D (1991) Relational similarity and the nonindependence of features in similarity judgments. Cogn Psychol 23(2):222–262
Gollery M (2005) Bioinformatics: sequence and genome analysis. Clin Chem 51(11):2219–2219
Golub GH, Van Loan CF (2012) Matrix computations, vol 3. JHU Press, BaltimoreMATH
González-Calero PA, Díaz-Agudo B, Gómez-Albarrán M et al (1999) Applying dls for retrieval in case-based reasoning. In: In Proceedings of the 1999 description logics workshop (Dl’99). Linkopings Universitet, Citeseer
Haussler D (1999) Convolution kernels on discrete structures. Technical report, Department of Computer Science, University of California at Santa Cruz
Hearst MA, Dumais ST, Osuna E, Platt J, Scholkopf B (1998) Support vector machines. IEEE Intell Syst Their Appl 13(4):18–28
Heckerman D, Meek C, Koller D (2007) Probabilistic entity-relationship models, prms, and plate models. In: Getoor L, Taskar B (eds) Introduction to statistical relational learning, MIT Press, pp 201–238
Holyoak KJ, Koh K (1987) Surface and structural similarity in analogical transfer. Mem Cogn 15(4):332–340
Horváth T, Wrobel S, Bohnebeck U (2001) Relational instance-based learning with lists and terms. Mach Learn 43(1–2):53–80MATH
Horváth T, Gärtner T, Wrobel S (2004) Cyclic pattern kernels for predictive graph mining. In: Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 158–167
Hu B, Kalfoglou Y, Alani H, Dupplaw D, Lewis P, Shadbolt N (2006) Semantic metrics. In: International conference on knowledge engineering and knowledge management. Springer, pp 166–181
Hutchinson A (1997) Metrics on terms and clauses. In: ECML ’97: proceedings of the 9th European conference on machine learning. Lecture notes in computer science, vol 1224. Springer, pp 138–145
Itakura F (1975) Minimum prediction residual principle applied to speech recognition. IEEE Trans Acoust Speech Signal Process 23(1):67–72
Jaakkola T, Haussler D (1999) Exploiting generative models in discriminative classifiers. In: Solla SA, Leen TK, Müller K-R (eds) Advances in neural information processing systems. MIT Press, Denver, Colarado, pp 487–493
Janowicz K (2006) Sim-dl: towards a semantic similarity measurement theory for the description logic $\cal{ALCNR}$ in geographic information retrieval. In: OTM confederated international conferences “on the move to meaningful internet systems. Springer, pp 1681–1692
Jeh G, Widom J (2002) Simrank: a measure of structural-context similarity. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 538–543
Jiang JJ, Conrath DW (1997) Semantic similarity based on corpus statistics and lexical taxonomy. arXiv:cmp-lg/9709008
Kalfoglou Y, Schorlemmer M (2003) Ontology mapping: the state of the art. Knowl Eng Rev 18(1):1–31MATH
Kashima H, Koyanagi T (2002) Kernels for semi-structured data. ICML 2:291–298
Kashima H, Tsuda K, Inokuchi A (2003) Marginalized kernels between labeled graphs. In: Proceedings of the twentieth international conference (ICML 2003). AAAI Press, pp 321–328
Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39–43MATH
Kaufman L, Rousseeuw P (1987) Clustering by means of medoids. North-Holland, Amsterdam
Keogh E, Kasetty S (2003) On the need for time series data mining benchmarks: a survey and empirical demonstration. Data Min Knowl Discov 7(4):349–371MathSciNet
Klein PN (1998) Computing the edit-distance between unrooted ordered trees. In: European symposium on algorithms. Springer, pp 91–102
Kok S, Domingos P (2007) Statistical predicate invention. In: Proceedings of the 24th international conference on machine learning. ACM, pp 433–440
Kolmogorov AN (1965) Three approaches to the quantitative definition of information. Probl Inf Transm 1(1):1–7MathSciNet
Kramer S, Lavrač N, Flach P (2001) Propositionalization approaches to relational data mining. In: Dzeroski S, Lavrac N (eds) Relational data mining. Springer, pp 262–291
Krieger HU, Schäfer U (1995) Efficient parameterizable type expansion for typed feature formalisms
Krogel MA, Rawles S, Železnỳ F, Flach PA, Lavrač N, Wrobel S (2003) Comparative evaluation of approaches to propositionalization. In: International conference on inductive logic programming. Springer, pp 197–214
Kulis B, et al (2013) Metric learning: a survey. Found Trends® Mach Learn 5(4):287–364
Lavrac N, Dzeroski S (1994) Inductive logic programming. In: Fuchs NE, Gottlob G (eds) WLP. Springer, Berlion, pp 146–160
Lehmann J, Hitzler P (2007) A refinement operator based learning algorithm for the LC description logic. In: Blockeel H, Ramon J, Shavlik JW, Tadepalli P (eds) ILP. Lecture notes in computer science, vol 4894. Springer, Berlin, pp 147–160
Lehmann J, Haase C (2009) Ideal downward refinement in the EL description logic. In: Raedt LD (ed) ILP. Lecture notes in computer science, vol 5989. Springer, Berlin pp 73–87
Leishman D (1989) Analogy as a constrained partial correspondence over conceptual graphs. In: KR, pp 223–234
Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Dokl 10:707–710MathSciNet
Levi G (1973) A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo 9(4):341MathSciNetMATH
Li Y, Gu C, Dullien T, Vinyals O, Kohli P (2019) Graph matching networks for learning the similarity of graph structured objects. arXiv preprint arXiv:190412787
Lü L, Zhou T (2011) Link prediction in complex networks: a survey. Phys A Stat Mech Its Appl 390(6):1150–1170
Luss R, d’Aspremont A (2008) Support vector machine classification with indefinite kernels. In: Advances in neural information processing systems, pp 953–960
Mahé P, Ueda N, Akutsu T, Perret JL, Vert JP (2005) Graph kernels for molecular structure–activity relationship analysis with support vector machines. J Chem Inf Model 45(4):939–951
Manago M, Bergmann R, Conruyt N, Traphöner R, Pasley J, Le Renard J, Maurer F, Wess S, Althoff KD, Dumont S (1994) Casuel: a common case representation language. INRECA Consortium Available on the World-Wide Web at http://​wwwagr informatik unikl de/bergmann/casuel/CASUEL toc2 4
Marteau PF (2009) Time warp edit distance with stiffness adjustment for time series matching. IEEE Trans Pattern Anal Mach Intell 31(2):306–318
Miller GA (1995) Wordnet: a lexical database for english. Commun ACM 38(11):39–41
Minsky M (1974) A framework for representing knowledge, MIT-AI LAboratory Memo 306
Mishne G, De Rijke M (2004) Source code retrieval using conceptual similarity. In: Coupling approaches, coupling media and coupling languages for information retrieval, pp 539–554
Mitchell TM (1980) The need for biases in learning generalizations. Department of Computer Science, Laboratory for Computer Science Research, Rutgers Univ, New Jersey
Mitchell TM, Keller RM, Kedar-Cabelli ST (1986) Explanation-based generalization: a unifying view. Mach Learn 1(1):47–80
Montani S, Leonardi G, Quaglini S, Cavallini A, Micieli G et al (2015) A knowledge-intensive approach to process similarity calculation. Expert Syst Appl 42(9):4207–4215
Muggleton S, Lodhi H, Amini A, Sternberg MJ (2005) Support vector inductive logic programming. In: International conference on discovery science. Springer, pp 163–175
Munkres J (1957) Algorithms for the assignment and transportation problems. J Soc Ind Appl Math 5(1):32–38MathSciNetMATH
Needleman SB, Wunsch CD (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 48(3):443–453
Neuhaus M, Bunke H (2006a) A convolution edit kernel for error-tolerant graph matching. In: 18th international conference on pattern recognition, 2006. ICPR 2006, vol 4. IEEE, pp 220–223
Neuhaus M, Bunke H (2006b) Edit distance-based kernel functions for structural pattern classification. Pattern Recogn 39(10):1852–1863MATH
Neuhaus M, Bunke H (2007) Automatic learning of cost functions for graph edit distance. Inf Sci 177(1):239–247MathSciNetMATH
Ng AY, Jordan MI, Weiss Y et al (2002) On spectral clustering: analysis and an algorithm. Adv Neural Inf Process Syst 2:849–856
Nienhuys-Cheng SH (1997) Distance between Herbrand interpretations: a measure for approximations to a target concept. In: Lavrac N, Dzeroski S (eds) Inductive logic programming. Springer, Berlin, pp 213–226MATH
Nikolentzos G, Meladianos P, Limnios S, Vazirgiannis M (2018) A degeneracy framework for graph similarity. Proc IJCAI 2018:2595–2601
Ontañón S, Zhu J (2011) The SAM algorithm for analogy-based story generation. In: Seventh artificial intelligence and interactive digital entertainment conference
Ontañón S, Shokoufandeh A (2016) Refinement-based similarity measures for directed labeled graphs. In: International conference on case-based reasoning. Springer, pp 311–326
Ontañón S, Montaña JL, Gonzalez AJ (2014) A dynamic-bayesian network framework for modeling and evaluating learning from observation. Expert Syst Appl 41(11):5212–5226
Page L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: bringing order to the web. Technical report, Stanford InfoLab
Plaza E (1995) Cases as terms: a feature term approach to the structured representation of cases. In: International conference on case-based reasoning. Springer, pp 265–276
Plaza E, Armengol E, Ontañón S (2005) The explanatory power of symbolic similarity in case-based reasoning. Artif Intell Rev 24(2):145–161MATH
Plotkin GD (1970) A note on inductive generalization. In: Meltzer B, Michie D (eds) Machine intelligence, vol 5. Edinburgh University Press, Edinburgh, pp 153–163
Pons P, Latapy M (2005) Computing communities in large networks using random walks. In: International symposium on computer and information sciences. Springer, pp 284–293
Poole J, Campbell J (1995) A novel algorithm for matching conceptual and related graphs. In: International conference on conceptual structures. Springer, pp 293–307
Rada R, Mili H, Bicknell E, Blettner M (1989) Development and application of a metric on semantic nets. IEEE Trans Syst Man Cybern 19(1):17–30
Ralaivola L, Swamidass SJ, Saigo H, Baldi P (2005) Graph kernels for chemical informatics. Neural Netw 18(8):1093–1110
Ramon J, Bruynooghe M (1998) A framework for defining distances between first-order logic objects. In: International conference on inductive logic programming. Springer, pp 271–280
Ramon J, Gärtner T (2003) Expressivity versus efficiency of graph kernels. In: Proceedings of the first international workshop on mining graphs, trees and sequences, pp 65–74
Ramoni M, Sebastiani P, Cohen P (2002) Bayesian clustering by dynamics. Mach Learn 47(1):91–121MATH
Resnik P (1995) Using information content to evaluate semantic similarity in a taxonomy. arXiv:cmp-lg/9511007
Resnik P et al (1999) Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language. J Artif Intell Res: JAIR 11:95–130MATH
Riesen K, Bunke H (2008) Iam graph database repository for graph based pattern recognition and machine learning. In: da Vitoria Lobo N, Kasparis T, Roli F, Kwok JT, Georgiopoulos M, Anagnostopoulos GC, Loog M (eds) Structural, syntactic, and statistical pattern recognition. Springer, Orlando, pp 287–297
Riesen K, Bunke H (2009) Approximate graph edit distance computation by means of bipartite graph matching. Image Vis Comput 27(7):950–959
Rubner Y, Tomasi C, Guibas LJ (2000) The earth mover’s distance as a metric for image retrieval. Int J Comput Vis 40(2):99–121MATH
Sánchez-Ruiz AA, Ontañón S, González-Calero PA, Plaza E (2011) Measuring similarity in description logics using refinement operators. In: ICCBR, pp 289–303
Sánchez-Ruiz AA, Ontañón S, González-Calero PA, Plaza E (2016) Measuring similarity of individuals in description logics over the refinement space of conjunctive queries. J Intell Inf Syst 47(3):447–467
Sanfeliu A, Fu KS (1983) A distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybern 3:353–362MATH
Santini S, Jain R (1999) Similarity measures. IEEE Trans Pattern Anal Mach Intell 21(9):871–883
Schaaf JW (1996) Fish and shrink. A next step towards efficient case retrieval in large scaled case bases. In: European workshop on advances in case-based reasoning. Springer, pp 362–376
Schädler K, Wysotzki F (1999) Comparing structures using a hopfield-style neural network. Appl Intell 11(1):15–30
Sebag M (1997) Distance induction in first order logic. In: International conference on inductive logic programming. Springer, pp 264–272
Serra J, Arcos JL (2014) An empirical evaluation of similarity measures for time series classification. Knowl Based Syst 67:305–314
Shapiro LG, Haralick RM (1981) Structural descriptions and inexact matching. IEEE Trans Pattern Anal Mach Intell 5:504–519
Shervashidze N, Schweitzer P, van Leeuwen EJ, Mehlhorn K, Borgwardt KM (2011) Weisfeiler–Lehman graph kernels. J Mach Learn Res 12(1):2539–2561MathSciNetMATH
Shieber SM (2003) An introduction to unification-based approaches to grammar. Microtome Publishing, New YorkMATH
Singhal A (2001) Modern information retrieval: a brief overview. IEEE Data Eng Bull 24(4):35–43
Small H (1973) Co-citation in the scientific literature: a new measure of the relationship between two documents. J Assoc Inf Sci Technol 24(4):265–269MathSciNet
Smola AJ, Vishwanathan S (2003) Fast kernels for string and tree matching. In: Thrun S, Saul LK, Schölkopf B (eds) Advances in neural information processing systems. MIT Press, Vancouver, Canada, pp 585–592
Sørensen TJ (1948) A method of establishing groups of equal amplitude in plant sociology based on similarity of species content. Kongelige Danske Videnskabernes Selskab 5(1–34):4–7
Sowa JF (1979) Semantics of conceptual graphs. In: Proceedings of the 17th annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, pp 39–44
Spielman DA (2010) Algorithms, graph theory, and linear equations in laplacian matrices. In: Proceedings of the international congress of mathematicians 2010 (ICM 2010) (In 4 Volumes) vol I: plenary lectures and ceremonies vols. II–IV: invited lectures. World Scientific, pp 2698–2722
Sussenguth EH (1964) Structure matching in information processing. Harvard University, CambridgeMATH
Tsai WH, Fu KS (1979) Error-correcting isomorphisms of attributed relational graphs for pattern analysis. IEEE Trans Syst Man Cybern 9(12):757–768MATH
Tsuda K, Kin T, Asai K (2002) Marginalized kernels for biological sequences. Bioinformatics 18(Suppl 1):S268–S275
Tversky A (1977) Features of similarity. Psychol Rev 84:327–352
Umeyama S (1988) An eigendecomposition approach to weighted graph matching problems. IEEE Trans Pattern Anal Machine Intell 10(5):695–703MATH
Valls-Vargas J, Ontanón S, Zhu J (2014) Toward automatic character identification in unannotated narrative text. In: Seventh intelligent narrative technologies workshop
van der Laag PRJ, Nienhuys-Cheng SH (1998) Completeness and properness of refinement operators in inductive logic programming. J Log Program 34(3):201–225MathSciNetMATH
Vert JP, Tsuda K, Schölkopf B (2004) A primer on kernel methods. Kernel Methods Comput Biol 47:35–70
Wallis WD, Shoubridge P, Kraetz M, Ray D (2001) Graph distances using graph union. Pattern Recogn Lett 22(6):701–704MATH
Wang Y, Ishii N (1997) A method of similarity metrics for structured representations. Expert Syst Appl 12(1):89–100
Weisfeiler B, Lehman AA (1968) A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia 2(9):12–16
Welch TA (1984) A technique for high-performance data compression. Computer 6(17):8–19
Wess S (1995) Fallbasiertes Problemlösen in wissensbasierten systemen zur entscheidungsunterst ützung und diagnostik
Wettschereck D, Aha DW, Mohri T (1997) A review and empirical evaluation of feature weighting methods for a class of lazy learning algorithms. Artif Intell Rev 11(1–5):273–314
Wolpert DH (1996) The lack of a priori distinctions between learning algorithms. Neural Comput 8(7):1341–1390
Wu Z, Palmer M (1994) Verbs semantics and lexical selection. In: Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, pp 133–138
Xu L, King I (2001) A pca approach for fast retrieval of structural patterns in attributed graphs. IEEE Trans Syst Man Cybern Part B (Cybern) 31(5):812–817
Xu K, Hu W, Leskovec J, Jegelka S (2018) How powerful are graph neural networks? arXiv:181000826
Yang L, Jin R (2006) Distance metric learning: a comprehensive survey. Mich State Univ 2(2):4
Zhang K (1989) The editing distance between trees: algorithms and applications. PhD thesis from the New York University
Zhang Z, Wang M, Xiang Y, Huang Y, Nehorai A (2018) Retgk: graph kernels based on return probabilities of random walks. In: Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, Neural Information Processing Systems Conference (eds) Advances in neural information processing systems, Vancouver, Canada, pp 3964–3974
Metadata
Title
An overview of distance and similarity functions for structured data
Author
Santiago Ontañón
Publication date
27-02-2020
Publisher
Springer Netherlands
Published in
Artificial Intelligence Review / Issue 7/2020
Print ISSN: 0269-2821
Electronic ISSN: 1573-7462
DOI
https://doi.org/10.1007/s10462-020-09821-w

Other articles of this Issue 7/2020

Artificial Intelligence Review 7/2020 Go to the issue

OriginalPaper

Feed-forward versus recurrent architecture and local versus cellular automata distributed representation in reservoir computing for sequence memory learning

OriginalPaper

Applicability of machine learning in spam and phishing email filtering: review and approaches

OriginalPaper

A general framework for multi-granulation rough decision-making method under q-rung dual hesitant fuzzy environment

OriginalPaper

A three-way decision method in a hybrid decision information system and its application in medical diagnosis

OriginalPaper

A comprehensive survey on model compression and acceleration

OriginalPaper

The effect of downsampling–upsampling strategy on foreground detection algorithms

Premium Partner

    Image Credits