K-clique and k-cycle counting in the streaming model.
Published: 2006
Language: eng
Number of pages: 64
ISBN-13: 9780494210628
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 &isin; (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 &isin; (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 &isin; (1,1.9]. Our algorithm achieves space efficiency when k is small and the density of Kk or C k in G is large.
Notes: Source: Masters Abstracts International, Volume: 45-03, page: 1534.

Advisor: Allan Borodin.

Thesis (M.Sc.)--University of Toronto, 2006.

Electronic version licensed for access by U. of T. users.

ROBARTS MICROTEXT copy on microfiche.