zbMATH — the first resource for mathematics

Synopsis data structures for massive data sets. (English) Zbl 0952.68040
Abello, James M. (ed.) et al., External memory algorithms. DIMACS workshop external memory algorithms and visualization, Rutgers Univ., New Brunswick, NJ, USA, May 20-22, 1998. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 50, 39-70 (1999).
Summary: Massive data sets with terabytes of data are becoming common-place. There is an increasing demand for algorithms and data structures that provide fast response times to queries on such data sets. In this paper, we describe a context for algorithmic work relevant to massive data sets and a framework for evaluating such work. We consider the use of “synopsis” data structures, which use very little space and provide fast (typically approximated) answers to queries. The design and analysis of effective synopsis data structures offer many algorithmic challenges. We discuss a number of concrete examples of synopsis data structures, and describe fast algorithms for keeping them up-to-date in the presence of online updates to the data sets.
For the entire collection see [Zbl 0931.00039].

68P05 Data structures
68W05 Nonnumerical algorithms
68P20 Information storage and retrieval of data
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
62-04 Software, source code, etc. for problems pertaining to statistics
68Q25 Analysis of algorithms and problem complexity