An approach to problems where the data is too large to be stored in Random Access Memory let alone be analyzed in full is Sampling. The simplest kind of sampling, namely Uniform Sampling can be implemented in one pass through the data. Recently, algorithms for solving approximately a host of graph and combinatorial problems which use a surprisingly small uniformly drawn sample have been developed.
There has also been progress on using non-uniform sampling in the ``streaming'' model, which allows just one pass through the data. Clustering and frequency estimation problems have been thus tackled.
We will also consider problems, where, the data consists
of a large matrix which can be stored in external memory and read a limited
number of times. We will present algorithms to find a succinct synopsis of
the matrix, storable in RAM, from which, later, we may answer Similarity (arising
in Information Retrieval) and other queries fast.