Algoritmusok adatfolyamokon
Előadás
Benczúr András
MTA SZTAKI és ELTE TTK Operációkutatás tanszék
Idöpont
csütörtök 16:00-17:30, ELTE D
3-607
Előismeretek:
Algoritmusok, valószínűségszámítás és lineáris algebra alapjai
Tervezett tematika
Bevezetés I: szublineáris tárral vagy időben megoldható feladatok
Bevezetés II: adatforrások, IP forgalom tulajdonságai
Bevezetés III: külső táras algoritmusok
Különböző elemek számának meghatározása
Mintavételezés
Gyakoriságok
Nagy adatbázisok kivonatolása
Kvantilisek meghatározása és hisztogramok
Mozgó ablak technikák
Alsó korlátok
Cache kezelés
Irodalom
- External Memory Algorithms and Data Structures, J. S. Vitter. DIMACS Series.
- Towards Estimation Error Guarantees for Distinct Values, M. Charikar, S. Chaudhuri, R. Motwani, and V. Narasayya. PODS 2000.
Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, P. B. Gibbons. VLDB 2001.
- Sampling from a Moving Window over Streaming Data, B. Babcock, M. Datar, and R. Motwani. SODA 2002.
On Random Sampling over Joins, S. Chaudhuri, R. Motwani, and V. Narasayya. SIGMOD 1999.
Towards Estimation Error Guarantees for Distinct Values, M. Charikar, S. Chaudhuri, R. Motwani, and V. Narasayya. PODS 2000.
Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, P. B. Gibbons. VLDB 2001.
Sampling algorithms: lower bounds and applicaitons, Z. Bar-Yossef, S. Ravi Kumar, and D. Sivakumar.STOC 2001.
- Finding Frequent Items in Data Streams, M. Charikar, K. Chen, and M. Farach-Colton. ICALP 2002.
An Approximate L1-Difference Algorithm for Massive Data Streams, J. Feigenbaum, S. Kannan, M. Strauss, M. Viswanathan. FOCS 1999.
Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation, P. Indyk. FOCS 2000.
- Tracking Join and Self-Join Sizes in Limited Storage, N. Alon, P. Gibbons, Y. Matias and M. Szegedy. PODS 1999.
Join Synopses for Approximate Query Answering, S. Acharya, P. Gibbons, V. Poosala, and S. Ramaswamy. SIGMOD 1999.
Congressional Samples for Approximate Answering of Group-By Queries, S. Acharya, P, Gibbons, and V. Poosala. SIGMOD 2000.
Overcoming Limitations of Sampling for Aggregation Queries, S. Chaudhuri, G. Das, M. Datar, R. Motwani and V. Narasayya. ICDE 2001.
A Robust Optimization-Based Approach for Approximate Answering of Aggregate Queries, S. Chaudhuri, G. Das and V. Narasayya. SIGMOD 2001.
Synopsis data structures for massive data sets, P. B. Gibbons and Y. Matias, DIMACS 1999.
- Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets, G. S. Manku, S. Rajagopalan, and B. G. Lindsay. SIGMOD 1999.
Space-efficient online computation of quantile summaries, M. Greenwald and S. Khanna. SIGMOD 2001.
Dynamic multidimensional histograms, N. Thaper, S. Guha, P. Indyk, and N. Koudas. SIGMOD 2002.
Fast, small-space algorithms for approximate histogram maintenance, A. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, and M. Strauss. STOC 2002.
- Maintaining Stream Statistics Over Sliding Windows, M. Datar, A. Gionis, P. Indyk, R. Motwani. SODA 2002.
Distributed Streams Algorithms for Sliding Windows, P. Gibbons, S. Tirthapura. SPAA 2002.
Maintaining Variance and K-Medians over Data Stream Windows. B. Babcock, M. Datar, R. Motwani, and L. O'Callaghan. Manuscript, 2002.
- Caching queues in memory buffers, R Motwani, D Thomas
Proc. SODA 2004.
Benczúr András