PCSA-based Algorithm Maintain r FM sketches but update j < r sketches Generate j hash functions H(x) that map x to [1,r] Initialize each FM to zero For each record (x,t) in dataset For each of the j hash functions H() i = H(x) Update i-th FM sketch Answering a query For any t, let B i (t) be the position of left most entry smaller than t in i- th FM Let B = ( B 1 (t) + B 2 (t) … + B r (t) )/ r Number of distinct elements arrived after (inclusive) t = (α * 2 B )/ j where α = 1.2897385 Inspired by PCSA technique in P..
{}