{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T13:14:05Z","timestamp":1773407645194,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-10-2-0253FA9950-09-1-0389"],"award-info":[{"award-number":["FA8750-10-2-0253FA9950-09-1-0389"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["FA8750-10-2-0253FA9950-09-1-0389"],"award-info":[{"award-number":["FA8750-10-2-0253FA9950-09-1-0389"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>An important aspect of system optimization research is the discovery of program traits or behaviors. In this paper, we present an automated method of program characterization which is able to examine and cluster program graphs, i.e., dynamic data graphs or control flow graphs. Our novel approximate graph clustering technology allows users to find groups of program fragments which contain similar code idioms or patterns in data reuse, control flow, and context. Patterns of this nature have several potential applications including development of new static or dynamic optimizations to be implemented in software or in hardware.<\/jats:p>\n          <jats:p>For the SPEC CPU 2006 suite of benchmarks, our results show that approximate graph clustering is effective at grouping behaviorally similar functions. Graph based clustering also produces clusters that are more homogeneous than previously proposed non-graph based clustering methods. Further qualitative analysis of the clustered functions shows that our approach is also able to identify some frequent unexploited program behaviors. These results suggest that our approximate graph clustering methods could be very useful for program characterization.<\/jats:p>","DOI":"10.1145\/2086696.2086700","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T16:47:14Z","timestamp":1327423634000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Approximate graph clustering for program characterization"],"prefix":"10.1145","volume":"8","author":[{"given":"John","family":"Demme","sequence":"first","affiliation":[{"name":"Columbia University, New York"}]},{"given":"Simha","family":"Sethumadhavan","sequence":"additional","affiliation":[{"name":"Columbia University, New York"}]}],"member":"320","published-online":{"date-parts":[[2012,1,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2006.37"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the SMART'09 Workshop.","author":"Alvincz L.","unstructured":"Alvincz , L. and Glesner , S . 2009. Breaking the curse of static analyses: Making compilers intelligent via machine learning . In Proceedings of the SMART'09 Workshop. Alvincz, L. and Glesner, S. 2009. Breaking the curse of static analyses: Making compilers intelligent via machine learning. In Proceedings of the SMART'09 Workshop."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391956.1391959"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Arvind and Iannucci R. A. 1987. Two fundamental issues in multiprocessing. In Parallel Computing in Science and Engineering 61--88.   Arvind and Iannucci R. A. 1987. Two fundamental issues in multiprocessing. In Parallel Computing in Science and Engineering 61--88.","DOI":"10.1007\/3-540-18923-8_15"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2009.16"},{"key":"e_1_2_1_6_1","volume-title":"ICSM'98: Proceedings of the International Conference on Software Maintenance. IEEE Computer Society","author":"Baxter I. D.","unstructured":"Baxter , I. D. , Yahin , A. , Moura , L. , Sant'Anna , M. , and Bier , L . 1998. Clone detection using abstract syntax trees . In ICSM'98: Proceedings of the International Conference on Software Maintenance. IEEE Computer Society , Los Alamitos, CA, 368. Baxter, I. D., Yahin, A., Moura, L., Sant'Anna, M., and Bier, L. 1998. Clone detection using abstract syntax trees. In ICSM'98: Proceedings of the International Conference on Software Maintenance. IEEE Computer Society, Los Alamitos, CA, 368."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTR.2008.4663796"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176760.1176765"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176760.1176779"},{"key":"e_1_2_1_10_1","volume-title":"MICRO 36: Proceedings of the 36th annual IEEE\/ACM International Symposium on Microarchitecture. IEEE Computer Society","author":"Clark N.","unstructured":"Clark , N. , Zhong , H. , and Mahlke , S . 2003. Processor acceleration through automated instruction set customization . In MICRO 36: Proceedings of the 36th annual IEEE\/ACM International Symposium on Microarchitecture. IEEE Computer Society , Los Alamitos, CA, 129. Clark, N., Zhong, H., and Mahlke, S. 2003. Processor acceleration through automated instruction set customization. In MICRO 36: Proceedings of the 36th annual IEEE\/ACM International Symposium on Microarchitecture. IEEE Computer Society, Los Alamitos, CA, 129."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000064.2000107"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781159"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242531.1242553"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Eeckhout L. 2010. Computer architecture performance evaluation methods. In Synthesis Lectures on Computer Architecture Morgan Claypool.   Eeckhout L. 2010. Computer architecture performance evaluation methods. In Synthesis Lectures on Computer Architecture Morgan Claypool.","DOI":"10.1007\/978-3-031-01727-8"},{"key":"e_1_2_1_15_1","first-page":"1","article-title":"Quantifying the impact of input data sets on program behavior and its applications","volume":"5","author":"Eeckhout L.","year":"2003","unstructured":"Eeckhout , L. , Vandierendonck , H. , and Bosschere , K. D. 2003 . Quantifying the impact of input data sets on program behavior and its applications . J. Instruction-Level Parall. 5 , 1 -- 33 . Eeckhout, L., Vandierendonck, H., and Bosschere, K. D. 2003. Quantifying the impact of input data sets on program behavior and its applications. J. Instruction-Level Parall. 5, 1--33.","journal-title":"J. Instruction-Level Parall."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the GCC Developers' Summit.","author":"Fursin G.","year":"2008","unstructured":"Fursin , G. , Miranda , C. , Temam , O. , Namolaru , M. , Yom-Tov , E. , Zaks , A. , Mendelson , B. , Barnard , P. , Ashton , E. , Courtois , E. , Bodin , F. , Bonilla , E. , Thomson , J. , Leather , H. , Williams , C. , and O'Boyle , M. 2008 . Milepost gcc: Machine learning based research compiler . In Proceedings of the GCC Developers' Summit. Fursin, G., Miranda, C., Temam, O., Namolaru, M., Yom-Tov, E., Zaks, A., Mendelson, B., Barnard, P., Ashton, E., Courtois, E., Bodin, F., Bonilla, E., Thomson, J., Leather, H., Williams, C., and O'Boyle, M. 2008. Milepost gcc: Machine learning based research compiler. In Proceedings of the GCC Developers' Summit."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92990-1_5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1368088.1368132"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Conference on Communication and Computational Intelligence (INCOCCI). 211--217","author":"Gupta M.","unstructured":"Gupta , M. , Singh Rao , R. , and Tripathi , A . 2010. Design pattern detection using inexact graph matching . In Proceedings of the International Conference on Communication and Computational Intelligence (INCOCCI). 211--217 . Gupta, M., Singh Rao, R., and Tripathi, A. 2010. Design pattern detection using inexact graph matching. In Proceedings of the International Conference on Communication and Computational Intelligence (INCOCCI). 211--217."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.11"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1152154.1152174"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.85"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2002.1019480"},{"key":"e_1_2_1_24_1","volume-title":"CASCON'93: Proceedings of the Conference of the Centre for Advanced Studies on Collaborative Research. IBM Press, 194--205","author":"Kontogiannis K.","year":"1993","unstructured":"Kontogiannis , K. 1993 . Program representation and behavioural matching for localizing similar code fragments . In CASCON'93: Proceedings of the Conference of the Centre for Advanced Studies on Collaborative Research. IBM Press, 194--205 . Kontogiannis, K. 1993. Program representation and behavioural matching for localizing similar code fragments. In CASCON'93: Proceedings of the Conference of the Centre for Advanced Studies on Collaborative Research. IBM Press, 194--205."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/832308.837142"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2006.10.017"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Kuhn H. W. 1955. The hungarian method for the assignment problem. Naval Resear. Logistics Quart. 83--97.  Kuhn H. W. 1955. The hungarian method for the assignment problem. Naval Resear. Logistics Quart. 83--97.","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_28_1","unstructured":"Lattner C. 2002. LLVM: An Infrastructure for multi-stage optimization. M.S. thesis Computer Science Department University of Illinois at Urbana-Champaign. http:\/\/www.llvm.org.  Lattner C. 2002. LLVM: An Infrastructure for multi-stage optimization. M.S. thesis Computer Science Department University of Illinois at Urbana-Champaign. http:\/\/www.llvm.org."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2009.21"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2006.28"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065034"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 18th International Conference on Data Engineering. 117--128","author":"Melnik S.","unstructured":"Melnik , S. , Garcia-Molina , H. , and Rahm , E . 2002. Similarity flooding: A versatile graph matching algorithm and its application to schema matching . In Proceedings of the 18th International Conference on Data Engineering. 117--128 . Melnik, S., Garcia-Molina, H., and Rahm, E. 2002. Similarity flooding: A versatile graph matching algorithm and its application to schema matching. In Proceedings of the 18th International Conference on Data Engineering. 117--128."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379671"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1878921.1878951"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353445.1353451"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2009.5070528"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250662.1250713"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the International Workshop on Software Clones (IWSC).","author":"Smith R.","unstructured":"Smith , R. and Horwitz , S . 2009. Detecting and measuring similarity in code clones . In Proceedings of the International Workshop on Software Clones (IWSC). Smith, R. and Horwitz, S. 2009. Detecting and measuring similarity in code clones. In Proceedings of the International Workshop on Software Clones (IWSC)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2005.29"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/780822.781141"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Student. 1908. The probable error of a mean. Biometrika 1--25.  Student. 1908. The probable error of a mean. Biometrika 1--25.","DOI":"10.2307\/2331554"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066677.1067023"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1133989"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775141"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500845"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2086696.2086700","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2086696.2086700","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:42Z","timestamp":1750241202000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2086696.2086700"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2086696.2086700"],"URL":"https:\/\/doi.org\/10.1145\/2086696.2086700","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}