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: 12165
Venue: VLDB
Year: 2019
Pagerank: 5.4041343e-05
Overall Rank: 8,603 | 40.98%
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,247	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.4574671e-05
8,616	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.4004741e-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
451	Mergeable Summaries	2012	PODS	0.00018151445
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010240222
2,808	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1006881e-05
3,628	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	7.2428869e-05

Semantically Similar Papers

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