Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors

Summary: GPU-accelerated, deterministic stream mining of quantiles and frequencies via rasterized sorting for histogram-based epsilon-approx summaries. Co-processor GPU with minimal CPU-GPU data transfer on commodity hardware; supports fixed/variable sliding windows and large streams (>100M values), beating CPU baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3732
Venue: SIGMOD
Year: 2005
Pagerank: 6.3121293e-05
Overall Rank: 5,216 | 64.22%
DOI: 10.1145/1066157.1066227

Incoming Non-self Citations Over Time

Authors

1. Naga K. Govindaraju (University of North Carolina)
2. Nikunj Raghuvanshi (University of North Carolina)
3. Dinesh Manocha (University of North Carolina)

BibTeX Citation

@inproceedings{govindaraju_sigmod05,
        title = {{Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors}},
        author = {Govindaraju, Naga K. and Raghuvanshi, Nikunj and Manocha, Dinesh},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066227},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066227},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
305	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021872796
631	Relational Joins on Graphics Processors	2008	SIGMOD	0.00015591241
2,655	Executing Stream Joins on the Cell Processor	2007	VLDB	8.2888851e-05
3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1442477e-05
7,113	GPUQP: Query Co-Processing Using Graphics Processors	2007	SIGMOD	5.6985502e-05
8,005	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.5080221e-05
8,231	Thread Cooperation in Multicore Architectures for Frequency Counting over Multiple Data Streams	2009	VLDB	5.4617036e-05
8,487	A Case for Graphics-driven Query Processing	2023	VLDB	5.4153858e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023097188
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00017275873
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404
1,400	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010890603
1,452	Fast Computation of Database Operations using Graphics Processors	2004	SIGMOD	0.00010745803
2,283	Hardware Acceleration for Spatial Selections and Joins	2003	SIGMOD	8.8099424e-05
2,741	Hardware Acceleration in Commercial Databases: A Case Study of Spatial Operations	2004	VLDB	8.1851944e-05
3,396	A Super Scalar Sort Algorithm for RISC Processors	1996	SIGMOD	7.4473906e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD
2	261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD
3	885	Finding Frequent Items in Data Streams	2008	VLDB
4	8,005	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD
5	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
6	2,667	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD
7	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
8	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
9	3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
10	1,452	Fast Computation of Database Operations using Graphics Processors	2004	SIGMOD