Approximate Range Thresholding

Authors:

Abstract
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 τ(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 < ε < 1, the task of the system is to capture an arbitrary moment during the period between the first moment when s(q) ≥ (1 - ε)⋅ τ(q) and the first moment when s(q) ≥ τ(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 łog 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.
Funding Information
  • National Natural Science Foundation of China (Project No. 62006219)
  • Australian Research Council (DE190101118, DP220101434, DP200102611)