Benchmarking optimised algorithms for transitive closure

V. Pieterse, L.G.W.A. Cleophas

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We investigate the impact of using different algorithmic techniques and data representations in algorithms to calculate the transitive closure of a finite binary relation. These techniques are change monitor, loop fusion, loop tiling and short-circuiting. We explain them and how they are applied in the algorithms. We measured the impact of these techniques on the elapsed time to execute the algorithms, using C++ implementations with two different data representations, and using various data sets. The investigation also covers more basic transitive closure algorithms, and as a result forms a large-scale empirical comparison of such algorithms.

Original languageEnglish
Title of host publicationSAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages1-10
ISBN (Print)978-1-4503-5250-5
DOIs
Publication statusPublished - 26 Sep 2017
Event2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017) - University of the Free State, Bloemfontein, South Africa
Duration: 26 Sep 201728 Sep 2017
Conference number: 23
http://www.saicsit2017.org.za/

Conference

Conference2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017)
Abbreviated titleSAICSIT 2017
CountrySouth Africa
CityBloemfontein
Period26/09/1728/09/17
Internet address

Fingerprint

Benchmarking
Fusion reactions

Keywords

  • Algorithmic techniques
  • Benchmarking
  • Transitive closure

Cite this

Pieterse, V., & Cleophas, L. G. W. A. (2017). Benchmarking optimised algorithms for transitive closure. In SAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa (pp. 1-10). [27] New York: Association for Computing Machinery, Inc. https://doi.org/10.1145/3129416.3129425
Pieterse, V. ; Cleophas, L.G.W.A. / Benchmarking optimised algorithms for transitive closure. SAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa . New York : Association for Computing Machinery, Inc, 2017. pp. 1-10
@inproceedings{1760c4b2813d4677bea3a1679a6cd0e9,
title = "Benchmarking optimised algorithms for transitive closure",
abstract = "We investigate the impact of using different algorithmic techniques and data representations in algorithms to calculate the transitive closure of a finite binary relation. These techniques are change monitor, loop fusion, loop tiling and short-circuiting. We explain them and how they are applied in the algorithms. We measured the impact of these techniques on the elapsed time to execute the algorithms, using C++ implementations with two different data representations, and using various data sets. The investigation also covers more basic transitive closure algorithms, and as a result forms a large-scale empirical comparison of such algorithms.",
keywords = "Algorithmic techniques, Benchmarking, Transitive closure",
author = "V. Pieterse and L.G.W.A. Cleophas",
year = "2017",
month = "9",
day = "26",
doi = "10.1145/3129416.3129425",
language = "English",
isbn = "978-1-4503-5250-5",
pages = "1--10",
booktitle = "SAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa",
publisher = "Association for Computing Machinery, Inc",
address = "United States",

}

Pieterse, V & Cleophas, LGWA 2017, Benchmarking optimised algorithms for transitive closure. in SAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa ., 27, Association for Computing Machinery, Inc, New York, pp. 1-10, 2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017), Bloemfontein, South Africa, 26/09/17. https://doi.org/10.1145/3129416.3129425

Benchmarking optimised algorithms for transitive closure. / Pieterse, V.; Cleophas, L.G.W.A.

SAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa . New York : Association for Computing Machinery, Inc, 2017. p. 1-10 27.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Benchmarking optimised algorithms for transitive closure

AU - Pieterse, V.

AU - Cleophas, L.G.W.A.

PY - 2017/9/26

Y1 - 2017/9/26

N2 - We investigate the impact of using different algorithmic techniques and data representations in algorithms to calculate the transitive closure of a finite binary relation. These techniques are change monitor, loop fusion, loop tiling and short-circuiting. We explain them and how they are applied in the algorithms. We measured the impact of these techniques on the elapsed time to execute the algorithms, using C++ implementations with two different data representations, and using various data sets. The investigation also covers more basic transitive closure algorithms, and as a result forms a large-scale empirical comparison of such algorithms.

AB - We investigate the impact of using different algorithmic techniques and data representations in algorithms to calculate the transitive closure of a finite binary relation. These techniques are change monitor, loop fusion, loop tiling and short-circuiting. We explain them and how they are applied in the algorithms. We measured the impact of these techniques on the elapsed time to execute the algorithms, using C++ implementations with two different data representations, and using various data sets. The investigation also covers more basic transitive closure algorithms, and as a result forms a large-scale empirical comparison of such algorithms.

KW - Algorithmic techniques

KW - Benchmarking

KW - Transitive closure

UR - http://www.scopus.com/inward/record.url?scp=85032639932&partnerID=8YFLogxK

U2 - 10.1145/3129416.3129425

DO - 10.1145/3129416.3129425

M3 - Conference contribution

AN - SCOPUS:85032639932

SN - 978-1-4503-5250-5

SP - 1

EP - 10

BT - SAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa

PB - Association for Computing Machinery, Inc

CY - New York

ER -

Pieterse V, Cleophas LGWA. Benchmarking optimised algorithms for transitive closure. In SAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa . New York: Association for Computing Machinery, Inc. 2017. p. 1-10. 27 https://doi.org/10.1145/3129416.3129425