Paper Info
Title
Data Stream Algorithms via Expander Graphs
Abstract
We present a simple way of designing deterministic algorithms for problems in the data stream model via lossless expander graphs. We illustrate this by considering two problems, namely, k-sparsity testing and estimating frequency of items.
Year
DOI
Venue
2008
10.1007/978-3-540-92182-0_8
ISAAC
Keywords
Field
DocType
lossless expander graph,deterministic algorithm,data stream algorithms,data stream model,expander graphs,k-sparsity testing,expander graph
Combinatorics,Expander graph,Data stream,Computer science,Bipartite graph,Algorithm,Theoretical computer science,Hash function,Lossless compression
Conference
Volume
ISSN
Citations 
5369
0302-9743
4
PageRank 
References 
Authors
0.43
20
1
Name
Order
Citations
PageRank
Sumit Ganguly1813236.01