1 Search Results for "Thejaswi, Suhas"


Document
Engineering Motif Search for Large Motifs

Authors: Petteri Kaski, Juho Lauri, and Suhas Thejaswi

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)


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 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).

Cite as

Petteri Kaski, Juho Lauri, and Suhas Thejaswi. Engineering Motif Search for Large Motifs. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{kaski_et_al:LIPIcs.SEA.2018.28,
  author =	{Kaski, Petteri and Lauri, Juho and Thejaswi, Suhas},
  title =	{{Engineering Motif Search for Large Motifs}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.28},
  URN =		{urn:nbn:de:0030-drops-89631},
  doi =		{10.4230/LIPIcs.SEA.2018.28},
  annote =	{Keywords: algorithm engineering, constrained multilinear sieving, graph motif problem, multi-GPU, vector-parallel, vertex-localization}
}
  • Refine by Author
  • 1 Kaski, Petteri
  • 1 Lauri, Juho
  • 1 Thejaswi, Suhas

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Parallel algorithms

  • Refine by Keyword
  • 1 algorithm engineering
  • 1 constrained multilinear sieving
  • 1 graph motif problem
  • 1 multi-GPU
  • 1 vector-parallel
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail