Handling Interpolated Data
Ségoufin, Luc; Rigaux, Philippe; Grumbach, Stéphane (2003), Handling Interpolated Data, Computer Journal, 46, 6, p. 664-679. http://dx.doi.org/10.1093/comjnl/46.6.664
TypeArticle accepté pour publication ou publié
Journal nameComputer Journal
Oxford University Press
MetadataShow full item record
Abstract (EN)This paper addresses fundamental issues related to the modeling of geometric data embedded in high-dimensional spaces. This covers several application fields, including moving objects where trajectories are described in a three- or four-dimensional space, and digital elevation models (DEMs). We show that moving objects and DEMs are specific instances of a broader class of complex spatial data that require the interpolation of values from collections of samples. We propose to model such data conceptually using infinite relations (e.g. the trajectory of a moving point yields an infinite ternary relation) which can be manipulated through standard relational query languages (e.g. SQL), with no mention of the interpolated definition. This approach is simple and establishes a clear separation between logical and physical levels. It permits the expression of queries on spatio-temporal databases in a purely declarative way. Next, we investigate algorithms for evaluating queries on interpolated data. In the general cases, the cost of manipulating $d$-dimensional data is exponential in $d$. We describe how to use rewriting and optimization techniques in order to evaluate queries with a small set of algorithms running in dimension 2, thus making the complexity independent from the global dimension.
Subjects / KeywordsGeometric data; Spatial data
Showing items related by title and author.
Rigaux, Philippe; Scholl, Michel; Ségoufin, Luc; Grumbach, Stéphane (2003) Article accepté pour publication ou publié