Optimization
[ Back ] [ Home ] [ Next ]

Constraints as Data
Potential Apps
Query by Example
Query by Example
Query by Example
More Examples
Model and Language
Main Features
Hosting Iterative Lang.
Constraint Calculus
Constraint Calculus
Polynomial Complexity
Query Evaluation
Functionality
Optimization
Optimization
Optimization
Optimization
Implemented Apps
Implemented Apps

Optimization by Approximation-based Filtering and Indexing

Inverse, approximation and indexed approximation groupings are indexing mechanisms in CCUBE, which we briefly exemplify below. They allow to use "regular" index structures, such as B- and R-trees, in the presence of nested collections and approximations. These structures are used, in particular, for indexing complex disjunctive and conjunctive constraints.

To understand the idea, consider the query "find all trajectories passing over the Fairfax county". It will be assumed here that a set of 4D aircraft trajectories as well as a map is stored in the database. We assume here that each trajectory has a piece-wise linear form, i.e., it is represented as a DC_LIN CST object.

where x,y,z are variables for a location, t is a time variable, and t_i-1, a_i,1,b_i,1,a_i,2, b_i,2,a_i,3,b_i,3, 1 £ i £ n, are constants. Note that for each i, the C_LIN constraint (t_i-1 £ t < t_i Ùx = a_i,1 t + b_i,1 Ùy = a_i,2 t + b_i,2 Ùz = a_i,3 t + b_i,3) describes the movement equations for the time interval [t_i-1,t_i), for the constant 3-D velocity vector (a_i,1,a_i,2,a_i,3), starting from the point (b_i,1,b_i,2,b_i,3).

presentation created by Victor E. Segal