Paper Info
Title
Range Thresholding on Streams.
Abstract
This paper studies a type of continuous queries called range thresholding on streams (RTS). Imagine the stream as an unbounded sequence of elements each of which is a real value. A query registers an interval, and must be notified as soon as a certain number of incoming elements fall into the interval. The system needs to support multiple queries simultaneously, and aims to minimize the space consumption and computation time. Currently, all the solutions to this problem entail quadratic time O(nm) to process n stream elements and m queries, which severely limits their applicability to only a small number of queries. We propose the first algorithm that breaks the quadratic barrier, by reducing the computation cost dramatically to O(n + m), subject only to a polylogarithmic factor. The algorithm is general enough to guarantee the same on weighted versions of the queries even in d-dimensional space of any constant d. Its vast advantage over the previous methods in practical environments has been confirmed through extensive experimentation.
Year
DOI
Venue
2016
10.1145/2882903.2915965
SIGMOD/PODS'16: International Conference on Management of Data San Francisco California USA June, 2016
Keywords
Field
DocType
Range Thresholding,Streams,Algorithms
Small number,Data mining,Computer science,Quadratic equation,Algorithm,Theoretical computer science,Thresholding,STREAMS,Time complexity,Database,Computation
Conference
ISBN
Citations 
PageRank 
978-1-4503-3531-7
1
0.37
References 
Authors
15
3
Name
Order
Citations
PageRank
Miao Qiao133.44
Junhao Gan21216.63
Yufei Tao37231316.71