External memory K-bisimulation reduction of big graphs

Y. Luo, G.H.L. Fletcher, A.J.H. Hidders, Y. Wu, P.M.E. De Bra

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

20 Citaten (Scopus)

Samenvatting

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 > 0. The I/O cost of our partition construction algorithm is bounded by O(k · sort}(|Et|) + k · scan(|Nt|) + sort(|Nt|)), while our maintenance algorithms are bounded by O(k · sort}(|Et|) + k · scan(|Nt|). The space complexity bounds are O(|Nt|+|Et|)$ and O(k · |Nt|+k ·|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 sort(n) and 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.
Originele taal-2Engels
TitelProceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM'13, Burlingame CA, USA, October 27-November 1, 2013)
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's919-928
ISBN van geprinte versie978-1-4503-2263-8
DOI's
StatusGepubliceerd - 2013
Evenementconference; 22nd ACM International Conference on Information and Knowledge Management; 2013-10-27; 2013-11-01 -
Duur: 27 okt. 20131 nov. 2013

Congres

Congresconference; 22nd ACM International Conference on Information and Knowledge Management; 2013-10-27; 2013-11-01
Periode27/10/131/11/13
Ander22nd ACM International Conference on Information and Knowledge Management

Vingerafdruk

Duik in de onderzoeksthema's van 'External memory K-bisimulation reduction of big graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit