Stream Frequency over Interval Queries

Summary: Generalized sliding-window frequency queries over arbitrary intervals enable hierarchical drill-down. Deterministic sketches achieve improved space with O(1) updates/queries, delivering 90–250× faster processing, ≥730× faster queries, and ≥40% lower space than prior work. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h96202891e858952c
Venue: VLDB
Year: 2019
Pagerank: 5.2828968e-05
Overall Rank: 8,764 | 41.08%
DOI: 10.14778/3297753.3297762

Incoming Non-self Citations Over Time

Authors

1. Ran Ben Basat (Harvard University)
2. Roy Friedman (Technion)
3. Rana Shahout (Technion)

BibTeX Citation

@article{basat_vldb19,
        title = {{Stream Frequency over Interval Queries}},
        author = {Basat, Ran Ben and Friedman, Roy and Shahout, Rana},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {4},
        pages = {433--445},
        doi = {10.14778/3297753.3297762},
        url = {https://doi.org/10.14778/3297753.3297762},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,415	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.3350162e-05
8,776	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.2800094e-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
456	Mergeable Summaries	2012	PODS	0.0001791284
710	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014608975
1,636	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010016656
2,875	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.9193665e-05
3,708	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	7.0812099e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,772	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB
2	11,737	A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams	2023	SIGMOD
3	12,350	Range Thresholding on Streams	2016	SIGMOD
4	1,383	On-the-Fly Sharing for Streamed Aggregation	2006	SIGMOD
5	9,496	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
6	7,870	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
7	909	Finding Frequent Items in Data Streams	2008	VLDB
8	11,945	Frequent Elements with Witnesses in Data Streams	2021	PODS
9	3,326	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB
10	124	Approximate Frequency Counts over Data Streams	2002	VLDB