Spatio-temporal aggregation using sketches

This work proposes a novel way of integrating spatio-temporal indexes with sketches, traditionally used for approximate query processing, to solve the distinct counting problem of summarized information about moving objects that lie in a query region during a query interval.

Abstract

Several spatio-temporal applications require the retrieval of summarized information about moving objects that lie in a query region during a query interval (e.g., the number of mobile users covered by a cell, traffic volume in a district, etc.). Existing solutions have the distinct counting problem: if an object remains in the query region for several timestamps during the query interval, it will be counted multiple times in the result. We solve this problem by integrating spatio-temporal indexes with sketches, traditionally used for approximate query processing. The proposed techniques can also be applied to reduce the space requirements of conventional spatio-temporal data and to mine spatio-temporal association rules.