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
Type
Article accepté pour publication ou publiéDate
2003Journal name
Computer JournalVolume
46Number
6Publisher
Oxford University Press
Pages
664-679
Publication identifier
Metadata
Show full item recordAbstract (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 / Keywords
Geometric data; Spatial dataRelated items
Showing items related by title and author.
-
Rigaux, Philippe; Scholl, Michel; Ségoufin, Luc; Grumbach, Stéphane (2003) Article accepté pour publication ou publié
-
Guéhis, Sonia; Rigaux, Philippe; Thion-Goasdoué, Virginie (2009) Communication / Conférence
-
Guéhis, Sonia; Rigaux, Philippe; Waller, Emmanuel (2006) Communication / Conférence
-
Litwin, Witold; Mokadem, Riad; Rigaux, Philippe; Schwartz, Thomas (2007) Communication / Conférence
-
Rigaux, Philippe; Litwin, Witold; du Mouza, Cédric (2009) Article accepté pour publication ou publié