Efficient Identification of Linchpin Vertices in Dependence Clusters

Article

Binkley, David, Gold, Nicolas, Harman, Mark, Islam, S., Krinke, Jens and Li, Zheng 2013. Efficient Identification of Linchpin Vertices in Dependence Clusters. ACM Transactions on Programming Languages and Systems. 35 (2), pp. 1-35.

Publication dates
Authors	Binkley, David, Gold, Nicolas, Harman, Mark, Islam, S., Krinke, Jens and Li, Zheng
Abstract	Several authors have found evidence of large dependence clusters in the source code of a diverse range of systems, domains, and programming languages. This raises the question of how we might efficiently locate the fragments of code that give rise to large dependence clusters. We introduce an algorithm for the identification of linchpin vertices, which hold together large dependence clusters, and prove correctness properties for the algorithm’s primary innovations. We also report the results of an empirical study concerning the reduction in analysis time that our algorithm yields over its predecessor using a collection of 38 programs containing almost half a million lines of code. Our empirical findings indicate improvements of almost two orders of magnitude, making it possible to process larger programs for which it would have previously been impractical.
Journal	ACM Transactions on Programming Languages and Systems
Journal citation	35 (2), pp. 1-35
ISSN	01640925
Year	2013
Publisher	Association for Computing Machinery (ACM)
Accepted author manuscript	toplas-13-linchpin.pdf License CC BY-NC
Web address (URL)	http://dx.doi.org/10.1145/2491522.2491524
Print	Jul 2013
Publication process dates
Deposited	05 Jan 2016
Copyright information	"© ACM, 2013. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Programming Languages and Systems, {35, 2, 2013} http://doi.acm.org/10.1145/2491522.2491524

Permalink -

https://repository.uel.ac.uk/item/85wqx

Download files

Accepted author manuscript

	toplas-13-linchpin.pdf
License: CC BY-NC

149
total views
295
total downloads
2
views this month
3
downloads this month

Export as

Related outputs

Semantic-Based Process Mining Technique for Annotation and Modelling of Domain Processes

Okoye, K., Islam, S., Naeem, U. and Sharif, S. 2020. Semantic-Based Process Mining Technique for Annotation and Modelling of Domain Processes. International Journal of Innovative Computing, Information and Control. 16 (3), pp. 899-921. https://doi.org/10.24507/ijicic.16.03.899

Improving Student Engagement and Performance in Computing Final Year Projects

Naeem, U., Islam, S. and Siddiqui, A. 2019. Improving Student Engagement and Performance in Computing Final Year Projects. IEEE TALE 2019. Yogyakarta - Indonesia 10 - 13 Oct 2019 IEEE. https://doi.org/10.1109/TALE48000.2019.9225860

Functional Connectivity Evaluation for Infant EEG Signals based on Artificial Neural Network

Sharif, M., Naeem, U., Islam, S. and Karami, A. 2018. Functional Connectivity Evaluation for Infant EEG Signals based on Artificial Neural Network. Arai, Kohei, Kapoor, Supriya and Bhatia, Rahul (ed.) Intelligent Systems Conference (IntelliSys) 2018. London, UK 06 - 07 Sep 2018 Springer, Cham. https://doi.org/10.1007/978-3-030-01057-7_34

The Application of a Semantic-Based Process Mining Framework on a Learning Process Domain

Okoye, Kingsley, Islam, S., Naeem, U., Sharif, M., Azam, Muhammad Awais and Karami, A. 2018. The Application of a Semantic-Based Process Mining Framework on a Learning Process Domain. Arai, Kohei, Kapoor, Supriya and Bhatia, Rahul (ed.) Intelligent Systems Conference (IntelliSys) 2018. London, UK 06 - 07 Sep 2018 Springer, Cham. https://doi.org/10.1007/978-3-030-01054-6_96

Authentication of Smartphone Users Based on Activity Recognition and Mobile Sensing

Ehatisham-ul-Haq, Muhammad, Azam, Muhammad Awais, Loo, Jonathan, Shuang, Kai, Islam, S., Naeem, U. and Amin, Yasar 2017. Authentication of Smartphone Users Based on Activity Recognition and Mobile Sensing. Sensors. 17 (9), p. 2043. https://doi.org/10.3390/s17092043

Taskification – Gamification of Tasks

Naeem, U., Islam, S., Sharif, M., Sudakov, Sergey and Azam, Awais 2017. Taskification – Gamification of Tasks. in: Proceedings of the 2017 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2017 ACM International Symposium on Wearable Computers Association for Computing Machinery (ACM). pp. 631-634

SignalSense - Towards Quality Service

Islam, S., Sharif, M., Naeem, U. and Geehan, James 2017. SignalSense - Towards Quality Service. in: Proceedings of the 2017 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2017 ACM International Symposium on Wearable Computers Association for Computing Machinery (ACM). pp. 627-630

