Capturing the Uncertainty of Moving-Object Representations

Dieter Pfoser, Christian S. JensenSSD 1999 · DOI

TL;DR

This paper tackles the challenge of representing and querying moving objects in databases, acknowledging that real-world data from sources like GPS is inherently uncertain. They propose a novel database schema and query processing approach that explicitly models and utilizes this uncertainty, enabling more robust and accurate retrieval of moving object data.

What Problem Does This Paper Address?

Managing and querying data about objects that move continuously (like vehicles or aircraft) is a growing area of interest for spatiotemporal databases. A key challenge is that the positions of these objects are typically not known continuously but are sampled at discrete intervals using technologies like GPS. This sampling, along with the interpolation needed to estimate positions between samples, introduces uncertainty into the data. Existing methods often overlook or inadequately handle this uncertainty, leading to potential inaccuracies in query results. This paper aims to address this gap by developing a representation and query processing framework that explicitly accounts for and leverages this inherent uncertainty.

Methods

The paper proposes a multi-faceted approach:

  • Representation: They represent the movement of objects as polylines, where each segment connects two sampled positions. Crucially, they introduce a mechanism to capture uncertainty associated with these representations.
  • Uncertainty Quantification: They model two primary sources of uncertainty:
  • Measurement Error: The inherent inaccuracy of the measurement device (e.g., GPS). They assume a circular Gaussian distribution for this error.
  • Sampling Error: The uncertainty introduced by interpolating between sampled points. They develop models for this, including a "worst-case sampling error" which assumes the object travels at its maximum speed. This error is represented by an "error ellipse" or a circle in the worst-case scenario.
  • Database Schema: A relational database schema is proposed to store object information, their trajectories (as line segments), and the associated error parameters.
  • Query Processing: They adapt the standard "filter-and-refine" approach for spatial queries.
  • Filter Step: This step uses an "expansion measure" derived from the query's probability requirement and the worst-case sampling error. The query window is expanded to ensure that all potentially qualifying objects are included.
  • Refinement Step: This step uses the more precise, position-specific sampling error to accurately determine which positions within the filtered segments truly meet the query's probability criteria.

Datasets

Not discussed in the paper. The paper uses a hypothetical taxi company scenario for illustrative examples.

Key Insights and Ideas

  • Uncertainty is Fundamental: The paper strongly emphasizes that ignoring uncertainty in moving object data leads to flawed results. It's not an edge case but a core aspect of the problem.
  • Sampling Error Dominates: For applications like fleet management with current GPS technology, the error introduced by sampling and interpolation is significantly larger than the measurement error itself. This justifies focusing on sampling error.
  • Worst-Case vs. Specific Error: The distinction between a global "worst-case sampling error" (useful for filtering) and position-specific sampling errors (needed for accurate refinement) is a key practical insight.
  • Query Window Expansion: The concept of "expansion measure" to adjust query windows based on probability requirements and error distributions is a clever way to adapt existing spatial query techniques.
  • Handling Small Query Windows: The paper addresses the tricky case of small query windows, proposing a strategy to avoid prematurely discarding valid results by ensuring a minimum window size related to the error.

Key Results

The paper demonstrates how their proposed database schema and query processing method can be used to answer queries involving positional uncertainty. For example, they show how to answer queries like "Retrieve taxis within area A between times B and C with at least X% probability." While specific quantitative results (e.g., percentage speedup or accuracy improvement) are not presented as empirical benchmarks, the paper provides a theoretical framework and algorithmic approach that logically addresses the problem of uncertain moving object data.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Linear Interpolation: They used linear interpolation for trajectories, suggesting that more advanced techniques like polynomial splines could be explored.
  • Error Measures: The work focused on measurement and sampling errors. Other error sources, such as those introduced by data manipulation before storage, could be incorporated.
  • Temporal Uncertainty: The current model primarily addresses spatial uncertainty. Future work could explore quantifying and handling temporal uncertainty, especially if motion sensors other than GPS are used.
  • Infrastructure Constraints: The current model assumes objects can move freely in space. Incorporating real-world infrastructure (roads, buildings, terrain) could lead to more accurate uncertainty estimates and improved query results.

Summary updated

BibTeX
@inproceedings{pfoser1999capturing,
  author = {Dieter Pfoser and Christian S. Jensen},
  title = {{Capturing the Uncertainty of Moving-Object Representations}},
  booktitle = {SSD},
  year = {1999},
  doi = {10.1007/3-540-48482-5\_9},
}
Figure