Exploiting coarse grained parallelism in conceptual data mining: Finding a needle in a haystack as a distributed effort

Mark Blokpoel; Franc Grootjen; Egon van den Broek

Exploiting coarse grained parallelism in conceptual data mining: Finding a needle in a haystack as a distributed effort

Mark Blokpoel, Franc Grootjen, Egon van den Broek

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

45 Downloads (Pure)

Abstract

A parallel implementation of Ganter’s algorithm to calculate concept lattices for Formal Concept Analysis is presented. A benchmark was executed to experimentally determine the algorithm’s performance, including an AMD Athlon64, Intel dual Xeon, and UltraSPARC T1, with respectively 1, 4, and 24 threads in parallel. Two subsets of Cranfield’s collection were chosen as document set. In addition, the theoretically maximum performance was determined. Due to scheduling problems, the performance of the UltraSPARC was disappointing. Two alternate schedulers are proposed to tackle this problem. It is shown that, given a good scheduler, the algorithm can massively exploit multi-threading architectures and so, substantially reduce the computational burden of Formal Concept Analysis.

Original language	Undefined
Title of host publication	Proceedings of the 8th Dutch-Belgian Information Retrieval Workshop (DIR2008)
Editors	E. Hoenkamp, M. De Cock, V. Hoste
Place of Publication	Maastricht, The Netherlands
Publisher	Maastricht University
Pages	7-13
Number of pages	7
ISBN (Print)	978-90-5681-282-9
Publication status	Published - 14 Apr 2008
Event	8th Dutch-Belgian Information Retrieval Workshop, DIR 2008 - Maastricht, Netherlands Duration: 14 Apr 2008 → 15 Apr 2008 Conference number: 8

Publication series

Name
Publisher	Maastricht University

Conference

Conference	8th Dutch-Belgian Information Retrieval Workshop, DIR 2008
Abbreviated title	DIR
Country/Territory	Netherlands
City	Maastricht
Period	14/04/08 → 15/04/08

Keywords

METIS-252703
Formal Concept Analysis
IR-79113
Parallel
Parallelism
HMI-IE: Information Engineering
Information Retrieval (IR)
EWI-20953
concept lattices
HMI-SLT: Speech and Language Technology
Cranfield collection

Access to Document

Cite this

Blokpoel, Mark ; Grootjen, Franc ; van den Broek, Egon. / Exploiting coarse grained parallelism in conceptual data mining: Finding a needle in a haystack as a distributed effort. Proceedings of the 8th Dutch-Belgian Information Retrieval Workshop (DIR2008). editor / E. Hoenkamp ; M. De Cock ; V. Hoste. Maastricht, The Netherlands : Maastricht University, 2008. pp. 7-13

@inproceedings{f52dc198599c45c09e9c39d3849c9408,

title = "Exploiting coarse grained parallelism in conceptual data mining: Finding a needle in a haystack as a distributed effort",

abstract = "A parallel implementation of Ganter{\textquoteright}s algorithm to calculate concept lattices for Formal Concept Analysis is presented. A benchmark was executed to experimentally determine the algorithm{\textquoteright}s performance, including an AMD Athlon64, Intel dual Xeon, and UltraSPARC T1, with respectively 1, 4, and 24 threads in parallel. Two subsets of Cranfield{\textquoteright}s collection were chosen as document set. In addition, the theoretically maximum performance was determined. Due to scheduling problems, the performance of the UltraSPARC was disappointing. Two alternate schedulers are proposed to tackle this problem. It is shown that, given a good scheduler, the algorithm can massively exploit multi-threading architectures and so, substantially reduce the computational burden of Formal Concept Analysis.",

keywords = "METIS-252703, Formal Concept Analysis, IR-79113, Parallel, Parallelism, HMI-IE: Information Engineering, Information Retrieval (IR), EWI-20953, concept lattices, HMI-SLT: Speech and Language Technology, Cranfield collection",

author = "Mark Blokpoel and Franc Grootjen and {van den Broek}, Egon",

year = "2008",

month = apr,

day = "14",

language = "Undefined",

isbn = "978-90-5681-282-9",

publisher = "Maastricht University",

pages = "7--13",

editor = "E. Hoenkamp and {De Cock}, M. and V. Hoste",

booktitle = "Proceedings of the 8th Dutch-Belgian Information Retrieval Workshop (DIR2008)",

note = "8th Dutch-Belgian Information Retrieval Workshop, DIR 2008 ; Conference date: 14-04-2008 Through 15-04-2008",

}

