3 papers
cs.DS2026
Optimal Passes and Perfect Sampling for Similarity Graph Statistics
Qin Zhang
We study statistical estimation on implicit weighted similarity graphs presented as node-arrival streams. Previous work~\cite{LZ26b} obtained constant-pass, sublinear-space algorit…
cs.DS2026
Statistics of Similarity Graphs in Node-Arrival Streams
Kaiwen Liu, Qin Zhang
In this paper, we study several statistical problems on similarity graphs in the node-arrival streaming model, including degree moments, diversity index, degree-moment sampling, an…
cs.DS2026
Estimating Correlation Clustering Cost in Node-Arrival Stream
Kaiwen Liu, Seba Daniela Villalobos, Qin Zhang
We study the correlation clustering problem in the node-arrival data stream model. Unlike previous work, where the stream consists of the graph's edges, we focus on the setting in…