CS599 Graph Analytics

Fall 2021

​

Lectures 14, 15, 17 10/21,10/26, 11/2

Charalampos E. Tsourakakis �ctsourak@bu.edu

Next few lectures agenda

• Foundations of streaming algorithms (moment estimation, heavy hitters) �
• Graph streaming algorithms
• Connectivity
• Triangles
• Matchings

The Streaming model

Input

-Stream of elements

- Order may be adversarial

- One pass over the stream

Goals�- Compute as accurately as possible statistics of interest

• E.g., Number of distinct elements appear in the stream, frequency moments, entropy etc.

- Key constraint: Minimum space algorithm

- Fast query and update times

​

Moment estimation problem

• Define the frequency of i as ��
• p=0: distinct elements
• p=1: length of stream
• p=2: repeat size/self-join size/Gini coefficient/surprise index in DB
• p=+inf: We define in this case �

Types of streams

A convenient way to think of the stream is as a sequence of updates of the form (i,Δ) to the histogram x[1,..n] of the universe [n].

​

​

Common assumptions: (i) Δ integer (ii) log(mM) = log(n) where |Δ|<=M

• Insert only stream: Δ=1��
• Strict Turnstile: we may have deletions, but we are guaranteed that all x_i values are non-negative throughout the stream
• General turnstile: anything goes, negative updates and negative x coordinates

Gap!

Morris algorithm

• Robert Morris has been credited historically with the first �streaming algorithm for estimating the F1 norm of a stream.
• Cash register model/insertion only�
• Key idea: instead of maintaining the actual length of the stream�m, keep the logarithm.
• E.g., if m=145, then by knowing the order of magnitude ~10²�we can tell that our number is between 100 and 999

​

• This allows us to use loglog(m) bits to represent m approximately

​

​

How to save 1 bit?

• Maintain a counter c (aka Morris counter)
• init(): c← 0
• process()�For each item in the stream
• Increase c with probability 1/2
• o/w keep same value
• Output estimate 2c

​

Let Z be the value of the counter after m increments.

• Z~Bin(m,½)
• E[Z]=m/2
• Var[Z] =m/4
• Space complexity: lg(m/2)=lg(m)-1 → we saved one bit at the cost of accuracy.

How to save k bits?

• Maintain a counter c (aka Morris counter)
• init(): c← 0
• process()�For each item in the stream
• Increase c with probability 1/2^k
• o/w keep same value
• Output estimate 2^kc

​

Let Z be the value of the counter after m increments.

• Z~Bin(m,2^-k)
• E[Z]=m/2^k
• Var[Z] = m/2^k (1-1/2^k)~m/2^k
• Space complexity: lg(m/2^k)=lg(m)-k → we saved k bits

How to save k bits?

​

• Another perspective as a birth process �
• Counter values follow a binomial distribution:

0

…

…

p

p

p

p

1-p

1-p

1-p

Morris algorithm → birth process with adaptive sampling

• Maintain a log-counter c (aka Morris counter)
• init(): c← 0
• process()�For each item in the stream
• Increase c with probability 1/2^c
• o/w keep same value
• Output estimate 2^c-1

0

…

…

Why this estimator?

Claim: Define Xn to be the value of the counter after n increments. Then, E[2^Xn]=n+1.

​

Proof (induction)

Base case: If n=0, X_n=0 and thus the claim holds.

Inductive step: By conditional expectation rule E[2^Xn+1]=E[E[2^Xn+1|X_n]] and the inductive hypothesis, we obtain the following expression:

​

​

​

​

Properties of Morris algorithm

​

1. The expectation of the variable Z=2^Xm satisfies the following:

� E[Z]=m+1

�Corollary: Morris algorithm outputs an unbiased estimator of m. �

1. The variance of Z is equal to Var[Z]=m(m-1)/2

�Observation: No improvement in terms of concentration as m grows since Var(Z)/E(Z)² is constant.

Morris algorithm

Morris+

• ^{Suppose we run s Morris counters and we output the average}
• ^{The average of this estimator remains the same but..}
• ^{the variance scales down by a factor of 1/s}

​

​

s

Reducing variance: Morris++

Claim: The space complexity with probability 1-δ is and we obtain an (ε,δ)-approximation scheme to F1 for insert-only streams. ���

