MADMatch: Many-to-many Approximate Diagram Matching for Design Comparison

MADMatch: Many-to-many Approximate Diagram Matching for Design Comparison. Kpodjedo, S., Ricca, F., Galinier, P., Antoniol, G., & Gu�h�neuc, Y. Transactions on Software Engineering (TSE), 39(8):1090–1111, IEEE CS Press, February, 2013. 23 pages.

Paper abstract bibtex

Matching algorithms play a fundamental role in many important but difficult software engineering activities, especially design evolution analysis and model comparison. We present MADMatch, a fast and scalable Many-to-many Approximate Diagram Matching approach based on an Error-Tolerant Graph matching (ETGM) formulation. Diagrams are represented as graphs, costs are assigned to possible differences between two given graphs, and the goal is to retrieve the cheapest matching. We address the resulting optimisation problem with a tabu search enhanced by the novel use of lexical and structural information. Through several case studies with different types of diagrams and tasks, we show that our generic approach obtains better results than dedicated state-of-the-art algorithms, such as AURA, PLTSDiff or UMLDiff, on the exact same datasets used to introduce (and evaluate) these algorithms.

@ARTICLE{Kpodjedo13-TSE-MADMatch,
   AUTHOR       = {S�gla Kpodjedo and Filippo Ricca and Philippe Galinier and 
      Giuliano Antoniol and Yann-Ga�l Gu�h�neuc},
   JOURNAL      = {Transactions on Software Engineering (TSE)},
   TITLE        = {MADMatch: Many-to-many Approximate Diagram Matching for 
      Design Comparison},
   YEAR         = {2013},
   MONTH        = {February},
   NOTE         = {23 pages.},
   NUMBER       = {8},
   PAGES        = {1090--1111},
   VOLUME       = {39},
   EDITOR       = {Martin Robillard},
   KEYWORDS     = {Topic: <b>Evolution patterns</b>, Venue: <b>TSE</b>},
   PUBLISHER    = {IEEE CS Press},
   URL          = {http://www.ptidej.net/publications/documents/TSE13b.doc.pdf},
   ABSTRACT     = {Matching algorithms play a fundamental role in many 
      important but difficult software engineering activities, especially 
      design evolution analysis and model comparison. We present MADMatch, 
      a fast and scalable Many-to-many Approximate Diagram Matching 
      approach based on an Error-Tolerant Graph matching (ETGM) 
      formulation. Diagrams are represented as graphs, costs are assigned 
      to possible differences between two given graphs, and the goal is to 
      retrieve the cheapest matching. We address the resulting optimisation 
      problem with a tabu search enhanced by the novel use of lexical and 
      structural information. Through several case studies with different 
      types of diagrams and tasks, we show that our generic approach 
      obtains better results than dedicated state-of-the-art algorithms, 
      such as AURA, PLTSDiff or UMLDiff, on the exact same datasets used to 
      introduce (and evaluate) these algorithms.}
}

Downloads: 0

{"_id":"irpEmHZPq3X7tk7kx","bibbaseid":"kpodjedo-ricca-galinier-antoniol-guhneuc-madmatchmanytomanyapproximatediagrammatchingfordesigncomparison-2013","downloads":0,"creationDate":"2017-07-26T09:21:27.809Z","title":"MADMatch: Many-to-many Approximate Diagram Matching for Design Comparison","author_short":["Kpodjedo, S.","Ricca, F.","Galinier, P.","Antoniol, G.","Gu�h�neuc, Y."],"year":2013,"bibtype":"article","biburl":"http://www.yann-gael.gueheneuc.net/Work/Publications/Biblio/complete-bibliography.bib","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["S�gla"],"propositions":[],"lastnames":["Kpodjedo"],"suffixes":[]},{"firstnames":["Filippo"],"propositions":[],"lastnames":["Ricca"],"suffixes":[]},{"firstnames":["Philippe"],"propositions":[],"lastnames":["Galinier"],"suffixes":[]},{"firstnames":["Giuliano"],"propositions":[],"lastnames":["Antoniol"],"suffixes":[]},{"firstnames":["Yann-Ga�l"],"propositions":[],"lastnames":["Gu�h�neuc"],"suffixes":[]}],"journal":"Transactions on Software Engineering (TSE)","title":"MADMatch: Many-to-many Approximate Diagram Matching for Design Comparison","year":"2013","month":"February","note":"23 pages.","number":"8","pages":"1090–1111","volume":"39","editor":[{"firstnames":["Martin"],"propositions":[],"lastnames":["Robillard"],"suffixes":[]}],"keywords":"Topic: Evolution patterns, Venue: TSE","publisher":"IEEE CS Press","url":"http://www.ptidej.net/publications/documents/TSE13b.doc.pdf","abstract":"Matching algorithms play a fundamental role in many important but difficult software engineering activities, especially design evolution analysis and model comparison. We present MADMatch, a fast and scalable Many-to-many Approximate Diagram Matching approach based on an Error-Tolerant Graph matching (ETGM) formulation. Diagrams are represented as graphs, costs are assigned to possible differences between two given graphs, and the goal is to retrieve the cheapest matching. We address the resulting optimisation problem with a tabu search enhanced by the novel use of lexical and structural information. Through several case studies with different types of diagrams and tasks, we show that our generic approach obtains better results than dedicated state-of-the-art algorithms, such as AURA, PLTSDiff or UMLDiff, on the exact same datasets used to introduce (and evaluate) these algorithms.","bibtex":"@ARTICLE{Kpodjedo13-TSE-MADMatch,\r\n AUTHOR = {S�gla Kpodjedo and Filippo Ricca and Philippe Galinier and \r\n Giuliano Antoniol and Yann-Ga�l Gu�h�neuc},\r\n JOURNAL = {Transactions on Software Engineering (TSE)},\r\n TITLE = {MADMatch: Many-to-many Approximate Diagram Matching for \r\n Design Comparison},\r\n YEAR = {2013},\r\n MONTH = {February},\r\n NOTE = {23 pages.},\r\n NUMBER = {8},\r\n PAGES = {1090--1111},\r\n VOLUME = {39},\r\n EDITOR = {Martin Robillard},\r\n KEYWORDS = {Topic: Evolution patterns, Venue: TSE},\r\n PUBLISHER = {IEEE CS Press},\r\n URL = {http://www.ptidej.net/publications/documents/TSE13b.doc.pdf},\r\n ABSTRACT = {Matching algorithms play a fundamental role in many \r\n important but difficult software engineering activities, especially \r\n design evolution analysis and model comparison. We present MADMatch, \r\n a fast and scalable Many-to-many Approximate Diagram Matching \r\n approach based on an Error-Tolerant Graph matching (ETGM) \r\n formulation. Diagrams are represented as graphs, costs are assigned \r\n to possible differences between two given graphs, and the goal is to \r\n retrieve the cheapest matching. We address the resulting optimisation \r\n problem with a tabu search enhanced by the novel use of lexical and \r\n structural information. Through several case studies with different \r\n types of diagrams and tasks, we show that our generic approach \r\n obtains better results than dedicated state-of-the-art algorithms, \r\n such as AURA, PLTSDiff or UMLDiff, on the exact same datasets used to \r\n introduce (and evaluate) these algorithms.}\r\n}\r\n\r\n","author_short":["Kpodjedo, S.","Ricca, F.","Galinier, P.","Antoniol, G.","Gu�h�neuc, Y."],"editor_short":["Robillard, M."],"key":"Kpodjedo13-TSE-MADMatch","id":"Kpodjedo13-TSE-MADMatch","bibbaseid":"kpodjedo-ricca-galinier-antoniol-guhneuc-madmatchmanytomanyapproximatediagrammatchingfordesigncomparison-2013","role":"author","urls":{"Paper":"http://www.ptidej.net/publications/documents/TSE13b.doc.pdf"},"keyword":["Topic: Evolution patterns","Venue: TSE"],"metadata":{"authorlinks":{"gu�h�neuc, y":"https://bibbase.org/show?bib=http%3A%2F%2Fwww.yann-gael.gueheneuc.net%2FWork%2FPublications%2FBiblio%2Fcomplete-bibliography.bib&msg=embed","guéhéneuc, y":"http://www.yann-gael.gueheneuc.net/"}}},"search_terms":["madmatch","many","many","approximate","diagram","matching","design","comparison","kpodjedo","ricca","galinier","antoniol","gu�h�neuc"],"keywords":["topic: evolution patterns","venue: tse"],"authorIDs":["2tFXMaTSHJKEB5ebi","2wY5eBcsYmbPNfmMS","36dm7jaw5EK5Wrr4D","3NxaNKic3nkXi568L","3S5Dkpx7DNefzJrnf","3afmfmoPr4SHa8B5F","3wmHB7JoQbQz2ujun","4YBWWbao6RKgiyGJE","4jZj9tB4SJ8zEEgHk","550075158eef46c5720009bb","5CvA2hsaib2bPMaef","5TFJbxqRDGFj2P8Rg","5a5fb236a39f2c3645000032","5a8f17e006df23bc34000020","5cx79LBmaWcihgM4J","5de9a6425b51bcde01000042","5dee1197584fb4df010000fc","5def500866cfe0df010000e7","5df228a41e4fe9df0100012c","5df617f72b34d0de0100008b","5dfa14782e791dde010000ea","5dfe3d5e68d95dde01000080","5dff1cba7769f4de01000077","5e0237bf4a106ede010000cb","5e02525b6ffa15df0100009f","5e05f65b6a743cde010000b0","5e0662c07da1d1de0100021a","5e093e8b934cacdf0100008b","5e0a61673eccf6e001000016","5e0ac75d27625ede010000a2","5e0b75b7e73cd6de010000f9","5e0d4ca6ae5827df0100007f","5e0ddf08552b25df01000137","5e0e5c41ac7d11df010000a3","5e1268e7a4cabfdf0100002c","5e12c45a70e2c4f201000043","5e1482a708c265de0100008f","5e157809f1f31adf01000006","5e15ab4ee8bfcff20100018e","5e162ca1df1bb4de01000123","5e185cff809b84f201000091","5e1a6c39b16ec5df0100000f","5e2017fc453fb7df010000fb","5e21b27e96aea7de01000084","5e22c57e49e2b4df0100000f","5e23c2aeb93b51de01000030","5e245835079bb2df0100007d","5e24fa3e2e79a1f201000027","5e26252f408641df01000161","5e26bfbd8535cedf0100005c","5e27d20468d625de01000014","5e280fd1f860fcde0100006a","5e2a827f881468de01000080","5e2cb33ecca05fde010000b7","5e2eb321b84405df01000128","5e2ef635e374eede0100001a","5e2fd6a74e91a9df01000010","5e3266bb5633c9de01000068","5e32ab0ee17accde0100012a","5e32bdec466076df010000d9","5e32d603150c84df01000068","5e34fb145978bef2010000a6","5e36bc8e7b975dde0100009a","5e389940030bcadf010001b4","5e39dd9a3687dddf010000a4","5e3ad173f2a00cdf01000206","5e3dcd50d51253de0100003d","5e3e8713666d79df010000a6","5e3ed80986a596de010000b9","5e3f4a0e77baf5df010000b2","5e3fefe1add5fbde01000087","5e409c79d668c6de010000c7","5e41795ed9f47bee01000194","5e41cd5be7c67ade010000eb","5e42ef1ca6f4a6f2010001eb","5e46dcb342fb31df01000113","5e46f12c461d04f201000078","5e478c9e27a0c8de010000ef","5e47fb06385298df010000b2","5e4add1941072bdf01000011","5e4c1c792dc400de0100011a","5e4c6262271596df010001b9","5e4f0360338acfde01000156","5e4f11b0e5389bde0100007e","5e530b976d68b8df010000a5","5e54ad6d929495df0100007c","5e57161b429006de0100005a","5e578352cef9b7de01000036","5e57839fcef9b7de0100003c","5e580f5a6a456fde0100004f","5e5afa78038583de010000f7","5e5b477174a3e7df010000b7","5e5ccb83aab7afde01000067","5e5d370173eb2edf01000038","5e5fca336b32b0f20100011b","5e6070ce9119f0de01000081","5e60e7f0839e59df010000e8","5e61032a31c7d3de0100019b","5e6377cfae1c4dde0100011e","5e646d9ee1ac00de010000a9","5e657007de41b9df0100017a","5e676f0910be53de0100001a","5gPbX6aQJFjpv2Na9","6eE2yRdMDQr2WGXuA","6iHE5tuM7yTfLd2pA","7BPWyvMr5e6bzbk7T","7RFwhpGkpZRsLwnmB","7amRA4ALcR2mksheF","7mkQL8eiftj5bGMzB","8jPjKehCMsj7ncvxN","8peLXfWtCSic5n7oz","95eRgTcabnJwF46f3","9Ba9JxkjQBCeGBZKg","9DjgvzQrx27uxbyJj","9HD56d3k5yrB9H9oq","9RtPuXNyeS3k8LM9J","9diLYpd8cMmjBh54T","9nx6Yv3XREwJDyRms","AfJhKcg96muyPdu7S","BGvchZsjW7Wejj9Cz","BYwdHpGr6xT5vmE5C","Bah6LM7GXdXTy8GGA","BmH2ytt7sXwPHcrse","C6mhrH6c2xwNneWx5","CqJYxtqe6qBbtd5yz","D4kEZ2JcWCoMvRPy7","DFWW7D6Y7X57n4cbM","DSorPqHDfrFiNM5Ew","DWXisKXaQArvre3QL","DwBm6isMpKSHHkhAd","E88raoktD8ANF92Yu","EAjLox7ycbofcCXce","F8rzFhY9yWA7pBX4j","G3iynDKjz9BHJbrdg","GJw6mQETXADSCZuuk","GWK5669HLqPyYMQ5J","GibAXjj4xXdFT8qWh","HzFZpgGcfabjAp9x6","KJ4eYziy6hanF9kr9","Kcyu7uncEFiYzYP2D","N4zzhqcywSzDDYsdh","NCDg3xE2mPcNAu7LX","NvgbTAz3hZ9SevZvd","QbcDS3wK43sRASvgu","S3b7Bb9wwfpByQgbo","SXJaeFCgBDJ5HAHtj","T5nL8TGrggoLAF8Dj","TG7ZJxaBNKhCmi8ra","W9vT8YcCNFEcp9mWQ","WZ5CpBEFNsb2ivfah","XxviSwRxhwgNwsraH","Z2Zs662GpXqKBEAMc","ZKYFgjHGm7PE4Y2kv","a5qpGirN3B5BLKdMh","a99yMwTJRm8ezEoTA","ahGA65oGDChNYp7Mb","bA7pGCMS9AB2RBo2p","bTQb3TcrbBShtqFPS","cYnqisf4wzBsM7MF5","cjHpaYiWD5eX7btH4","ckrbesqi3pWqfF2nP","cmSeARFJMpYepXtZw","dH8EsWHZtCFuQk5bq","dS5kvBMnk3LMQe56w","eXsFRMzE7WfbHbBL4","fmmsBu4m6ayKtuopf","fw8BgTXKHC8XNyATL","hdXr3PD8cHNWyAdCe","hgZxckC87u2A57teF","is8MSfdaNdr9La2c5","juvCjffHJaPQf44im","keQBT2Apb9yaev8AH","myHdF8zARwW5uGmFs","nJLfaznnYgFqWQQrv","oK9xcwvdx6HRcWu6g","onghitNWSvN2FpCaN","osgPwDW2y5KDXRa2i","pAWFMDHu5dNixqPAq","pLvmgrCjMeDYJiJxB","q4azvWakEjp2TQM7S","qBee6Md9YwRKwkeW3","qQky2Csek4mroLn2P","tJz4YBCqAzZAzek5d","tLtjttw8dEqF6YQ4s","uQ6jCrPijzAmZyfXz","vGEaFNt7mm92Z7GXc","vRkMmE65HSFpCk6FW","vScAoCmy5nQdJh87Q","vsEsf8FR3Fxb6z7fJ","wL9qt9zZNZQJKfuwt","x5ejzvDeXCc89Dukv","xEQyC5shxpYySSJJm","xhwDdvQ7MYxa6keXm","xkviMnkrGBneANvMr","y64rFMcyp7tDsBrJQ","yBT79RWXy7W3eSdxp","yBYJWSShoKkMG8aPE","yQPghCwQv22kf6dFq","yd5sCxaEiu5vWizTq"],"dataSources":["Sed98LbBeGaXxenrM","8vn5MSGYWB4fAx9Z4","L4MmnFQ9js4SGijb8"]}