CrimeSafe - Helping you stay safe

Islam, S., Naeem, U., Sharif, M. and Dovnarovic, Arnold 2017. CrimeSafe - Helping you stay safe. in: Proceedings of the 2017 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2017 ACM International Symposium on Wearable Computers Association for Computing Machinery (ACM). pp. 642-645

Using semantic-based approach to manage perspectives of process mining: Application on improving learning process domain data

Kingsley, Okoye, Tawil, Abdel-Rahman H., Naeem, U., Islam, S. and Lamine, Elyes 2017. Using semantic-based approach to manage perspectives of process mining: Application on improving learning process domain data. in: 2016 IEEE International Conference on Big Data (Big Data) IEEE. pp. 3529-3538

Dependence Cluster Visualization

Islam, S., Krinke, Jens and Binkley, David 2010. Dependence Cluster Visualization. in: Proceedings of the 5th international symposium on Software visualization New York, NY, USA Association for Computing Machinery (ACM). pp. 93-102

Less is more: Temporal fault predictive performance over multiple Hadoop releases

Harman, Mark, Islam, S., Jia, Yue, Minku, Leandro L., Sarro, Federica and Srivisut, Komsan 2014. Less is more: Temporal fault predictive performance over multiple Hadoop releases. in: Goues, Claire Le and Yoo, Shin (ed.) Search-Based Software Engineering Springer International Publishing.

ORBS: Language-Independent Program Slicing

Binkley, David, Gold, Nicolas, Harman, Mark, Islam, S., Krinke, Jens and Yoo, Shin 2014. ORBS: Language-Independent Program Slicing. in: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering New York, NY, USA Association for Computing Machinery (ACM). pp. 109-120

Jolinar: Analysing the Energy Footprint of Software Applications (demo)

Noureddine, A., Islam, S. and Bashroush, R. 2016. Jolinar: Analysing the Energy Footprint of Software Applications (demo). in: Proceedings of the 25th International Symposium on Software Testing and Analysis New York, NY, USA Association for Computing Machinery (ACM). pp. 445-448

Semantic-Based Model Analysis Towards Enhancing Information Values of Process Mining: Case Study of Learning Process Domain

Okoye, Kingsley, Tawila, Abdel-Rahman H., Naeem, U., Islam, S. and Lamine, Elyes 2017. Semantic-Based Model Analysis Towards Enhancing Information Values of Process Mining: Case Study of Learning Process Domain. in: Abraham, Ajith, Cherukuri, Aswani Kumar, Madureira, Ana Maria and Muda, Azah Kamilah (ed.) Proceedings of the Eighth International Conference on Soft Computing and Pattern Recognition (SoCPaR 2016) Springer, Cham.

Assessing the impact of global variables on program dependence and dependence clusters

Binkley, David, Harman, Mark, Hassoun, Youssef, Islam, S. and Li, Zheng 2009. Assessing the impact of global variables on program dependence and dependence clusters. Journal of Systems and Software. 83 (1), pp. 96-107. https://doi.org/10.1016/j.jss.2009.03.038

Requirements for the formal representation of pathophysiology mechanisms by clinicians

de Bono, B., Helvensteijn, M., Kokash, N., Martorelli, I., Sarwar, D., Islam, S., Grenon, P. and Hunter, P. 2016. Requirements for the formal representation of pathophysiology mechanisms by clinicians. Interface Focus. 6 (2), p. 20150075. https://doi.org/10.1098/rsfs.2015.0099

An empirical study on dependence clusters for effort-aware fault-proneness prediction

Yang, Yibiao, Harman, Mark, Krinke, Jens, Islam, S., Binkley, David, Zhou, Yuming and Xu, Baowen 2016. An empirical study on dependence clusters for effort-aware fault-proneness prediction. in: Lo, David, Apel, Sven and Khurshid, Sarfraz (ed.) ASE’16 Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering IEEE/ACM. pp. 296-307

Towards Cloud Security Monitoring: A Case Study

Ismail, Umar Mukhtar, Islam, S. and Islam, S. 2016. Towards Cloud Security Monitoring: A Case Study. in: 2016 Cybersecurity and Cyberforensics Conference (CCC) IEEE.

gUML: Reasoning about Energy at Design Time by Extending UML Deployment Diagrams with Data Centre Contextual Information

Jebraeil, Nigar, Noureddine, A., Doyle, J., Islam, S. and Bashroush, R. 2017. gUML: Reasoning about Energy at Design Time by Extending UML Deployment Diagrams with Data Centre Contextual Information. in: 2017 IEEE World Congress on Services (SERVICES) IEEE. pp. In Press