Chain: operator scheduling for memory minimization in data stream systems
The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Abstract
In many applications involving continuous data streams, data arrival is bursty and data rate fluctuates over time. Systems that seek to give rapid or real-time query responses in such an environment must be prepared to deal gracefully with bursts in data arrival without compromising system performance. We discuss one strategy for processing bursty streams --- adaptive, load-aware scheduling of query operators to minimize resource consumption during times of peak load. We show that the choice of an operator scheduling strategy can have significant impact on the run-time system memory usage. We then present Chain scheduling, an operator scheduling strategy for data stream systems that is near-optimal in minimizing run-time memory usage for any collection of single-stream queries involving selections, projections, and foreign-key joins with stored relations. Chain scheduling also performs well for queries with sliding-window joins over multiple streams, and multiple queries of the above types. A thorough experimental evaluation is provided where we demonstrate the potential benefits of Chain scheduling, compare it with competing scheduling strategies, and validate our analytical conclusions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
On the self-similar nature of Ethernet traffic (extended version)
Leland, W. E., Taqqu, M. S., Willinger, W., & Wilson, D. V. (1994) · IEEE/ACM Transactions on Networking · doi:10.1109/90.282603 · Cited by 5,233
Wide area traffic: the failure of Poisson modeling
Paxson, V., & Floyd, S. (1995) · IEEE/ACM Transactions on Networking · doi:10.1109/90.392383 · Cited by 3,708
Models and issues in data stream systems
Babcock, B., Babu, S., Datar, M., Motwani, R., & Widom, J. (2002) · Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/543613.543615 · Cited by 2,495
Self-citationBursty and hierarchical structure in streams
Kleinberg, J. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775061 · Cited by 1,337
Bursty and Hierarchical Structure in Streams
Kleinberg, J. (2003) · Data Mining and Knowledge Discovery · doi:10.1023/a:1024940629314 · Cited by 1,170
Monitoring Streams — A New Class of Data Management Applications
Carney, D., Çetintemel, U., Cherniack, M., Convey, C., Lee, S.-D., Seidman, G., Tatbul, N., Zdonik, S., & Stonebraker, M. R. (2002) · Elsevier eBooks · doi:10.1016/b978-155860869-6/50027-5 · Cited by 842
Eddies: continuously adaptive query processing
Avnur, R., & Hellerstein, J. M. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335420 · Cited by 798
Continuously adaptive continuous queries over streams
Madden, S., Shah, M., Hellerstein, J. M., & Raman, V. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564698 · Cited by 583
Continuous queries over append-only databases
Terry, D., Goldberg, D., Nichols, D., & Oki, B. (1992) · Proceedings of the 1992 ACM SIGMOD international conference on Management of data · doi:10.1145/130283.130333 · Cited by 399
An adaptive query execution system for data integration
Ives, Z. G., Florescu, D., Friedman, M., Levy, A. Y., & Weld, D. S. (1999) · ACM SIGMOD Record · doi:10.1145/304181.304209 · Cited by 396
Cited by
Aurora: a new model and architecture for data stream management
Abadi, D. J., Carney, D., �etintemel, U., Cherniack, M., Convey, C., Lee, S., Stonebraker, M., Tatbul, N., & Zdonik, S. (2003) · The VLDB Journal The International Journal on Very Large Data Bases · doi:10.1007/s00778-003-0095-z · Cited by 1,495
The CQL continuous query language: semantic foundations and query execution
Arasu, A., Babu, S., & Widom, J. (2006) · The VLDB Journal · doi:10.1007/s00778-004-0147-z · Cited by 1,170
Self-citationSTREAM: The Stanford Data Stream Management System
Arasu, A., Babcock, B., Babu, S., Cieslewicz, J., Datar, M., Ito, K., Motwani, R., Srivastava, U., & Widom, J. (2016) · Data-Centric Systems and Applications · doi:10.1007/978-3-540-28608-0_16 · Cited by 406
Self-citationLoad shedding for aggregation queries over data streams
Babcock, B., Datar, M., & Motwani, R. (2004) · Proceedings. 20th International Conference on Data Engineering · doi:10.1109/icde.2004.1320010 · Cited by 311
Self-citationDias de Assunção, M., da Silva Veith, A., & Buyya, R. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2017.12.001 · Cited by 304
Flexible time management in data stream systems
Srivastava, U., & Widom, J. (2004) · Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1055558.1055596 · Cited by 275
STREAM: the stanford stream data manager (demonstration description)
Arasu, A., Babcock, B., Babu, S., Datar, M., Ito, K., Nishizawa, I., Rosenstein, J., & Widom, J. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872854 · Cited by 264
Self-citationOperator Scheduling in a Data Stream Manager
Carney, D., Çetintemel, U., Rasin, A., Zdonik, S., Cherniack, M., & Stonebraker, M. (2003) · Proceedings 2003 VLDB Conference · doi:10.1016/b978-012722442-8/50079-3 · Cited by 254
A survey on the evolution of stream processing systems
Fragkoulis, M., Carbone, P., Kalavri, V., & Katsifodimos, A. (2024) · The VLDB Journal · doi:10.1007/s00778-023-00819-8 · Cited by 207
BRAID: stream mining through group lag correlations
Sakurai, Y., Papadimitriou, S., & Faloutsos, C. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066226 · Cited by 166
DSPBench: A suite of benchmark applications for distributed data stream processing systems
Bordin, M. V., Griebler, D., Mencagli, G., Geyer, C. F. R., & Fernandes, L. G. L. (2020) · IEEE Access · doi:10.1109/access.2020.3043948 · Cited by 63
“The importance of memory usage was also acknowledged by the early schedulers for first-generation DSPSs [71].”
Background
Metadata
- Authors
- Babcock, B., Babu, S., Motwani, R., & Datar, M.
- Venue
- Proceedings of the 2003 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 2003-06-09
- Pages
- 253-264
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2124298185
- Cited by
- 253
- References
- 16
- FWCI
- 14.55
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.