Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: External memory bisimulation reduction of big graphs   In this paper, we present, to our knowledge, the first known I/O efficient
solutions for computing the k-bisimulation partition of a massive directed
graph, and performing maintenance of such a partition upon updates to the
underlying graph. Ubiquitous in the theory and application of graph data,
bisimulation is a robust notion of node equivalence which intuitively groups
together nodes in a graph which share fundamental structural features.
k-bisimulation is the standard variant of bisimulation where the topological
features of nodes are only considered within a local neighborhood of radius
$k\geqslant 0$.
  The I/O cost of our partition construction algorithm is bounded by $O(k\cdot
\mathit{sort}(|\et|) + k\cdot scan(|\nt|) + \mathit{sort}(|\nt|))$, while our
maintenance algorithms are bounded by $O(k\cdot \mathit{sort}(|\et|) + k\cdot
\mathit{sort}(|\nt|))$. The space complexity bounds are $O(|\nt|+|\et|)$ and
$O(k\cdot|\nt|+k\cdot|\et|)$, resp. Here, $|\et|$ and $|\nt|$ are the number of
disk pages occupied by the input graph's edge set and node set, resp., and
$\mathit{sort}(n)$ and $\mathit{scan}(n)$ are the cost of sorting and scanning,
resp., a file occupying $n$ pages in external memory. Empirical analysis on a
variety of massive real-world and synthetic graph datasets shows that our
algorithms perform efficiently in practice, scaling gracefully as graphs grow
in size.

31
The categories of this paper are: ao-sci
34
The categories of this paper are: chem-ph
27
The categories of this paper are: comp-gas
18
The categories of this paper are: econ
32
The categories of this paper are: atom-ph
33
The categories of this paper are: plasm-ph
25
The categories of this paper are: patt-sol
17
The categories of this paper are: q-fin
21
The categories of this paper are: adap-org
6
The categories of this paper are: astro-ph
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
26
The categories of this paper are: bayes-an
9
The categories of this paper are: nlin
29
The categories of this paper are: funct-an
10
The categories of this paper are: q-bio