#### Massive Data Streams in Graph Theory and Computational Geometry

#### Abstract

Streaming is an important paradigm for handling data sets that are too
large to fit in main memory. In the streaming computational model, algorithms
are restricted to using much less space than they would need to store the
input. The massive data set is accessed in a sequential fashion and,
therefore, can be viewed as a stream of data elements. The order of the data
elements in the stream is not controlled by the algorithm. There are three
important resources considered in the streaming model: the size of the
workspace, the number of passes that the algorithm makes over the stream, and
the time to process each data element in the stream. In this thesis, we study
computational-geometry problems and graph problems in the streaming model. We
design algorithms for computing diameter in the streaming and the
sliding-window models and prove some corresponding lower bounds. The
sliding-window model is a variation of the streaming model in which only more
recent data elements in the stream are considered. Previously, work in the
streaming model has focused on algorithms that use polylog space. For graph
problems, this restriction is too strong. We investigate the computational
power of the model with different space restrictions. For a graph of n
vertices, our lower bounds show that not many interesting computations can be
done when the space restriction is o(n). We also show that, by using
n*polylog(n) space, one can design algorithms that provide approximations to
some basic problems, e.g., the all-pairs, shortest-path distance problem. We
present two main algorithms that approximate these distances. We also exhibit
tradeoffs between the accuracy of the results and the resources used by the
algorithms.

Back to publications

Back to previous page