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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 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/Disc99_1 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

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

References

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