|
|
|
 |
|
 |
|
Approximation Techniques for Indexing Two-Dimensional Constraint Databases
|
Elisa Bertino,
Barbara Catania, and
Boris Chidlovskii
View Paper (PDF)
Return to Session 4B: Index Techniques
Constraint databases have recently been proposed
as a powerfulframework 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. In [4], we have shown that both selection problems can be reduced
to a point location problem by using a dual transformation 14, IO]. If the
angular coefJicient of the half-plane belongs to a predejned set, we have
proved that a dynamic optimal indexing solution, based on Bf -trees, exists. In
this paper we propose two approximation techniques that can be used to3nd the
result when the angular coefficient does not belong to the predefined set. We
also experimentally compare the proposed techniques with R-trees.
Copyright(C) 2000 ACM
|
|
|
|
|
|
|
