Approximate Range Thresholding

In this paper, we study the (approximate) Range Thresholding (RT) problem over streams. Each stream element is a d-dimensional point and with a positive integer weight. An RT query q specifies a d-dimensional axis-parallel rectangular range R(q) and a positive integer threshold tau(q). Once the query q is registered in the system, define s(q) as the total weight of the elements that satisfy: (i) they arrive after q's registration, and (ii) they fall in the range R(q). Given a real number 0 < epsilon < 1, the task of the system is to capture an arbitrary moment during the period between the first moment when s(q) >= (1 - epsilon) . tau(q) and the first moment when s(q) >= tau(q). The challenge is to support a large number of RT queries simultaneously while achieving sub-quadratic overall running time and near-linear space consumption all the time. We propose a new algorithm called FastRTS , which can reduce the exponent in the poly-logarithmic factor of the state-of-the-art QGT algorithm from d + 1 to d, yet slightly increasing the log term itself. Besides, we propose two extremely effective optimization techniques which significantly improve the practical performance of FastRTS . Experimental results show that FastRTS outperforms the competitors by up to three orders of magnitude in both running time and peak memory usage.