Hashing-based hybrid duplicate detection for Bayesian network structure learning

Niklas Jahnsson; Brandon Malone; Petri Myllymäki

doi:10.1007/978-3-319-28379-1_4

Hashing-based hybrid duplicate detection for Bayesian network structure learning

Niklas Jahnsson, Brandon Malone^*, Petri Myllymäki

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

1 Citation (Scopus)

Abstract

In this work, we address the well-known score-based Bayesian network structure learning problem. Breadth-first branch and bound (BFBnB) has been shown to be an effective approach for solving this problem. Delayed duplicate detection (DDD) is an important component of the BFBnB algorithm. Previously, an external sortingbased technique, with complexity O(mlogm), where m is the number of nodes stored in memory, was used for DDD. In this work, we propose a hashing-based technique, with complexity O(m), for DDD. In practice, by removing the O(logm) overhead of sorting, over an order of magnitude more memory is available for the search. Empirically, we show the extra memory improves locality and decreases the amount of expensive external memory operations. We also give a bin packing algorithm for minimizing the number of external memory files.

Original language	English
Title of host publication	Advanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings
Editors	Joe Suzuki, Maomi Ueno
Publisher	Springer
Pages	46-60
Number of pages	15
ISBN (Print)	9783319283784
DOIs	https://doi.org/10.1007/978-3-319-28379-1_4
Publication status	Published - 1 Jan 2015
MoE publication type	A4 Conference publication
Event	International Workshop on Advanced Methodologies for Bayesian Networks - Yokohama, Japan Duration: 16 Nov 2015 → 18 Nov 2015 Conference number: 2

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9505
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	International Workshop on Advanced Methodologies for Bayesian Networks
Abbreviated title	AMBN
Country/Territory	Japan
City	Yokohama
Period	16/11/2015 → 18/11/2015

Keywords

Bayesian networks
Delayed duplicate detection
State space search
Structure learning

Access to Document

10.1007/978-3-319-28379-1_4

Cite this

Jahnsson, N., Malone, B., & Myllymäki, P. (2015). Hashing-based hybrid duplicate detection for Bayesian network structure learning. In J. Suzuki, & M. Ueno (Eds.), Advanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings (pp. 46-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9505). Springer. https://doi.org/10.1007/978-3-319-28379-1_4

Jahnsson, Niklas ; Malone, Brandon ; Myllymäki, Petri. / Hashing-based hybrid duplicate detection for Bayesian network structure learning. Advanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings. editor / Joe Suzuki ; Maomi Ueno. Springer, 2015. pp. 46-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9b0f87c78b2c4881851ca8d4774a2de0,

title = "Hashing-based hybrid duplicate detection for Bayesian network structure learning",

abstract = "In this work, we address the well-known score-based Bayesian network structure learning problem. Breadth-first branch and bound (BFBnB) has been shown to be an effective approach for solving this problem. Delayed duplicate detection (DDD) is an important component of the BFBnB algorithm. Previously, an external sortingbased technique, with complexity O(mlogm), where m is the number of nodes stored in memory, was used for DDD. In this work, we propose a hashing-based technique, with complexity O(m), for DDD. In practice, by removing the O(logm) overhead of sorting, over an order of magnitude more memory is available for the search. Empirically, we show the extra memory improves locality and decreases the amount of expensive external memory operations. We also give a bin packing algorithm for minimizing the number of external memory files.",

keywords = "Bayesian networks, Delayed duplicate detection, State space search, Structure learning",

author = "Niklas Jahnsson and Brandon Malone and Petri Myllym{\"a}ki",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-319-28379-1_4",

language = "English",

isbn = "9783319283784",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "46--60",

editor = "Joe Suzuki and Maomi Ueno",

booktitle = "Advanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings",

address = "Germany",

note = "International Workshop on Advanced Methodologies for Bayesian Networks, AMBN ; Conference date: 16-11-2015 Through 18-11-2015",

}

Jahnsson, N, Malone, B & Myllymäki, P 2015, Hashing-based hybrid duplicate detection for Bayesian network structure learning. in J Suzuki & M Ueno (eds), Advanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9505, Springer, pp. 46-60, International Workshop on Advanced Methodologies for Bayesian Networks, Yokohama, Japan, 16/11/2015. https://doi.org/10.1007/978-3-319-28379-1_4

Hashing-based hybrid duplicate detection for Bayesian network structure learning. / Jahnsson, Niklas; Malone, Brandon; Myllymäki, Petri.
Advanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings. ed. / Joe Suzuki; Maomi Ueno. Springer, 2015. p. 46-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9505).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Hashing-based hybrid duplicate detection for Bayesian network structure learning

AU - Jahnsson, Niklas

AU - Malone, Brandon

AU - Myllymäki, Petri

N1 - Conference code: 2

PY - 2015/1/1

Y1 - 2015/1/1

N2 - In this work, we address the well-known score-based Bayesian network structure learning problem. Breadth-first branch and bound (BFBnB) has been shown to be an effective approach for solving this problem. Delayed duplicate detection (DDD) is an important component of the BFBnB algorithm. Previously, an external sortingbased technique, with complexity O(mlogm), where m is the number of nodes stored in memory, was used for DDD. In this work, we propose a hashing-based technique, with complexity O(m), for DDD. In practice, by removing the O(logm) overhead of sorting, over an order of magnitude more memory is available for the search. Empirically, we show the extra memory improves locality and decreases the amount of expensive external memory operations. We also give a bin packing algorithm for minimizing the number of external memory files.

AB - In this work, we address the well-known score-based Bayesian network structure learning problem. Breadth-first branch and bound (BFBnB) has been shown to be an effective approach for solving this problem. Delayed duplicate detection (DDD) is an important component of the BFBnB algorithm. Previously, an external sortingbased technique, with complexity O(mlogm), where m is the number of nodes stored in memory, was used for DDD. In this work, we propose a hashing-based technique, with complexity O(m), for DDD. In practice, by removing the O(logm) overhead of sorting, over an order of magnitude more memory is available for the search. Empirically, we show the extra memory improves locality and decreases the amount of expensive external memory operations. We also give a bin packing algorithm for minimizing the number of external memory files.

KW - Bayesian networks

KW - Delayed duplicate detection

KW - State space search

KW - Structure learning

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

U2 - 10.1007/978-3-319-28379-1_4

DO - 10.1007/978-3-319-28379-1_4

M3 - Conference article in proceedings

AN - SCOPUS:84955326861

SN - 9783319283784

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 46

EP - 60

BT - Advanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings

A2 - Suzuki, Joe

A2 - Ueno, Maomi

PB - Springer

T2 - International Workshop on Advanced Methodologies for Bayesian Networks

Y2 - 16 November 2015 through 18 November 2015

ER -

Jahnsson N, Malone B, Myllymäki P. Hashing-based hybrid duplicate detection for Bayesian network structure learning. In Suzuki J, Ueno M, editors, Advanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings. Springer. 2015. p. 46-60. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-28379-1_4

Hashing-based hybrid duplicate detection for Bayesian network structure learning

Abstract

Publication series

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

Cite this