Representing uncertainty in spatial and spatiotemporal databases

Abstract

The theme of this thesis is uncertainty in spatial and spatiotemporal databases. Due to lack of accurate measurements, or rapid changes in time, spatial and spatiotemporal data are often uncertain. This thesis presents new abstract and discrete models for uncertain spatial and spatiotemporal information. The models are based on the principle that one knows that the uncertain object, regardless of type, must be within a certain area.

The first part of this thesis concerns an abstract model. To this author’sknowledge, this is the first attempt to create a general type system for uncertainty with spatial data. Individual uncertain types have been modelled before, but no work has studied points, lines and regions and used the same principles to model all three. It also seems to be the first model to handle temporal as well as spatial uncertainty. This thesis contains mathematical definitions of uncertain points, lines, regions and temporal versions of these. The thesis also contains definitions of relevant operations on these types. These operations are also evaluated for their usefulness with regard to uncertain data.

The second part of this thesis concerns three discrete models which are all based on the abstract model mentioned earlier. One of these is an advanced model that manages to model almost all of the aspects of the abstract model, but at the cost of increased need for storage space. It is also difficult to compute probabilities in a consistent manner for this model.The second model is of medium complexity, and balances storage use and modelling power. It also has the advantage that computing probabilities in a consistent manner is much easier than for the advanced model. The third model is an attempt to bring the storage space needed as low as possible. It therefore has somewhat limited modelling power. Unlike the two other discrete models, it cannot be extended to handle spatiotemporal data.

The handling of uncertain spatiotemporal data is based on how crisp spatiotemporal data are handled in [GBE+00] and [FGNS00]. This thesis makes two important additions to these models so that they can handle uncertain data. First, it presents ways of generating a sliced representation when the times the snapshots were taken are uncertain. Second, it details how operations change as a result of uncertainty. The Initial and Final operations exemplify this as in the crisp case they return the initial and final shapes of an object, but they cannot be defined in the uncertain case. This thesis discusses how these operations can be replaced in the uncertain case.