ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Algorithms for Querying by Spatial Structure.

Dimitris Papadias, Nikos Mamoulis, Vasilis Delis: Algorithms for Querying by Spatial Structure. VLDB 1998: 546-557
@inproceedings{DBLP:conf/vldb/PapadiasMD98,
  author    = {Dimitris Papadias and
               Nikos Mamoulis and
               Vasilis Delis},
  editor    = {Ashish Gupta and
               Oded Shmueli and
               Jennifer Widom},
  title     = {Algorithms for Querying by Spatial Structure},
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
               USA},
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {546-557},
  ee        = {db/conf/vldb/PapadiasMD98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Structural queries constitute a special form of content-based retrieval where the user specifies a set of spatial constraints among query variables and asks for all configurations of actual objects that (totally or partially) match these constraints. Processing such queries can be thought of as a general form of spatial joins, i.e., instead of pairs, the result consists of n-tuples of objects, where n is the number of query variables. In this paper we describe a flexible framework which permits the representation of configurations in different resolution levels and supports the automatic derivation of similarity measures. We subsequently propose three algorithms for structural query processing which integrate constraint satisfaction with spatial indexing (R-trees). For each algorithm we apply several optimization techniques and experimentally evaluate performance using real data.

Copyright © 1998 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD DiSC

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

ACM SIGMOD Anthology

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

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[A83]
James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11): 832-843(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BG95]
Fahiem Bacchus, Adam J. Grove: On the Forward Checking Algorithm. CP 1995: 292-308 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BB84]
...
[BKSS90]
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BKS93]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BKSS94]
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BKS96]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BvR95]
Fahiem Bacchus, Paul van Run: Dynamic Variable Ordering in CSPs. CP 1995: 258-275 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DPM98]
...
[F92]
Christian Freksa: Temporal Reasoning Based on Semi-Intervals. Artif. Intell. 54(1): 199-227(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GR95]
Venkat N. Gudivada, Vijay V. Raghavan: Design and Evaluation of Algorithms for Image Retrieval by Spatial Similarity. ACM Trans. Inf. Syst. 13(2): 115-144(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[G93]
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[G84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HE80]
Robert M. Haralick, Gordon L. Elliott: Increasing Tree Search Efficiency for Constraint Satisfaction Problems. Artif. Intell. 14(3): 263-313(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HJR97]
Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[M98]
...
[NNS96]
Mohammad Nabil, Anne H. H. Ngu, John Shepherd: Picture Similarity Retrieval Using 2D Projection Interval Representation. IEEE Trans. Knowl. Data Eng. 8(4): 533-539(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[N89]
...
[O86]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PS94]
Dimitris Papadias, Timos K. Sellis: Qualitative Representation of Spatial Knowledge in Two-Dimensional Space. VLDB J. 3(4): 479-516(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PTSE95]
Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis, Max J. Egenhofer: Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees. SIGMOD Conference 1995: 92-103 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PF97]
Euripides G. M. Petrakis, Christos Faloutsos: Similarity Searching in Medical Image Databases. IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PS88]
...
[R91]
Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RKV95]
Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[T94]
...

Copyright © Tue Mar 16 02:22:07 2010 by Michael Ley (ley@uni-trier.de)