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)


    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
    Number of pages15
    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)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    WorkshopInternational Workshop on Advanced Methodologies for Bayesian Networks
    Abbreviated titleAMBN


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


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

    Cite this