s

Morris++: Median of t Moris+’s where

Moris+: avg of s independent �Morris counters

Moris+: avg of s independent �Morris counters

Moris+: avg of s independent �Morris counters

Reducing variance: change basis

​

• ​
• The expectation of the variable Z=((1+a)^Xm-1)/a satisfies the following:

� E[Z]=m

​

• The variance of Z is equal to Var[Z]=a m(m-1)/2

​

…

1/(1+a)^X

1 - 1/(1+a)^X

vs.

deterministic

Morris₂

Morris_1+a

How to set a?

• Set a=2ε²δ and apply Chebyshev’s inequality ����
• Space complexity: ��

​

…

1/(1+a)^X

1 - 1/(1+a)^X

Morris_1+a

Optimal Algorithm for F1

• Nelson and Yu proved recently that Morris algorithm�Is optimal by
• Tightening the analysis of the space complexity�����for an (ε,δ)-approximation scheme to F₁.�
• Proving a tight lower bound, and thus practically nailing down the problem.

Merging Morris Counters

• Imagine that we have distributed our computation across k machines.
• We have two Morris counter values, c₁ and c₂. What should our estimate be?
• Suppose we have the same base b=(1+a) for 1>=a>0.

�Merge(c₁,c₂)

• a=min(c₁,c₂), β=max(c₁,c₂)
• For j← 0 to α-1
• if U[0,1]<b^j-β then β← β+1

�Intuition: simulating updates in the second counter by observing that in order to have an increase from x to x+1 we need b^x updates.

Stream 1

Stream 2

c₁

c₂

Flajolet-Martin (FM) sketch

• Key assumption: We have an idealized hash function that maps each element of the universe into a string of random bits (i.e., Pr(bit=0)=Pr(bit=1)=½) ����

�

• Intuition: If we see the prefix 11110xx, probably we have seen more than 32 distinct items.�
• Idea: Keep track of prefixes of the form 1^k0

Flajolet-Martin (FM) sketch

​

• FM estimator: Clearly, 2^R where R is the largest size of such a prefix approximates the number of distinct elements. However, it turns out there is some small bias: ��
• Flajolet and Martin proved the following remarkable result: ���� where ν(p)=#bits equal to 1 in binary representation of p�
• Thus, an unbiased (modulo negligible terms) estimator becomes �
• Fascinating analysis of an algorithm

Flajolet-Martin (FM) sketch

​

​

Important functions �1. h(x) = hash function that transforms x into a uniform binary string

2. ρ(x) = position of leftmost 0 (e.g., ρ(111010100000)=4)

�Algorithm

• Initialize a bitmask with L bits to 0, i.e., BITMASK �
• For each element x in the stream
• BITMASK[ρ(h(x))] ← 1 �
• Set R← ρ(BITMASK)�
• Output

Flajolet-Martin (FM) sketch

​

• Is the constant 1/φ unexpected in the estimator?
• Intuition: since if we have a prefix 1111...10 there are likely to be more than 2^R and less than 2^R+1 elements. �
• Variance of the estimator is 1.257, which in practice means it can be off by a factor of 2. �
• Question: how do we reduce variance?
• Idea 1: use multiple hash functions
• Idea 2: generalize FM counters from binary strings to (d+1)-ary strings, where we count up to a certain threshold d how many hashes hit a bit of the bitmask.
• Idea 3: combine the above

Stochastic Averaging

• We improve the accuracy of the algorithm by a multiplicative factor of by taking the average of k different hash function ⇒ expensive �
• Better idea: use the first bits to create substreams! ��Split the elements in k=2^l substreams by using the first l bits of the hash. E.g, for l=2�h(v) = b₁b₂ b₃b₄b₅...

Substream id hash value�

​

Flajolet-Martin theorem

The estimator Z is asymptotically unbiased, i.e., E_n[Z] → n and the coefficient �

of variation using k bitmasks is �Memory: O(klogn)

Example: can count cardinalities up to 10⁹ with error <=6% using 4kBs of memory (=4096 bytes)**

“Caveat” of their work: Practical implementations of the hash function are not discussed.

* See also Mitzenmacher-Vadhan: Why simple hash functions work: Exploiting the entropy in a data stream

