×

Tesseral spatio-temporal reasoning for multi-dimensional data. (English) Zbl 0948.68165

Summary: A generally applicable approach to \(N\)-dimensional spatial reasoning is described. The approach is founded on a unique representation based on ideas concerning “tesseral” addressing. This offers many computational advantages including minimal data storage, computationally efficient translation of data, and simple data comparison, regardless of the number of dimensions under consideration. The representation allows spatial attributes associated with objects to be expressed simply and concisely in terms of sets of addresses which can then be related using standard set operations expressed as constraints. The approach has been incorporated into a spatial reasoning system – the SPARTA (SPAtial Reasoning using Tesseral Addressing) system – which has been successfully used in conjunction with a significant number of spatial application domains.

MSC:

68T10 Pattern recognition, speech recognition

Software:

CHIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beattie, B.; Coenen, F. P.; Bench-Capon, T. J.M.; Diaz, B. M.; Shave, M. J.R., Spatial reasoning for GIS using a Tesseral data representation, (Revell, N.; Tjoa, A. M., Database and Expert Systems Applications (Proceedings DEXA’95), Lecture Notes in Computer Science, 978 (1995), Springer: Springer Berlin), 207-216 · Zbl 0904.68139
[2] F.P. Coenen, B. Beattie, T.J.M. Bench-Capon, B.M. Diaz, M.J.R. Shave, Spatial reasoning for geographic information systems, Proceedings first International Conference on GeoComputation, School of Geography, University of Leeds, vol. 1, 1996, pp. 121-131.; F.P. Coenen, B. Beattie, T.J.M. Bench-Capon, B.M. Diaz, M.J.R. Shave, Spatial reasoning for geographic information systems, Proceedings first International Conference on GeoComputation, School of Geography, University of Leeds, vol. 1, 1996, pp. 121-131.
[3] Brown, A. G.P.; Coenen, F. P.; Shave, M. J.R.; Knight, M. W., An AI approach to noise prediction, Buil. Acoust., 4, 2, 137-150 (1999)
[4] Beattie, B.; Coenen, F. P.; Hough, A.; Bench-Capon, T. J.M.; Diaz, B. M.; Shave, M. J.R., Spatial reasoning for environmental impact assessment, Third International Conference on GIS and Environmental Modelling, National Centre for Geographic Information and Analysis (1996), Santa Barbara: Santa Barbara WWW and CD
[5] F.P. Coenen, B. Beattie, T.J.M. Bench-Capon, B.M. Diaz, M.J.R. Shave, Spatio-temporal reasoning using a multi-dimensional tesseral representation, Proceedings ECAI’98, Wiley, New York, 1998, pp. 140-144.; F.P. Coenen, B. Beattie, T.J.M. Bench-Capon, B.M. Diaz, M.J.R. Shave, Spatio-temporal reasoning using a multi-dimensional tesseral representation, Proceedings ECAI’98, Wiley, New York, 1998, pp. 140-144. · Zbl 0904.68139
[6] F.P. Coenen, B. Beattie, T.J.M. Bench-Capon, M.J.R Shave, B.M. Diaz, Spatial reasoning for timetabling: the TIMETABLER system, Proceedings of the first International Conference on the Practice and Theory of Automated Timetabling - ICPTAT’95, Napier University, Edinburgh, 1995, 57-68; F.P. Coenen, B. Beattie, T.J.M. Bench-Capon, M.J.R Shave, B.M. Diaz, Spatial reasoning for timetabling: the TIMETABLER system, Proceedings of the first International Conference on the Practice and Theory of Automated Timetabling - ICPTAT’95, Napier University, Edinburgh, 1995, 57-68
[7] F.P. Coenen, Rulebase checking using a spatial representation, Database and Expert Systems Applications (Proceedings DEXA’98), Lecture Notes in Computer Science, Springer, Berlin, 1999, pp. 166-175.; F.P. Coenen, Rulebase checking using a spatial representation, Database and Expert Systems Applications (Proceedings DEXA’98), Lecture Notes in Computer Science, Springer, Berlin, 1999, pp. 166-175.
[8] Allen, J. F., Time and time again: the many ways to represent time, Int. J. Intell. Systems, 6, 341-355 (1991)
[9] Egenhofer, M. J., Deriving the composition of binary topological relations, J. Visual Languages Comput., 5, 133-149 (1994)
[10] Bell, S. B.M.; Diaz, B. M.; Holroyd, F. C.; Jackson, M. J.J., Spatially referenced methods of processing raster and vector data, Image Vision Comput., 1, 4, 211-220 (1983)
[11] B.M. Diaz, S.B.M. Bell, Spatial data processing using tesseral methods, Natural Environment Research Council Publication, Swindon, England, 1986.; B.M. Diaz, S.B.M. Bell, Spatial data processing using tesseral methods, Natural Environment Research Council Publication, Swindon, England, 1986.
[12] G.M. Morton, A computer oriented geodetic data base, and a new technique in file sequencing, IBM Canada Ltd., 1966.; G.M. Morton, A computer oriented geodetic data base, and a new technique in file sequencing, IBM Canada Ltd., 1966.
[13] Grunbaum, B.; Shephard, G. C., Tilings and Patterns (1987), Freeman: Freeman New York · Zbl 0601.05001
[14] Holroyd, F. C., The Geometry of tiling hierarchies, Ars Combin., 16B, 211-244 (1983) · Zbl 0576.05009
[15] Samet, H., The quadtree and related data structures, ACM Comput. Surv., 16, 2, 187-260 (1984)
[16] Gargantini, I., Linear octrees for fast processing of three dimensional objects, Comput. Graphics Image Process., 20, 365-374 (1982)
[17] Retz-Schmidt, G., Various views on spatial preposition, AI Mag., 9, 2, 95-105 (1988)
[18] Cohn, A. G.; Gooday, J. M.; Bennet, B.; Gotts, N. M., A logical approach to representing and reasoning about space, Artif. Intell. Rev., 9, 255-259 (1995)
[19] van Hentenryck, P., Constraint Satisfaction in Logic Programming (1989), MIT Press: MIT Press Cambridge, MA
[20] Mackworth, A. K., Consistency in networks of relations, AI J., 8, 1, 99-118 (1977) · Zbl 0341.68061
[21] Lauriere, J-L., A language and a program for stating and solving combinatorial problems, Artif. Intell., 10, 1, 29-127 (1978) · Zbl 0374.68060
[22] Dincbas, M.; van Hentenryck, P.; Simonis, H.; Aggoun, A.; Graf, T.; Berthier, F., The constraint logic programming language CHIP, Proceedings of the International Conference on Fifth Generation Computer Systems (GGCS’88) (1998), Tokyo: Tokyo Japan
[23] A. Colmerauer, Opening the PROLOG-III universe, Byte Mag. 12 (9) (1987).; A. Colmerauer, Opening the PROLOG-III universe, Byte Mag. 12 (9) (1987).
[24] Jaffar, J.; Michaylov, S., Methodology and implementation of a CLP system, Fourth International Conference on Logic Programming (1987), Melbourne: Melbourne Australia
[25] Jaffar, J.; Lasses, J-L.; Maher, M. J., A logic programming language scheme, (DeGroot, D.; Linderstrom, G., Logic Programming, Relations, Functions and equations (1986), Prentice-Hall, Englewood Cliffs: Prentice-Hall, Englewood Cliffs NJ, USA) · Zbl 0900.68127
[26] Freksa, C., Qualitative spatial reasoning, (Mark, D. M.; Frank, A. U., Cognitive and Linguistic Aspects of Geographic Space (1991), Kluwer, Dordrecht: Kluwer, Dordrecht Netherlands), 361-372
[27] Hernández, D., Relative representation of spatial knowledgethe 2-D case, (Mark, D. M.; Frank, A. U., Cognitive and Linguistic Aspects of Geographic Space (1991), Kluwer, Dordrecht: Kluwer, Dordrecht Netherlands), 373-385
[28] A. Mukerjee, G. Joe, A qualitative model of space, Proceedings AAAI’ 90, 1990, pp. 721-727.; A. Mukerjee, G. Joe, A qualitative model of space, Proceedings AAAI’ 90, 1990, pp. 721-727.
[29] G. Ligozat, Weak representations of interval algebras, Proceedings AAAI’90, 1990, pp. 715-720.; G. Ligozat, Weak representations of interval algebras, Proceedings AAAI’90, 1990, pp. 715-720.
[30] Allen, J. F., Maintaining knowledge about temporal intervals, Commun. of the ACM, 26, 11, 832-843 (1983) · Zbl 0519.68079
[31] Allen, J. F., Towards a general theory of action and time, Arti. Intell., 23, 123-154 (1984) · Zbl 0567.68025
[32] J.F. Allen, J.A. Koomen, Planning using a temporal world model, in: Proceedings IJCAI’83, vol. 2, Morgan Kaufman, Los Altos, 1983, pp. 741-747.; J.F. Allen, J.A. Koomen, Planning using a temporal world model, in: Proceedings IJCAI’83, vol. 2, Morgan Kaufman, Los Altos, 1983, pp. 741-747.
[33] Allen, J. F.; Hayes, P. J., A common sense theory of time, (Proceedings IJCAI’85 (1985), Morgan Kaufman: Morgan Kaufman Los Altos), 528-531
[34] Allen, J. F.; Hayes, P. J., Short time periods, (Proceedings IJCAI’87 (1987), Morgan Kaufman: Morgan Kaufman Los Altos), 981-983
[35] Allen, J. F.; Hayes, P. J., Moments and points in an interval-based temporal logic, Comput. Intell. (Canada), 5, 225-238 (1989)
[36] Galton, A., A critical examination of Allen’s theory of action and time, Artif. Intell., 42, 159-188 (1990) · Zbl 0733.03017
[37] Vilain, M. B.; Kautz, H., Constraint propagation algorithms for temporal reasoning, (Proceedings AAAI’86 Morgan Kaufmann (1986), Los Altos: Los Altos CA), 377-382
[38] Vilain, M. B.; Kautz, H.; van Beek, P. G., Constraint propagation algorithms for temporal reasoninga revised report, (Weld, A. D.; de Kleer, J., Readings in Qualitative Reasoning about Physical Systems (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 373-381
[39] Nokel, K., Convex relations between time intervals, (Proceedings 5th Osterreichische Artificial-Intelligence-Tagung (1989), Springer: Springer Berlin), 298-302
[40] D. Puller, M.J. Egenhofer, Towards formal definitions of topological relations among spatial objects, in: D. Marble (Ed.), Proceedings Third International Symposium on Spatial Data Handling, 1988, pp. 225-242.; D. Puller, M.J. Egenhofer, Towards formal definitions of topological relations among spatial objects, in: D. Marble (Ed.), Proceedings Third International Symposium on Spatial Data Handling, 1988, pp. 225-242.
[41] Hamblin, C. L., Instants and intervals, Stud, Gen., 24, 127-134 (1971)
[42] Chang, S. K.; Shi, Q. Y.; Yan, C. W., Iconic Indexing by 2-D strings, IEEE Tran. Pattern Anal. Mach. Intell., PAM1-9, 3, 413-428 (1987)
[43] Frank, A.; Barrera, R.; Al-taha, K. K., Temporal relations in geographic information systems, ACM SIGMOS Rec., 20, 3, 85-91 (1991)
[44] J. Malik, T.O. Binford, Reasoning in time and space. Proceedings, International Joint Conference on Artificial Intelligence (IJCAI’83), vol. 1, 1983, pp. 343-345.; J. Malik, T.O. Binford, Reasoning in time and space. Proceedings, International Joint Conference on Artificial Intelligence (IJCAI’83), vol. 1, 1983, pp. 343-345.
[45] Papadias, D.; Theodoridis, Y.; Sellis, T.; Egenhofer, M. J., Topological relations in the world of minimum bounding rectangles: a study with R-trees, SIGMOD’95, ((1995), San Jose: San Jose CA, USA), 92-103
[46] Egenhofer, M. J., A formal definition of binary topological relationships, (Litwin, W.; Scheck, H-J., Proceedings third International Conference on Foundations of Data Organisation and Algorithms (FODO), Lecture Notes in Computer Science 367 (1989), Springer: Springer New York), 457-472
[47] Egenhofer, M. J.; Franzosa, R., Point-set topological spatial relationships, Int. J. Geographic Inform. Systems, 5, 161-174 (1991)
[48] Clarke, B. L., A Calculus of individuals based on connection, Notre Dame J. Formal Logic, 23, 3, 204-218 (1981) · Zbl 0438.03032
[49] Clarke, B. L., Individuals and points, Notre Dame J. Formal Logic, 26, 1, 61-75 (1985) · Zbl 0597.03005
[50] Cohn, A. G., A more expressive formulation of many sorted logic, J. of Automat. Reason., 3, 2, 113-200 (1987) · Zbl 0642.68166
[51] Randell, A. D., Analysing the familiarreasoning about space and time in the everyday world (1991), Ph.D. Thesis: Ph.D. Thesis University of Warwick, UK
[52] A.D. Randell, Z. Cui, A.G. Cohn, An interval logic for space based on “connections”, Proceedings of ECAI’92, 1992.; A.D. Randell, Z. Cui, A.G. Cohn, An interval logic for space based on “connections”, Proceedings of ECAI’92, 1992.
[53] Randell, A. D.; Cui, Z.; Cohn, A. G., A spatial logic based on regions and connection, Proceedings third International Conference on Principals of Knowledge Representation and Reasoning (1992), Morgan Kaufmann: Morgan Kaufmann Los Altrs, CA
[54] Cui, Z.; Cohn, A. G.; Randell, D. A., Qualitative simulation based on a logic of space and time, Proceedings AISB Workshop “Qualitative and Causal Reasoning” (QCR’93) (1993), University of Birmingham
[55] Vieu, L., A logical framework for reasoning about space, (Frank, A. U.; Campari, I., Spatial Information TheoryA Theoretical Basis for GISProceedings COSIT’93 (1993), Springer: Springer Berlin), 25-35
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.