Binary string relations: a foundation for spatiotemporal knowledge representation

ABSTRACT

The paper is concerned with the qualitative representation of spatiotemporal relations. We initially propose a multiresolution framework for the representation of relations among 1D intervals, based on a binary string encoding. We subsequently extend this framework to multiple dimensions, thus allowing the description of spatiotemporal relations at various contexts. The feasible relations at a particular resolution level are inherently permeated by a poset structure, called conceptual neighbourhood, upon which we propose efficient relation inferencing mechanisms. Finally, we discuss the application of our model to spatiotemporal reasoning, which refers to the classic problems of satisfiability and deductive closure of a set of spatiotemporal assertions.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: James F. Allen, Towards a general theory of action and time, Artificial Intelligence, v.23 n.2, p.123-154, July 1984 [doi>10.1016/0004-3702(84)90008-0 ]
• 3: Allen, J., "Time and time again: The many ways to represent time," International Journal of Intelligent Systems, 6(4), 1991.
• 4: Dana Harry Ballard , Christopher M. Brown, Computer Vision, Prentice Hall Professional Technical Reference, 1982
• 5: Bruns, T.H., Egenhofer, M.J., "Similarity of Spatial Scenes", 7~h International Symposium on Spatial Data Handling, 1996.
• 6: Chvatal, V., "Linear Programming", W. H. Freeman.
• 7: S. K. Chang , Q. Y. Shi , C. W. Yan, Iconic indexing by 2-D strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.3, p.413-428, May 1987
• 8: Egenhofer, M.J., "Spatial Relations: Models and Inferences", Tutorial 2, International Symposium on Large Spatial databases (SSD'97), 1997.
• 9: Egenhofer, M.J., Herring, J., "Categorizing Binary Topological Relationships Between Regions, Lines and Points in Geographic Databases", Technical Report, Department of Surveying Engineering, University of Maine, Orono, ME, 1991.
• 10: Frank, A., "Qualitative Spatial Reasoning about Distances and Directions in Geographic Space", Journal of Visual Languages and Computing, 3(4), 1992.
• 11: Eugene C. Freuder, Synthesizing constraint expressions, Communications of the ACM, v.21 n.11, p.958-966, Nov. 1978 [doi>10.1145/359642.359654]
• 12: Freksa, C., "Conceptual Neighbourhood and its Role in Temporal and Spatial Reasoning", IMACS Workshop on Decision Support Systems and Qualitative Reasoning, 1991.
• 13: Christian Freksa, Temporal reasoning based on semi-intervals, Artificial Intelligence, v.54 n.1-2, p.199-227, March 1992 [doi>10.1016/0004-3702(92)90090-K ]
• 14: Hogge, J., "TPLAN: A Temporal Interval-Based Planner with Novel Extensions", Technical Report UIUCDCS-R-87, University of Illinois, 1987.
• 15: H. A. Kautz, A formal theory of plan recognition, University of Rochester, Rochester, NY, 1987
• 16: Kautz, H. A., "Temporal Reasoning", M/T Encyclopedia of Cognitive Science (forthcoming), h ttp ://www. research, art. com/ ~Kautz/papers-ftp/index.html.
• 17: Koubarakis, M., Mylopoulos, J., Stanley, M., Borgida, A., "Telos: Features and Formalisation", Technical report KRR-TR-89-4, Department of Computer Science, University of Toronto, 1989.
• 18: Ladkin, P., Maddux, R., "The Algebra of Binary Constraint Networks", Kestrel Institute Technical Report KES. U. 88.9, 1988.
• 19: Ligozat, G., "On Generalised Interval Calculi", International AAAI Conference, 1991.
• 20: Li, J., Ozsu, T., Szafron, D., "Spatial Reasoning Rules in Multimedia Management Systems", International Conference on Multimedia Modelling (MMM), 1996.
• 21: Mackworth, A.K., "Consistency in Networks of Relations",Artificial Intelligence, 8, 1977.
• 22: Drew McDermott , Ernest Davis, Planning Routes through uncertain territory, Artificial Intelligence, v.22 n.1, p.107-156, March 1984
• 23: Mukerjee, A., Joe, G., "A qualitative Model For Space", International AAAI Conference, 1990.
• 24: Montanari, U., "Networks of Constraints: Fundamental Properties and Applications to Picture Processing", Information Science, 7, 1974.
• 25: Mohammad Nabil , Anne H. H. Ngu , John Shepherd, Picture Similarity Retrieval Using the 2D Projection Interval Representation, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.533-539, August 1996 [doi>10.1109/69.536246 ]
• 26: Nokel, K., "Temporal Matchning: Recognizing Dynamic Situations from Discrete Measurements", iith IJCAL 1989.
• 27: Dimitris Papadias , Nikos Mamoulis , Vasilis Delis, Algorithms for Querying by Spatial Structure, Proceedings of the 24rd International Conference on Very Large Data Bases, p.546-557, August 24-27, 1998
• 28: Dimitris Papadias , Timos K. Sellis, Spatial Reasoning Using Symbolic Arrays, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.153-161, September 21-23, 1992
• 29: Dimitris Papadias , Timos Sellis, Qualitative representation of spatial knowledge in two-dimensional space, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 30: Randell, D.A., Cui, Z., Cohn, A., "A Spatial Logic Based on Regions and Connection", Third International Conference on Principles of Knowledge Representation and Reasoning, 1992.
• 31: A. Prasad Sistla , Clement T. Yu , R. Haddad, Reasoning About Spatial Relationships in Picture Retrieval Systems, Proceedings of the 20th International Conference on Very Large Data Bases, p.570-581, September 12-15, 1994
• 32: Peter van Beek , Robin Cohen, Exact and approximate reasoning about temporal relations, Computational Intelligence, v.6 n.3, p.132-147, Aug. 1990 [doi>10.1111/j.1467-8640.1990.tb00130.x]
• 33: Marc Vilain , Henry Kautz , Peter van Beek, Constraint propagation algorithms for temporal reasoning: a revised report, Readings in qualitative reasoning about physical systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Temporal logic

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

General Terms:
Design, Management, Performance, Theory, Verification

Keywords:
conceptual neighbourhoods, spatiotemporal reasoning, spatiotemporal relations