Qualitative Representation of Spatial Knowledge in Two-Dimensional Space.

Dimitris Papadias, Timos K. Sellis: Qualitative Representation of Spatial Knowledge in Two-Dimensional Space. VLDB J. 3(4): 479-516(1994)
  author    = {Dimitris Papadias and
               Timos K. Sellis},
  title     = {Qualitative Representation of Spatial Knowledge in Two-Dimensional
  journal   = {VLDB J.},
  volume    = {3},
  number    = {4},
  year      = {1994},
  pages     = {479-516},
  ee        = {db/journals/vldb/PapadiasS94.html},
  bibsource = {DBLP,}


Various relation-based systems, concerned with the qualitative representation and processing of spatial knowledge, have been developed in numerous application domains. In this article, we identify the common concepts underlying qualitative spatial knowledge representation, we compare the representational properties of the different systems, and we outline the computational tasks involved in relation-based structures that combine several ideas in spatial knowledge representation. A symbolic spatial index is an array that preserves only a set of spatial relations among distinct objects in an image, called the modeling space; the index array discards information, such as shape and size of objects, and irrelevant spatial relations. The construction of a spatial index from an input image can be thought of as a transformation that keeps only a set of representative points needed to define the relations of the modeling space. By keeping the relative arrangements of the representative points in symbolic spatial indexes and discarding all other points, we maintain enough information to answer queries regarding the spatial relations of the modeling space without the need to access the initial image or an object database. Symbolic spatial indexes can be used to solve problems involving route planning, composition of spatial relations, and update operations.

Copyright © 1994 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.

Key Words

Spatial data models, spatial query languages, representation of direction and topological relations, qualitative spatial information processing.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


[Allen 1983]
James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11): 832-843(1983) BibTeX
[Bruegger & Muller 1992]
[Buisson 1989]
Laurent Biusson: Reasoning on Space with Object-Centered Knowledge Representations. SSD 1989: 325-344 BibTeX
[Chang & Fu 1980]
Ning-San Chang, King-sun Fu: Query-by-Pictorial-Example. IEEE Trans. Software Eng. 6(6): 519-524(1980) BibTeX
[Chang et al. 1987]
[Chang et al. 1988]
Shi-Kuo Chang, C. W. Yan, Donald C. Dimitroff, Timothy Arndt: An Intelligent Image Database System. IEEE Trans. Software Eng. 14(5): 681-688(1988) BibTeX
[Chang et al. 1989]
Shi-Kuo Chang, Erland Jungert, Y. Li: The Design of Pictorial Databases Based Upon the Theory of Symbolic Projections. SSD 1989: 303-323 BibTeX
[Clementini et al. ]
[Davis 1986]
[Dutta 1989]
Soumitra Dutta: Qualitative Spatial Reasoning: A Semi-quantitative Approach Using Fuzzy Logic. SSD 1989: 345-364 BibTeX
[Egenhofer 1991]
Max J. Egenhofer: Reasoning about Binary Topological Relations. SSD 1991: 143-160 BibTeX
[Egenhofer & Herring 1990]
[Egenhofer & Sharma 1993]
[Frank 1992]
[Frank 1994]
[Freksa 1991]
[Freksa 1992]
[Glasgow & Papadias 1992]
[Glasgow et al. 1992]
[Güsgen 1989]
[Hernàndez 1993]
Daniel Hernández: Maintaining Qualitative Spatial Knowledge. COSIT 1993: 36-53 BibTeX
[Herskovits 1986]
[Holmes & Jungert 1992]
[Jackendoff 1983]
[Kainz et al. 1993]
[Kuipers 1978]
[Larkin & Simon 1987]
[Lee et al. 1992]
[Levine 1978]
[Lindsay 1988]
[Mark 1992]
[McDermott & Davis 1984]
Drew V. McDermott, Ernest Davis: Planning Routes Through Uncertain Territory. Artif. Intell. 22(2): 107-156(1984) BibTeX
[Mukerjee & Joe 1990]
Amitabha Mukerjee, Gene Joe: A Qualitative Model for Space. AAAI 1990: 721-727 BibTeX
[Papadias 1994]
[Papadias & Glasgow 1991]
[Papadias & Sellis 1992]
[Papadias & Sellis 1993]
Dimitris Papadias, Timos K. Sellis: The Semantics of Relations in 2D Space Using Representative Points: Spatial Indexes. COSIT 1993: 234-247 BibTeX
[Papadias & Sellis 1994]
[Papadias et al. 1994a]
Dimitris Papadias, Andrew U. Frank, Manolis Koubarakis: Constraint-Based Reasoning in Geographic Databases: the Case of Symbolic Arrays. Workshop on Deductive Databases and Logic Programming 1994: 159-171 BibTeX
[Papadias et al. 1994b]
Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis: The Retrieval of Direction Relations using R-trees. DEXA 1994: 173-182 BibTeX
[Peuquet 1986]
[Peuquet & Ci-Xiang 1987]
[Pullar & Egenhofer 1988]
[Randell et al. 1992]
David A. Randell, Zhan Cui, Anthony G. Cohn: A Spatial Logic based on Regions and Connection. KR 1992: 165-176 BibTeX
[Requicha 1980]
Aristides A. G. Requicha: Representations for Rigid Solids: Theory, Methods, and Systems. ACM Comput. Surv. 12(4): 437-464(1980) BibTeX
[Roussopoulos et al. 1988]
Nick Roussopoulos, Christos Faloutsos, Timos K. Sellis: An Efficient Pictorial Database System for PSQL. IEEE Trans. Software Eng. 14(5): 639-650(1988) BibTeX
[Sistla et al. 1994]
A. Prasad Sistla, Clement T. Yu, R. Haddad: Reasoning About Spatial Relationships in Picture Retrieval Systems. VLDB 1994: 570-581 BibTeX
[Smith & Park 1992]
[Ullman 1988]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Vieu 1993]
Laure Vieu: A Logical Framework for Reasoning about Space. COSIT 1993: 25-35 BibTeX

Referenced by

  1. Eliseo Clementini, Paolino Di Felice: Spatial Operators. SIGMOD Record 29(3): 31-38(2000)
  2. Dimitris Papadias, Nikos Mamoulis, Vasilis Delis: Algorithms for Querying by Spatial Structure. VLDB 1998: 546-557
  3. Glaucia Faria, Claudia Bauzer Medeiros, Mario A. Nascimento: An Extensible Framework for Spatio-Temporal Database Applications. SSDBM 1998: 202-205
  4. Toshiyuki Amagasa, Masayoshi Aritsugi, Takayuki Tanaka, Yoshinari Kanamori: Implementing Class Library and Index for Managing Spatio-Temporal Data. ER Workshops 1998: 532-541
  5. Thodoros Topaloglou, John Mylopoulos: Representing Partial Spatial Information in Databases. ER 1996: 325-340
  6. 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
  7. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:22 2009