Spatio-temporal histograms

Hicham G. Elmongui, Mohamed F. Mokbel, Walid G. Aref

Research output: Contribution to journalConference articlepeer-review

9 Scopus citations


This paper presents a framework for building and continuously maintaining spatio-temporal histograms (ST-Histograms, for short). ST-Histograms are used for selectivity estimation of continuous pipelined query operators. Unlike traditional histograms that examine and/or sample all incoming data tuples, ST-Histograms are built by monitoring the actual selectivities of the outstanding continuous queries. ST-Histograms have three main features: (1) The ST-Histograms are built with (almost) no overhead to the system. We use only feedback (i.e., the actual selectivity) from the existing continuous queries. (2) Rather than wasting system resources in maintaining accurate histograms for the whole spatial space, we only maintain accurate histograms for that part of the space that is relevant to the current existing queries. The rest of the space has less accurate histograms. (3) The ST-Histograms are equipped with a periodicity detection procedure that predicts the future execution of the continuous queries. Hence, the query processing engine can continuously adapt the continuous query pipeline to reflect this prediction. Experimental results based on a real implementation inside a data stream management system show a superior performance of ST-Histograms in terms of providing accurate operator selectivity estimations with no extra overhead.

Original languageEnglish (US)
Pages (from-to)19-36
Number of pages18
JournalLecture Notes in Computer Science
StatePublished - 2005
Event9th International Symposium on Spatial and Temporal Databases, SSTD 2005 - Angra dos Reis, Brazil
Duration: Aug 22 2005Aug 24 2005


Dive into the research topics of 'Spatio-temporal histograms'. Together they form a unique fingerprint.

Cite this