Approximate Range Thresholding
Authors:
Open Access
- 10 June 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1108-1121
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.Keywords
Funding Information
- National Natural Science Foundation of China (Project No. 62006219)
- Australian Research Council (DE190101118, DP220101434, DP200102611)
This publication has 17 references indexed in Scilit:
- Processing flows of informationACM Computing Surveys, 2012
- Processing a large number of continuous preference top- k queries2012
- Algorithms for distributed functional monitoringACM Transactions on Algorithms, 2011
- High-performance complex event processing over streams2006
- I/O-efficient dynamic planar point locationComputational Geometry, 2004
- A denotational semantics for continuous queries over streams and relationsACM SIGMOD Record, 2004
- Aurora: a new model and architecture for data stream managementThe VLDB Journal, 2003
- Continuously adaptive continuous queries over streams2002
- Active database systemsACM Computing Surveys, 1999
- R-trees1984