This paper proposes a framework for the handling of spatio-temporal queries with inexact matches, using the concept of relation similarity. We initially describe a binary string encoding for 1D relations that permits the automatic derivation of similarity measures. We then extend this model to various granularity levels and many dimensions, and show that reasoning on spatio-temporal structure is significantly facilitated in the new framework. Finally, we provide algorithms and optimization methods for four types of queries: (i) object retrieval based on some spatio-temporal relations with respect to a reference object, (ii) spatial joins, i.e., retrieval of object pairs that satisfy some input relation, (iii) structural queries, which retrieve configurations matching a particular spatio-temporal structure, and (iv) special cases of motion queries. Considering the current large availability of multidimensional data and the increasing need for flexible query-answering mechanisms, our techniques can be used as the core of spatio-temporal query processors.

The paper is concerned with the qualitative representation of spatiotemporal relations. We initially propose a multiresolution framework for the representation of relations among 1D intervals, based on a binary string encoding. We subsequently extend this framework to multiple dimensions, thus allowing the description of spatiotemporal relations at various contexts. The feasible relations at a particular resolution level are inherently permeated by a poset structure, called conceptual neighbourhood, upon which we propose efficient relation inferencing mechanisms. Finally, we discuss the application of our model to spatiotemporal reasoning, which refers to the classic problems of satisfiability and deductive closure of a set of spatiotemporal assertions.

In ttis paper we addrms the issue of s@uctural JIzdiIIzcdia siIzzZari@, mhlch is based on the re~ations between the individud objects that comprise a rnuItimedla documenti We propose a binary string encoding for lD relations which permits the automatic derivation of similarity measur~.T1'ethen etiend it to various r~oIution levels and many dimensions and show that reasoning on spatiotempord structure is si=wificantly facilitated in the new framework by applying it to multimedia presentation and motion similarity. Ke~words hlultimedia Stiarity, StiarityQueries, Spatiotempod Relations Permission to make digital or hard copies of all or part of this work for