Hashing-based hybrid duplicate detection for Bayesian network structure learning

Niklas Jahnsson, Brandon Malone*, Petri Myllymäki

*Tämän työn vastaava kirjoittaja

    Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

    1 Sitaatiot (Scopus)

    Abstrakti

    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.

    AlkuperäiskieliEnglanti
    OtsikkoAdvanced Methodologies for Bayesian Networks - 2nd International Workshop, AMBN 2015, Proceedings
    ToimittajatJoe Suzuki, Maomi Ueno
    Sivut46-60
    Sivumäärä15
    DOI - pysyväislinkit
    TilaJulkaistu - 1 tammikuuta 2015
    OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
    TapahtumaInternational Workshop on Advanced Methodologies for Bayesian Networks - Yokohama, Japani
    Kesto: 16 marraskuuta 201518 marraskuuta 2015
    Konferenssinumero: 2

    Julkaisusarja

    NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Vuosikerta9505
    ISSN (painettu)0302-9743
    ISSN (elektroninen)1611-3349

    Workshop

    WorkshopInternational Workshop on Advanced Methodologies for Bayesian Networks
    LyhennettäAMBN
    MaaJapani
    KaupunkiYokohama
    Ajanjakso16/11/201518/11/2015

    Sormenjälki Sukella tutkimusaiheisiin 'Hashing-based hybrid duplicate detection for Bayesian network structure learning'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä