Approximation Techniques for Indexing Constraint Databases
Elisa Bertino, Barbara Catania, Boris Chidlovskii
Constraint databases have recently been proposed as a powerful framework to model and retrieve spatial data.
The use of constraint databases should be supported by access data structures that make effective use of
secondary storage and reduce query processing time. In this paper, we consider the indexing problem for
objects represented by conjunctions of two-variable linear constraints and we analyze the problem of
determining all generalized tuples whose extension intersects or is contained in the extension of a given
half-plane. Previously, we have shown that both selection problems can be reduced to a point location problem
by using a dual transformation. If the angular coefficient of the half-plane belongs to a predefined set, we have
proved that a dynamic optimal indexing solution, based on B+-trees, exists. In this paper we propose two
approximation techniques that can be used to find the result when the angular coefficient does not belong to
the predefined set. We also experimentally compare the proposed techniques with R-trees.
Proc. 6th Intern. Database Systems for Advanced Applications(DASFAA)'99 Conf., Hsinchu, Taiwan, ROC
dasfaa99.ps.gz (45.24 kB)