The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Evaluating window joins over unbounded streams
Abstract
We investigate algorithms for evaluating sliding window joins over pairs of unbounded streams. We introduce a unit-time-basis cost model to analyze the expected performance of these algorithms. Using this cost model, we propose strategies for maximizing the efficiency of processing joins in three scenarios. First, we consider the case where one stream is much faster than the other. We show that asymmetric combinations of join algorithms, (e.g., hash join on one input, nested-loops join on the other) can outperform symmetric join algorithm implementations. Second, we investigate the case where system resources are insufficient to keep up with the input streams. We show that we can maximize the number of join result tuples produced in this case by properly allocating computing resources across the two input streams. Finally, we investigate strategies for maximizing the number of result tuples produced when memory is limited, and show that proper memory allocation across the two input streams can result in significantly lower resource usage and/or more result tuples produced.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Next century challenges: scalable coordination in sensor networks
Estrin, D., Govindan, R., Heidemann, J., & Kumar, S. (1999) · Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/313451.313556 · Cited by 2,703
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
Next century challenges: mobile networking for “Smart Dust”
Kahn, J. M., Katz, R. H., & Pister, K. S. J. (1999) · Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/313451.313558 · Cited by 1,660
NiagaraCQ: a scalable continuous query system for Internet databases
Chen, J., DeWitt, D. J., Tian, F., & Wang, Y. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335432 · Cited by 1,022
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
Maintaining Stream Statistics over Sliding Windows
Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539701398363 · Cited by 835
The space complexity of approximating the frequency moments
Alon, N., Matias, Y., & Szegedy, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237823 · Cited by 822
Eddies: continuously adaptive query processing
Avnur, R., & Hellerstein, J. M. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335420 · Cited by 798
Towards Sensor Database Systems
Bonnet, P., Gehrke, J., & Seshadri, P. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44498-x_1 · Cited by 791
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 - PODS '02 · doi:10.1145/543614.543615 · Cited by 745
Continuous queries over data streams
Babu, S., & Widom, J. (2001) · ACM SIGMOD Record · doi:10.1145/603867.603884 · Cited by 721
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
NiagaraCQ: a scalable continuous query system for Internet databases
Chen, J., DeWitt, D. J., Tian, F., & Wang, Y. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335432 · Cited by 481
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
Eddies: continuously adaptive query processing
Avnur, R., & Hellerstein, J. M. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335420 · Cited by 381
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2001) · Cited by 376
Making B+- trees cache conscious in main memory
Rao, J., & Ross, K. A. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335449 · Cited by 373
Ripple joins for online aggregation
Haas, P. J., & Hellerstein, J. M. (1999) · ACM SIGMOD Record · doi:10.1145/304181.304208 · Cited by 369
Processing complex aggregate queries over data streams
Dobra, A., Garofalakis, M., Gehrke, J., & Rastogi, R. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564699 · Cited by 319
Automatically Extracting Structure from Free Text Addresses.
Borkar, V., Deshmukh, K., & Sarawagi, S. (2000) · Cited by 313
On computing correlated aggregates over continual data streams
Gehrke, J., Korn, F., & Srivastava, D. (2001) · Proceedings of the 2001 ACM SIGMOD international conference on Management of data · doi:10.1145/375663.375665 · Cited by 278
A Study of Index Structures for Main Memory Database Management Systems
Lehman, T. J., & Carey, M. J. (1986) · Minds at UW (University of Wisconsin) · Cited by 267
Cache Conscious Indexing for Decision-Support in Main Memory
Rao, J., & Ross, K. A. (1998) · doi:10.7916/d8t441zb · Cited by 248
Cost-based query scrambling for initial delays
Urhan, T., Franklin, M. J. M., & Amsaleg, L. (1998) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/276304.276317 · Cited by 211
The Niagara Internet Query System.
Naughton, J. F., DeWitt, D. J., Maier, D., Aboulnaga, A., Chen, J., Galanis, L., Kang, J., Krishnamurthy, R., Luo, Q., Prakash, N., et al. (2001) · Cited by 197
Self-citationMaking B+- trees cache conscious in main memory
Rao, J., & Ross, K. A. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335449 · Cited by 187
Hancock: a language for extracting signatures from data streams
Cortes, C., Fisher, K., Pregibon, D., & Rogers, A. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347094 · Cited by 179
Cited by
Load Shedding in a Data Stream Manager
Tatbul, N., Çetintemel, U., Zdonik, S., Cherniack, M., & Stonebraker, M. (2003) · Proceedings 2003 VLDB Conference · doi:10.1016/b978-012722442-8/50035-5 · Cited by 577
Load 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
Approximate join processing over data streams
Das, A., Gehrke, J., & Riedewald, M. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872765 · Cited by 275
Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams
Golab, L., & Tamer Özsu, M. (2003) · Proceedings 2003 VLDB Conference · doi:10.1016/b978-012722442-8/50051-3 · Cited by 263
Chain: operator scheduling for memory minimization in data stream systems
Babcock, B., Babu, S., Motwani, R., & Datar, M. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872789 · Cited by 253
Metadata
- Authors
- Kang, J., Naughton, J. F., & Viglas, S. D.
- Venue
- Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405)
- Publisher
- IEEE
- Published
- 2004-05-06
- Pages
- 341-352
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2140894225
- Cited by
- 352
- References
- 28
- FWCI
- 22.84
- 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.