Flexible Time Management in Data Stream Systems

Summary: Formalizes application-defined time in DSMSs and the correctness challenges from inter-stream skew, intra-stream disorder, and variable latency. Proposes a parametrized heartbeat-generation algorithm with runtime parameter estimation to enable correct continuous-query evaluation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1328
Venue: PODS
Year: 2004
Pagerank: 0.0001870735
Overall Rank: 424 | 97.10%
DOI: 10.1145/1055558.1055596

Incoming Non-self Citations Over Time

Authors

1. Utkarsh Srivastava (Stanford University)
2. Jennifer Widom (Stanford University)

BibTeX Citation

@inproceedings{srivastava_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Flexible Time Management in Data Stream Systems}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055596},
        doi = {10.1145/1055558.1055596},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Srivastava, Utkarsh and Widom, Jennifer},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030738755
224	MillWheel: Fault-Tolerant Stream Processing at Internet Scale	2013	VLDB	0.00024130894
361	The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing	2015	VLDB	0.00020138717
732	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.00014536846
1,223	Out-of-Order Processing: A New Architecture for High-Performance Stream Systems	2008	VLDB	0.00011602265
1,703	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.9673138e-05
1,789	Fault-Tolerance in the Borealis Distributed Stream Processing System	2005	SIGMOD	9.7502324e-05
1,945	Continuous Analytics Over Discontinuous Streams	2010	SIGMOD	9.4348569e-05
2,479	Microsoft CEP Server and Online Behavioral Targeting	2009	VLDB	8.521563e-05
2,929	StreamRec: A Real-Time Recommender System	2011	SIGMOD	7.9525409e-05
3,242	SECRET: A Model for Analysis of the Execution Semantics of Stream Processing Systems	2010	VLDB	7.6053312e-05
3,332	A Heartbeat Mechanism and its Application in Gigascope	2005	VLDB	7.5129799e-05
3,342	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	7.4999147e-05
4,189	On-the-fly Progress Detection in Iterative Stream Queries	2009	VLDB	6.8435848e-05
4,389	Consistency and Completeness: Rethinking Distributed Stream Processing in Apache Kafka	2021	SIGMOD	6.7304854e-05
4,417	Massively Multi-Query Join Processing in Publish/Subscribe Systems	2007	SIGMOD	6.7148702e-05
4,942	Active Complex Event Processing over Event Streams	2011	VLDB	6.4333059e-05
5,101	To Share, or not to Share Online Event Trend Aggregation Over Bursty Event Streams	2021	SIGMOD	6.3642265e-05
5,719	Optimal and General Out-of-Order Sliding-Window Aggregation	2019	VLDB	6.1094861e-05
5,756	Clonos: Consistent Causal Recovery for Highly-Available Streaming Dataflows	2021	SIGMOD	6.097233e-05
5,776	Recognizing Patterns in Streams with Imprecise Timestamps	2010	VLDB	6.0920784e-05
6,502	Watermarks in Stream Processing Systems: Semantics and Comparative Analysis of Apache Flink and Google Cloud Dataflow	2021	VLDB	5.8604458e-05
6,680	Beyond Analytics: The Evolution of Stream Processing Systems	2020	SIGMOD	5.8049764e-05
7,321	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	5.6454313e-05
7,626	Quality-Driven Continuous Query Execution over Out-of-Order Data Streams	2015	SIGMOD	5.5800458e-05
8,138	Safety Guarantee of Continuous Join Queries over Punctuated Data Streams	2006	VLDB	5.4803781e-05
8,322	Event Trend Aggregation Under Rich Event Matching Semantics	2019	SIGMOD	5.4540698e-05
8,824	DLACEP: A Deep-Learning Based Framework for Approximate Complex Event Processing	2022	SIGMOD	5.3623113e-05
9,330	Differentially Private Stream Processing at Scale	2024	VLDB	5.2891952e-05
9,468	Disaggregated State Management in Apache Flink 2.0	2025	VLDB	5.2634238e-05
9,726	Data Integration and Data Exchange: It’s Really About Time	2013	CIDR	5.2302483e-05
9,784	Dynamic Graph Databases with Out-of-order Updates	2024	VLDB	5.2209769e-05
10,996	Scribe: How Meta transports terabytes per second in real time	2025	VLDB	5.093636e-05
11,665	Klink: Progress-Aware Scheduling for Streaming Data Systems	2021	SIGMOD	5.093636e-05
12,507	Supporting a Spectrum of Out-of-Order Event Processing Technologies: From Aggressive to Conservative Methodologies	2009	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00054667018
335	A Taxonomy of Time in Databases	1985	SIGMOD	0.00020869676
687	Sequence Query Processing	1994	SIGMOD	0.00014948592
1,027	Chain: Operator Scheduling for Memory Minimization in Data Stream Systems	2003	SIGMOD	0.00012563656
1,730	Real-Time Databases	1991	VLDB	9.9085421e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,945	Continuous Analytics Over Discontinuous Streams	2010	SIGMOD
2	722	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD
3	899	Consistent Streaming Through Time: A Vision for Event Stream Processing	2007	CIDR
4	7,284	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD
5	4,463	Consistency in a Stream Warehouse	2011	CIDR
6	26	Models and Issues in Data Stream Systems	2002	PODS
7	3,332	A Heartbeat Mechanism and its Application in Gigascope	2005	VLDB
8	8,720	Robust Real-time Query Processing with QStream	2005	VLDB
9	13,778	Scheduling Continuous Queries in Data Stream Management Systems	2008	VLDB
10	8,679	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB