Sketching and streaming high-dimensional vectors
Sketching and streaming high-dimensional vectors
复制标题
绘制和流式传输高维向量
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Jelani Nelson
中科院分区：
文献类型：
--
作者：
Jelani Nelson
数据集的草图是一个小空间数据结构，支持某些预先指定的查询集（和可能的更新），而在实际存储所有数据的空间中次要使用空间。应用程序本身可以通过一个小空间算法来计算，只有一个通过一个通过数据，一种所谓的流算法和流媒体的素描。和数据库。 •在旋转门模型中用于锤式估计的流算法，可实现最佳的空间复杂性。最佳算法也具有快速的O（1/e）log log（1/e））更新时间（1±e）近似值•从旋转栅流中的经验熵估计到矩估计的一般减少仅针对此问题的近乎最佳的空间复杂性。 e）使用概率1 -δ，我们嵌入了最佳尺寸O（e -2 log（1/δ））中，使得分布的每个矩阵都具有O（e -1 log（1/δ））非 - 每列零条目。
A sketch of a dataset is a small-space data structure supporting some prespecified set of queries (and possibly updates) while consuming space substantially sublinear in the space required to actually store all the data. Furthermore, it is often desirable, or required by the application, that the sketch itself be computable by a small-space algorithm given just one pass over the data, a so-called streaming algorithm. Sketching and streaming have found numerous applications in network traffic monitoring, data mining, trend detection, sensor networks, and databases. In this thesis, I describe several new contributions in the area of sketching and streaming algorithms. • The first space-optimal streaming algorithm for the distinct elements problem. Our algorithm also achieves O(1) update and reporting times. • A streaming algorithm for Hamming norm estimation in the turnstile model which achieves the best known space complexity. • The first space-optimal algorithm for pth moment estimation in turnstile streams for 0 < p < 2, with matching lower bounds, and another space-optimal algorithm which also has a fast O(log(1/e) log log(1/e)) update time for (1 ± e)approximation. • A general reduction from empirical entropy estimation in turnstile streams to moment estimation, providing the only known near-optimal space-complexity upper bound for this problem. • A proof of the Johnson-Lindenstrauss lemma where every matrix in the support of the embedding distribution is much sparser than previous known constructions. In particular, to achieve distortion (1 ± e) with probability 1 − δ, we embed into optimal dimension O(e−2 log(1/δ)) and such that every matrix in the support of the distribution has O(e−1 log(1/δ)) non-zero entries per column. Thesis Supervisor: Erik D. Demaine Title: Professor Thesis Supervisor: Piotr Indyk Title: Professor