Algorithms for Querying by Spatial Structure.

Dimitris Papadias, Nikos Mamoulis, Vasilis Delis: Algorithms for Querying by Spatial Structure. VLDB 1998: 546-557
  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,
  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,}


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


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

ACM SIGMOD Anthology

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

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 BibTeX


James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11): 832-843(1983) BibTeX
Fahiem Bacchus, Adam J. Grove: On the Forward Checking Algorithm. CP 1995: 292-308 BibTeX
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 BibTeX
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 BibTeX
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208 BibTeX
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265 BibTeX
Fahiem Bacchus, Paul van Run: Dynamic Variable Ordering in CSPs. CP 1995: 258-275 BibTeX
Christian Freksa: Temporal Reasoning Based on Semi-Intervals. Artif. Intell. 54(1): 199-227(1992) BibTeX
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) BibTeX
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Robert M. Haralick, Gordon L. Elliott: Increasing Tree Search Efficiency for Constraint Satisfaction Problems. Artif. Intell. 14(3): 263-313(1980) BibTeX
Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405 BibTeX
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) BibTeX
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
Dimitris Papadias, Timos K. Sellis: Qualitative Representation of Spatial Knowledge in Two-Dimensional Space. VLDB J. 3(4): 479-516(1994) BibTeX
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 BibTeX
Euripides G. M. Petrakis, Christos Faloutsos: Similarity Searching in Medical Image Databases. IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997) BibTeX
Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 BibTeX
Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79 BibTeX

Referenced by

  1. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
  2. Dimitris Papadias, Nikos Mamoulis, Yannis Theodoridis: Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999: 44-55
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:23 2009