Engineering Motif Search for Large Motifs

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en Kaski, Petteri Lauri, Juho Muniyappa, Suhas
dc.contributor.editor D'Angelo, Gianlorenzo 2018-12-10T10:32:33Z 2018-12-10T10:32:33Z 2018
dc.identifier.citation Kaski , P , Lauri , J & Muniyappa , S 2018 , Engineering Motif Search for Large Motifs . in G D'Angelo (ed.) , 17th International Symposium on Experimental Algorithms (SEA 2018) . , 28 , Leibniz International Proceedings in Informatics (LIPIcs) , vol. 103 , Schloss Dagstuhl--Leibniz-Zentrum für Informatik , pp. 1-19 , International Symposium on Experimental Algorithms , L'Aquila , Italy , 27/06/2018 . DOI: 10.4230/LIPIcs.SEA.2018.28 en
dc.identifier.isbn 978-3-95977-070-5
dc.identifier.issn 1868-8969
dc.identifier.other PURE UUID: e198762a-7b4f-4561-a6a5-fa2b3d704f2a
dc.identifier.other PURE ITEMURL:
dc.identifier.other PURE LINK:
dc.identifier.other PURE FILEURL:
dc.description.abstract 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 matchwith 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). en
dc.format.extent 1-19
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.relation.ispartof International Symposium on Experimental Algorithms en
dc.relation.ispartofseries 17th International Symposium on Experimental Algorithms (SEA 2018) en
dc.relation.ispartofseries Leibniz International Proceedings in Informatics (LIPIcs) en
dc.relation.ispartofseries Volume 103 en
dc.rights openAccess en
dc.subject.other 113 Computer and information sciences en
dc.title Engineering Motif Search for Large Motifs en
dc.type A4 Artikkeli konferenssijulkaisussa fi
dc.description.version Peer reviewed en
dc.contributor.department Helsinki Institute for Information Technology HIIT
dc.contributor.department Nokia Bell Labs
dc.contributor.department Department of Computer Science
dc.subject.keyword algorithm engineering
dc.subject.keyword constrained multilinear sieving
dc.subject.keyword graph motif problem
dc.subject.keyword multi-GPU
dc.subject.keyword vector-parallel
dc.subject.keyword vertex-localization
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-201812106327
dc.identifier.doi 10.4230/LIPIcs.SEA.2018.28
dc.type.version publishedVersion

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication


My Account