Sketching and streaming high-dimensional vectors

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 0(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/[epsilon]) log log(1[epsilon])) update time for (1+/-[epsilon])- 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+/-[epsilon]) with probability 1-[delta], we embed into optimal dimension 0([epsilon]-²log(1/[delta])) and such that every matrix in the support of the distribution has 0([epsilon]-¹ log(1/[delta])) non-zero entries per column.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2011

Author dc:creator

• Nelson, Jelani (Jelani Osei)

Advisor dc:contributor.advisor

• Erik D. Demaine and Piotr Indyk.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/66314

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/66314