Summary Data Structures for Massive Data

摘要

Prompted by the need to compute holistic properties of increasingly large data sets, the notion of the "summary" data structure has emerged in recent years as an important concept. Summary structures can be built over large, distributed data, and provide guaranteed performance for a variety of data summarization tasks. Various types of summaries are known: summaries based on random sampling; summaries formed as linear sketches of the input data; and other summaries designed for a specific problem at hand.