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, Feburary, 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{\'e}gla Kpodjedo and Filippo Ricca and Philippe Galinier and Giuliano Antoniol and Yann-Ga{\"e}l Gu{\'e}h{\'e}neuc},
title = {{MADMatch}: Many-to-many Approximate Diagram Matching for Design Comparison},
journal = {Transactions on Software Engineering ({TSE})},
year = {2013},
month = {Feburary},
volume = {39},
number = {8},
pages = {1090--1111},
note = {23 pages.},
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.},
editor = {Martin Robillard},
grant = {NSERC DG and CRC on Software Patterns},
keywords = {Evolution patterns ; TSE},
kind = {RIAS},
language = {english},
publisher = {IEEE CS Press},
url = {http://www.ptidej.net/publications/documents/TSE13b.doc.pdf},
page = {1--23}
}
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/BibBase/guehene (automatically cleaned).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":[]}],"title":"MADMatch: Many-to-many Approximate Diagram Matching for Design Comparison","journal":"Transactions on Software Engineering (TSE)","year":"2013","month":"Feburary","volume":"39","number":"8","pages":"1090–1111","note":"23 pages.","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.","editor":[{"firstnames":["Martin"],"propositions":[],"lastnames":["Robillard"],"suffixes":[]}],"grant":"NSERC DG and CRC on Software Patterns","keywords":"Evolution patterns ; TSE","kind":"RIAS","language":"english","publisher":"IEEE CS Press","url":"http://www.ptidej.net/publications/documents/TSE13b.doc.pdf","page":"1–23","bibtex":"@ARTICLE{Kpodjedo13-TSE-MADMatch,\n author = {S{\\'e}gla Kpodjedo and Filippo Ricca and Philippe Galinier and Giuliano Antoniol and Yann-Ga{\\\"e}l Gu{\\'e}h{\\'e}neuc},\n title = {{MADMatch}: Many-to-many Approximate Diagram Matching for Design Comparison},\n journal = {Transactions on Software Engineering ({TSE})},\n year = {2013},\n month = {Feburary},\n volume = {39},\n number = {8},\n pages = {1090--1111},\n note = {23 pages.},\n 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.},\n editor = {Martin Robillard},\n grant = {NSERC DG and CRC on Software Patterns},\n keywords = {Evolution patterns ; TSE},\n kind = {RIAS},\n language = {english},\n publisher = {IEEE CS Press},\n url = {http://www.ptidej.net/publications/documents/TSE13b.doc.pdf},\n page = {1--23}\n}\n\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":["Evolution patterns ; 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":"https://bibbase.org/show?bib=http://www.yann-gael.gueheneuc.net/Work/BibBase/guehene%20(automatically%20cleaned).bib"}},"downloads":0,"html":""},"search_terms":["madmatch","many","many","approximate","diagram","matching","design","comparison","kpodjedo","ricca","galinier","antoniol","guéhéneuc"],"keywords":["evolution patterns ; 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"]}