ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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}
}
BibTeX

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.

Copyright © 1999 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD DiSC

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

ACM SIGMOD Anthology

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

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 BibTeX
[2]
Lars Arge, Jeffrey Scott Vitter: Optimal Dynamic Interval Management in External Memory (extended abstract). FOCS 1996: 560-569 BibTeX
[3]
Alberto Belussi, Elisa Bertino, Barbara Catania: Manipulating Spatial Data in Constraint Databases. SSD 1997: 115-141 BibTeX
[4]
Elisa Bertino, Barbara Catania, Boris Shidlovsky: Towards Optimal Two-Dimensional Indexing for Constraint Databases. Inf. Process. Lett. 64(1): 1-8(1997) BibTeX
[5]
Alexander Brodsky, Catherine Lassez: Separability of Polyhedra and a New Approach to Spatial Storage (Extended Abstract). PPCP 1993: 7-11 BibTeX
[6]
...
[7]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[8]
...
[9]
Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, Jeffrey Scott Vitter: External-Memory Computational Geometry (Preliminary Version). FOCS 1993: 714-723 BibTeX
[10]
Oliver Günther: Efficient Structures for Geometric Data Management. Lecture Notes in Computer Science Vol. 337 Springer 1988, ISBN 3-540-50463-X
BibTeX
[11]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[12]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX
[13]
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX
[14]
...
[15]
Franco P. Preparata, Michael Ian Shamos: Computational Geometry - An Introduction. Springer 1985, ISBN 3-540-96131-3
BibTeX
[16]
Sridhar Ramaswamy: Efficient Indexing for Constraint and Temporal Databases. ICDT 1997: 419-431 BibTeX
[17]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[18]
...
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
DASFAA 1999 Proceedings: Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:05:38 2009