Approximation Techniques for Indexing Two-Dimensional Constraint Databases.

Elisa Bertino, Barbara Catania, Boris Chidlovskii: Approximation Techniques for Indexing Two-Dimensional Constraint Databases. DASFAA 1999: 213-220

@inproceedings{DBLP:conf/dasfaa/BertinoCC99,
  author    = {Elisa Bertino and
               Barbara Catania and
               Boris Chidlovskii},
  editor    = {Arbee L. P. Chen and
               Frederick H. Lochovsky},
  title     = {Approximation Techniques for Indexing Two-Dimensional Constraint
               Databases},
  booktitle = {Database Systems for Advanced Applications, Proceedings of the
               Sixth International Conference on Database Systems for Advanced
               Applications (DASFAA), April 19-21, Hsinchu, Taiwan},
  publisher = {IEEE Computer Society},
  year      = {1999},
  isbn      = {0-7695-0084-6},
  pages     = {213-220},
  ee        = {db/conf/dasfaa/BertinoCC99.html},
  crossref  = {DBLP:conf/dasfaa/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 2 Number 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Online Edition: IEEE Computer Society Digital Library

Citation Page

References

[1]: Lars Arge, Darren Erik Vengroff, Jeffrey Scott Vitter: External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (Extended Abstract). ESA 1995: 295-310
[2]: Lars Arge, Jeffrey Scott Vitter: Optimal Dynamic Interval Management in External Memory (extended abstract). FOCS 1996: 560-569
[3]: Alberto Belussi, Elisa Bertino, Barbara Catania: Manipulating Spatial Data in Constraint Databases. SSD 1997: 115-141
[4]: Elisa Bertino, Barbara Catania, Boris Shidlovsky: Towards Optimal Two-Dimensional Indexing for Constraint Databases. Inf. Process. Lett. 64(1): 1-8(1997)
[5]: Alexander Brodsky, Catherine Lassez: Separability of Polyhedra and a New Approach to Spatial Storage (Extended Abstract). PPCP 1993: 7-11
[6]: ...
[7]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[8]: ...
[9]: Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, Jeffrey Scott Vitter: External-Memory Computational Geometry (Preliminary Version). FOCS 1993: 714-723
[10]: Oliver Günther: Efficient Structures for Geometric Data Management. Lecture Notes in Computer Science Vol. 337 Springer 1988, ISBN 3-540-50463-X
[11]: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
[12]: Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995)
[13]: Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243
[14]: ...
[15]: Franco P. Preparata, Michael Ian Shamos: Computational Geometry - An Introduction. Springer 1985, ISBN 3-540-96131-3
[16]: Sridhar Ramaswamy: Efficient Indexing for Constraint and Temporal Databases. ICDT 1997: 419-431
[17]: Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518
[18]: ...