Enumerating subgraph instances using map-reduce
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 62-73
Abstract
The theme of this paper is how to find all instances of a given “sample” graph in a larger “data graph,” using a single round of map-reduce. For the simplest sample graph, the triangle, we improve upon the best known such algorithm. We then examine the general case, considering both the communication cost between mappers and reducers and the total computation cost at the reducers. To minimize communication cost, we exploit the techniques of [1] for computing multiway joins (evaluating conjunctive queries) in a single map-reduce round. Several methods are shown for translating sample graphs into a union of conjunctive queries with as few queries as possible. We also address the matter of optimizing computation cost. Many serial algorithms are shown to be “convertible,” in the sense that it is possible to partition the data graph, explore each partition in a separate reducer, and have the total computation cost at the reducers be of the same order as the computation cost of the serial algorithm.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Counting triangles and the curse of the last reducer2011
- Counting and detecting small subgraphs via equations and matrix multiplication2011
- Cluster Computing, Recursion and DatalogLecture Notes in Computer Science, 2011
- Subgraph Enumeration in Large Social Contact Networks Using Parallel Color Coding and Streaming2010
- DOULION2009
- Size Bounds and Query Plans for Relational Joins2008
- Finding and counting given length cyclesAlgorithmica, 1997
- Some results on the containment and minimization of (in) equality queriesInformation Processing Letters, 1994
- Constraint checking with partial information1994
- Asymmetric graphsActa Mathematica Hungarica, 1963