K Minimum Values (kMV) sketch

Basic idea: Use a “good enough” hash function h:[n] → R and the k smallest hashed values.

KMV-Init(k)

• Pick hash function h
• Initialize L=[] for k ( item, hash(item) ) pairs

KMV-Update(x)�- If x is not in L

L← L U {(x,h(x))}� if |L|>k then remove x with largest h(x) value from L

KMV-Query()

v← largest hash value in L�Return (k-1) R/v

KMV analysis

​

Let A be the set of distinct elements.

• What is the probability that our estimator will exceed (1+ε)|Α|?

���

​

�Let’s assume h is chosen from a family of pairwise independent hash functions, and that R is large enough to ensure hash collisions are unlikely to occur (e.g., R=n³)

AMS sketch for F_p

Theorem: For every ε,δ>0, there exists a randomized algorithm A that computes a number Y so that the probability that Y deviates from F_p by more than εF_p is at most δ. ��Furthermore, algorithm A uses memory bits.

�

Lower bound: For any fixed p>5, δ<½, any randomized algorithm that outputs a number � �Z_p such that

​

​

AMS sketch for F_k

​

• Suppose the length of the stream m=F₁ is known a priori.��Algorithm�
• Choose a random position p in the stream member, and let x_p=v. �
• Let �
• Output �

Remarks�In order to get an (ε,δ)-approximation scheme we set�and we take the median of s₂ variables each being the average of s₁ independent Xs.

Reservoir sampling

• If we do not know m a priori, we use standard reservoir sampling. �
• When the element x_j arrives we update our sample with probability 1/j.�
• In case the replacement takes place, we reset r=1.�
• If we do not replace our sample, then if x_j is equal to the sample value v, we increase the value of r by 1.

Improved AMS sketch for F₂

​

• The previous theorem yields that we can get an estimate for F2 using�memory bits. �
• For F2, a logarithmic number of bits suffices with the following different algorithm:�Algorithm
• Let h:[n] → {-1,+1} be chosen from a 4-wise independent hash family H.
• z← 0
• For each element x in the stream
1. z← z+h(x)
• Output z^2�
• Space Usage:

AMS sketch

• Flajolet and Martin assumed the existence of a family of hash functions that exhibit ideal properties. ��
• Alon, Matias, Szegedy provided a slight modification of the FM sketch that uses 2-wise independent hash functions �
• Construction of 2-wise independent hash function
• F=GF(2^d) where 2^d>n
• Choose a,b uar and independently from F
• h(x)=ax+b where product and addition are computed in the field F
• E.g., h(x) = ax+b mod p where p is prime��

AMS Sketch for F₀

• For each element x in the stream
• Compute r(h(x))=largest value r such that the rightmost bits of h(x) are 0.
• R=max(R,r(h(x))
• Output Y=2^R

​

Due to the random choice of a,b

1. h(x) is uniformly distributed over F. Therefore, �
2. The mapping is pairwise independent

​

In other words, for x,y distinct

AMS Sketch for F₀

​

AMS Sketch for F₀

Theorem: For every c>2 there exists an algorithm that outputs an estimate Y of F₀ such that the probability that the ratio between Y and F₀ is not between 1/c and c is at most 2/c.

​

Space usage: O(logn) to store the hash functions, O(loglogn) to store r.

�Median trick: the failure probability can become δ using the standard median trick, i.e., repeat the process log(1/δ) times and output the median. This yields a (O(1), δ) approximation scheme. ��Remark: The intuition is the same as FM, namely on average one out of F0 distinct numbers will satisfy ρ(h(x))>=log₂(F₀), so yields a good approximation of log₂(F₀).�

Triangle counting via moment estimation

• Define T_i to be the number of triples with i edges between them.��
• Let’s compute the moments of the virtual stream. Clearly: �

Stream update:(u,v) Virtual stream: (u,v,x₁),...,(u,v,x_n-2)

Triangle counting via moment estimation

• The number of distinct elements in the virtual stream is �
• The second moment F₂ is given by the following equation������
• Idea: Thus, we keep two sketches, one for estimating F₀ and one for estimation F₂ and at the end of the stream we solve a linear system to compute T₃. �
• Space: �