• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2003
Journal name
Computer Journal
Volume
46
Number
6
Publisher
Oxford University Press
Pages
664-679
Publication identifier
http://dx.doi.org/10.1093/comjnl/46.6.664
Metadata
Show full item record
Author(s)
Ségoufin, Luc
Rigaux, Philippe cc
Grumbach, Stéphane
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 / Keywords
Geometric data; Spatial data

Related items

Showing items related by title and author.

  • Thumbnail
    Building a constraint-based spatial database system: model, languages, and implementation 
    Rigaux, Philippe; Scholl, Michel; Ségoufin, Luc; Grumbach, Stéphane (2003) Article accepté pour publication ou publié
  • Thumbnail
    Speeding-Up Data-Driven Applications with Program Summaries 
    Guéhis, Sonia; Rigaux, Philippe; Thion-Goasdoué, Virginie (2009) Communication / Conférence
  • Thumbnail
    Data-Driven Publication of Relational Databases 
    Guéhis, Sonia; Rigaux, Philippe; Waller, Emmanuel (2006) Communication / Conférence
  • Thumbnail
    Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures 
    Litwin, Witold; Mokadem, Riad; Rigaux, Philippe; Schwartz, Thomas (2007) Communication / Conférence
  • Thumbnail
    Large-scale indexing of spatial data in distributed repositories: the SD-Rtree 
    Rigaux, Philippe; Litwin, Witold; du Mouza, Cédric (2009) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo