SINA: Scalable incremental processing of continuous queries in spatio-temporal databases

Mohamed F. Mokbel, Xiaopeng Xiong, Walid G. Aref

Research output: Contribution to journalConference articlepeer-review

318 Scopus citations


This paper introduces the Scalable INcremental hash-based Algorithm (SINA, for short); a new algorithm for evaluating a set of concurrent continuous spatio-temporal queries. SINA is designed with two goals in mind: (1) Scalability in terms of the number of concurrent continuous spatio-temporal queries, and (2) Incremental evaluation of continuous spatio-temporal queries. SINA achieves scalability by employing a shared execution paradigm where the execution of continuous spatio-temporal queries is abstracted as a spatial join between a set of moving objects and a set of moving queries. Incremental evaluation is achieved by computing only the updates of the previously reported answer. We introduce two types of updates, namely positive and negative updates. Positive or negative updates indicate that a certain object should be added to or removed from the previously reported answer, respectively. SINA manages the computation of positive and negative updates via three phases: the hashing phase, the invalidation phase, and the joining phase. The hashing phase employs an in-memory hash-based join algorithm that results in a set of positive updates. The invalidation phase is triggered every T seconds or when the memory is fully occupied to produce a set of negative updates. Finally, the joining phase is triggered by the end of the invalidation phase to produce a set of both positive and negative updates that result from joining in-memory data with in-disk data. Experimental results show that SINA is scalable and is more efficient than other index-based spatio-temporal algorithms.

Original languageEnglish (US)
Pages (from-to)623-634
Number of pages12
JournalProceedings of the ACM SIGMOD International Conference on Management of Data
StatePublished - Jul 27 2004
EventProceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2004 - Paris, France
Duration: Jun 13 2004Jun 18 2004


Dive into the research topics of 'SINA: Scalable incremental processing of continuous queries in spatio-temporal databases'. Together they form a unique fingerprint.

Cite this