K-clique and k-cycle counting in the streaming model.

Description

In this thesis, we give algorithms for two graph problems: k -clique (Kk) and k-cycle (Ck) counting in the streaming model. The streaming model is a computational model to solve problems on large sequential data sets. Compared to the conventional computational model, the streaming model requires efficient space and small time per item.The input of the problems is the number of vertices n v, for a given graph G, constants epsilon', delta > 0, an integer k ∈ (0, nv), and a sequential set of edges of G in "an arbitrary order. The algorithm reduces the counting problems to Frequency Moment problems using a sketch over alpha - stable random variables for alpha ∈ (1,1.9] and pseudorandom generators. Our algorithm is based on Indyk's technique. Indyk claims his technique is provably correct for general alpha other than 1 or 2 but he does not aware any practical applications [16]. This thesis shows that k-clique (Kk) and k-cycle (C k) counting are such applications involving general alpha ∈ (1,1.9]. Our algorithm achieves space efficiency when k is small and the density of Kk or C k in G is large.

Subjects

Links

• URL