Blokpoel, M, Grootjen, F & van den Broek, E 2008, Exploiting coarse grained parallelism in conceptual data mining: Finding a needle in a haystack as a distributed effort. in E Hoenkamp, M De Cock & V Hoste (eds), Proceedings of the 8th Dutch-Belgian Information Retrieval Workshop (DIR2008). Maastricht University, Maastricht, The Netherlands, pp. 7-13, 8th Dutch-Belgian Information Retrieval Workshop, DIR 2008, Maastricht, Netherlands, 14/04/08.

Exploiting coarse grained parallelism in conceptual data mining: Finding a needle in a haystack as a distributed effort. / Blokpoel, Mark; Grootjen, Franc; van den Broek, Egon.
Proceedings of the 8th Dutch-Belgian Information Retrieval Workshop (DIR2008). ed. / E. Hoenkamp; M. De Cock; V. Hoste. Maastricht, The Netherlands: Maastricht University, 2008. p. 7-13.

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

TY - GEN

T1 - Exploiting coarse grained parallelism in conceptual data mining: Finding a needle in a haystack as a distributed effort

AU - Blokpoel, Mark

AU - Grootjen, Franc

AU - van den Broek, Egon

N1 - Conference code: 8

PY - 2008/4/14

Y1 - 2008/4/14

N2 - A parallel implementation of Ganter’s algorithm to calculate concept lattices for Formal Concept Analysis is presented. A benchmark was executed to experimentally determine the algorithm’s performance, including an AMD Athlon64, Intel dual Xeon, and UltraSPARC T1, with respectively 1, 4, and 24 threads in parallel. Two subsets of Cranfield’s collection were chosen as document set. In addition, the theoretically maximum performance was determined. Due to scheduling problems, the performance of the UltraSPARC was disappointing. Two alternate schedulers are proposed to tackle this problem. It is shown that, given a good scheduler, the algorithm can massively exploit multi-threading architectures and so, substantially reduce the computational burden of Formal Concept Analysis.

AB - A parallel implementation of Ganter’s algorithm to calculate concept lattices for Formal Concept Analysis is presented. A benchmark was executed to experimentally determine the algorithm’s performance, including an AMD Athlon64, Intel dual Xeon, and UltraSPARC T1, with respectively 1, 4, and 24 threads in parallel. Two subsets of Cranfield’s collection were chosen as document set. In addition, the theoretically maximum performance was determined. Due to scheduling problems, the performance of the UltraSPARC was disappointing. Two alternate schedulers are proposed to tackle this problem. It is shown that, given a good scheduler, the algorithm can massively exploit multi-threading architectures and so, substantially reduce the computational burden of Formal Concept Analysis.

KW - METIS-252703

KW - Formal Concept Analysis

KW - IR-79113

KW - Parallel

KW - Parallelism

KW - HMI-IE: Information Engineering

KW - Information Retrieval (IR)

KW - EWI-20953

KW - concept lattices

KW - HMI-SLT: Speech and Language Technology

KW - Cranfield collection

M3 - Conference contribution

SN - 978-90-5681-282-9

SP - 7

EP - 13

BT - Proceedings of the 8th Dutch-Belgian Information Retrieval Workshop (DIR2008)

A2 - Hoenkamp, E.

A2 - De Cock, M.

A2 - Hoste, V.

PB - Maastricht University

CY - Maastricht, The Netherlands

T2 - 8th Dutch-Belgian Information Retrieval Workshop, DIR 2008

Y2 - 14 April 2008 through 15 April 2008

ER -