Loading...
Please wait, while we are loading the content...
Similar Documents
895 : Sketching , Streaming and Sub-linear Space Algorithms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Indyk, Piotr |
| Copyright Year | 2008 |
| Abstract | The topic of this class is computation over data streams, and its various manifestations. A data stream is a sequence of data elements (numbers, geometric points, etc), which is much larger than the amount of available memory. The goal is to compute (perhaps approximately) some function of the data using only one pass1 over the data stream. The difficulty in designing data stream algorithms comes from the fact that any data element that has not been stored is essentialy lost forever. As a result, one must exercise care to make sure that the “important” data elements are properly selected and preserved. Data streams occur in many applications. For example, a network router must process terabits of packet data, which cannot be all stored by the router. At the same time, there are various statistics and patterns of the network traffic that are useful to know, e.g., in order to be able to detect unusual network behavior. Data stream algorithms enable computing such stats quickly and using very little memory. Other application areas include:2 databases, sensor networks, etc. See [Mut03] for more on motivation and applications. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic6/lectureNotes/lec1/lec1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
