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 proceedingConference contributionScientificpeer-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 languageEnglish
    Title of host publicationAdvanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings
    EditorsJoe Suzuki, Maomi Ueno
    Pages46-60
    Number of pages15
    DOIs
    Publication statusPublished - 1 Jan 2015
    MoE publication typeA4 Article in a conference publication
    EventInternational Workshop on Advanced Methodologies for Bayesian Networks - Yokohama, Japan
    Duration: 16 Nov 201518 Nov 2015
    Conference number: 2

    Publication series

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

    Workshop

    WorkshopInternational Workshop on Advanced Methodologies for Bayesian Networks
    Abbreviated titleAMBN
    CountryJapan
    CityYokohama
    Period16/11/201518/11/2015

    Keywords

    • Bayesian networks
    • Delayed duplicate detection
    • State space search
    • Structure learning

    Fingerprint Dive into the research topics of 'Hashing-based hybrid duplicate detection for Bayesian network structure learning'. Together they form a unique fingerprint.

  • 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). https://doi.org/10.1007/978-3-319-28379-1_4