Engineering Motif Search for Large Motifs

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

7 Lataukset (Pure)

Abstrakti

Given a vertex-colored graph H and a multiset M of colors as input, the graph motif problem asks us to decide whether H has a connected induced subgraph whose multiset of colors agrees with M. The graph motif problem is NP-complete but known to admit randomized algorithms based on constrained multilinear sieving over GF(2^b) that run in time O(2^kk^2m {M({2^b})}) and with a false-negative probability of at most k/2^{b-1} for a connected m-edge input and a motif of size k. On modern CPU microarchitectures such algorithms have practical edge-linear scalability to inputs with billions of edges for small motif sizes, as demonstrated by Björklund, Kaski, Kowalik, and Lauri [ALENEX'15]. This scalability to large graphs prompts the dual question whether it is possible to scale to large motif sizes. We present a vertex-localized variant of the constrained multilinear sieve that enables us to obtain, in time O(2^kk^2m{M({2^b})}) and for every vertex simultaneously, whether the vertex participates in at least one match with the motif, with a per-vertex probability of at most k/2^{b-1} for a false negative. Furthermore, the algorithm is easily vector-parallelizable for up to 2^k threads, and parallelizable for up to 2^kn threads, where n is the number of vertices in H. Here {M({2^b})} is the time complexity to multiply in GF(2^b). We demonstrate with an open-source implementation that our variant of constrained multilinear sieving can be engineered for vector-parallel microarchitectures to yield hardware utilization that is bound by the available memory bandwidth. Our main engineering contributions are (a) a version of the recurrence for tightly labeled arborescences that can be executed as a sequence of memory-and-arithmetic coalescent parallel workloads on multiple GPUs, and (b) a bit-sliced low-level implementation for arithmetic in characteristic 2 to support (a).
AlkuperäiskieliEnglanti
Otsikko17th Symposium on Experimental Algorithms, SEA 2018
ToimittajatGianlorenzo D'Angelo
Sivut1-19
ISBN (elektroninen)978-3-95977-070-5
DOI - pysyväislinkit
TilaJulkaistu - 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Experimental Algorithms - Gran Sasso Science Institute, L'Aquila, Italia
Kesto: 27 kesäkuuta 201829 kesäkuuta 2018
Konferenssinumero: 17

Julkaisusarja

NimiLeibniz International Proceedings in Informatics (LIPIcs)
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Vuosikerta103
ISSN (elektroninen)1868-8969

Conference

ConferenceInternational Symposium on Experimental Algorithms
LyhennettäSEA
MaaItalia
KaupunkiL'Aquila
Ajanjakso27/06/201829/06/2018

Sormenjälki Sukella tutkimusaiheisiin 'Engineering Motif Search for Large Motifs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Laitteet

    Science-IT

    Mikko Hakala (Manager)

    Perustieteiden korkeakoulu

    Laitteistot/tilat: Facility

  • Siteeraa tätä

    Kaski, P., Lauri, J., & Muniyappa, S. (2018). Engineering Motif Search for Large Motifs. teoksessa G. D'Angelo (Toimittaja), 17th Symposium on Experimental Algorithms, SEA 2018 (Sivut 1-19). [28] (Leibniz International Proceedings in Informatics (LIPIcs); Vuosikerta 103). https://doi.org/10.4230/LIPIcs.SEA.2018.28