Approximate Query Evaluation Using Linear Constraint Databases

This paper shows that constraint databases can be used for the approximation of several types of discretely recorded continuous data, for example time series data and some spatio-temporal geographic data. We show that time series data can be approximated by a piecewise linear approximation that runs in linear time in the number of data points, and the piecewise linear approximation can be represented in a linear constraint database. Similarly, the spatio-temporal geographic data that is composed of a set of spatial locations, where each location is associated with a time series, can be also approximated and represented in a linear constraint database. The approximations provide data compression, faster query evaluation-that preserve high precision and recall-and interpolation enabling the evaluation of queries that could not be evaluated before.

Authors

• Peter Z. Revesz
• Rui Chen
• Min Ouyang

Keywords

• Query processing
• Piecewise linear approximation
• Temperature
• Interpolation
• Piecewise linear techniques
• Spatial databases
• Data compression
• Computer science
• Data engineering
• Time measurement
• Linear Constraints
• Query Evaluation
• Approximate Query
• Time Series
• Source Code
• Time Series Data
• Linear Approximation
• Number Of Data Points
• Local Setting
• Linear Time
• Geographic Data
• Spatiotemporal Data
• Linear Function
• Weather Station
• Estimation Algorithm
• Precision And Recall
• Time Instants
• Original Point
• Head And Tail
• Piecewise Linear Function
• Sequence Of Points
• Voronoi Diagram
• Error Tolerance
• SQL Queries
• Linear Algorithm
• Original Time Series