Benchmarking optimised algorithms for transitive closure

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

doi:10.1145/3129416.3129425

Benchmarking optimised algorithms for transitive closure

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	SAICSIT '17 Proceedings of the South African Institute of Computer Scientists and Information Technologists, 26-28 September 2017, Thaba 'Nchu, South Africa
Place of Publication	New York
Publisher	Association for Computing Machinery, Inc
Pages	1-10
ISBN (Print)	978-1-4503-5250-5
DOIs	https://doi.org/10.1145/3129416.3129425
Publication status	Published - 26 Sept 2017
Event	2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017) - University of the Free State, Bloemfontein, South Africa Duration: 26 Sept 2017 → 28 Sept 2017 Conference number: 23 http://www.saicsit2017.org.za/

Conference

Conference	2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017)
Abbreviated title	SAICSIT 2017
Country/Territory	South Africa
City	Bloemfontein
Period	26/09/17 → 28/09/17
Internet address	http://www.saicsit2017.org.za/

Keywords

Algorithmic techniques
Benchmarking
Transitive closure

Access to Document

10.1145/3129416.3129425

Cite this

@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 = sep,

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",

note = "2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017), SAICSIT 2017 ; Conference date: 26-09-2017 Through 28-09-2017",

url = "http://www.saicsit2017.org.za/",

}

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 proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Benchmarking optimised algorithms for transitive closure

AU - Pieterse, V.

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

N1 - Conference code: 23

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

T2 - 2017 South African Institute of Computer Scientists and Information Technologists Conference (SAICSIT 2017)

Y2 - 26 September 2017 through 28 September 2017

ER -

Benchmarking optimised algorithms for transitive closure

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this