Document Open Access Logo

An Efficient Representation of General Qualitative Spatial Information Using Bintrees

Authors Leif Harald Karlsen, Martin Giese

PDF
Thumbnail PDF

File

LIPIcs.COSIT.2017.4.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Leif Harald Karlsen
Martin Giese

Cite As Get BibTex

Leif Harald Karlsen and Martin Giese. An Efficient Representation of General Qualitative Spatial Information Using Bintrees. In 13th International Conference on Spatial Information Theory (COSIT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 86, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.COSIT.2017.4

Abstract

In this paper we extend previous work on using bintrees as an efficient representation for qualitative information about spatial objects. Our approach represents each spatial object as a bintree satisfying the exact same qualitative relationships to other bintree representations as the corresponding spatial objects. We prove that such correct bintrees always exists and that they can be constructed as a sum of local representations, allowing a practically efficient construction. Our representation is both efficient, w.r.t. storage space and query time, and can represent many well-known qualitative relations, such as the relations in the Region Connection Calculus and Allen's Interval Algebra.

Subject Classification

Keywords
  • Qualitative spatial data
  • Bintree
  • Data structure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of databases, volume 8. Addison-Wesley Reading, 1995. Google Scholar
  2. J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832-843, 1983. URL: http://dx.doi.org/10.1016/b978-1-4832-1447-4.50033-x.
  3. M. Attene, M. Campen, and L. Kobbelt. Polygon mesh repairing: An application perspective. ACM Computing Surveys (CSUR), 45(2):15, 2013. URL: http://dx.doi.org/10.1145/2431211.2431214.
  4. J. Chen, A. G. Cohn, D. Liu, S. Wang, J. Ouyang, and Q. Yu. A survey of qualitative spatial representations. The Knowledge Engineering Review, 30(01):106-136, 2015. URL: http://dx.doi.org/10.1017/S0269888913000350.
  5. A. G. Cohn, J. Bennett, B.and Gooday, and N. M. Gotts. Qualitative spatial representation and reasoning with the region connection calculus. GeoInformatica, 1(3):275-316, 1997. URL: http://dx.doi.org/10.1023/A:1009712514511.
  6. A. G. Cohn and N. M. Gotts. The ‘egg-yolk’ representation of regions with indeterminate boundaries. Geographic objects with indeterminate boundaries, 2:171-187, 1996. Google Scholar
  7. A. G. Cohn and J. Renz. Chapter 13 qualitative spatial representation and reasoning. In Handbook of Knowledge Representation, volume 3 of Foundations of Artificial Intelligence, pages 551 - 596. Elsevier, 2008. URL: http://dx.doi.org/https://doi.org/10.1016/S1574-6526(07)03013-1.
  8. A. Guttman. R-trees: a dynamic index structure for spatial searching, volume 14. ACM, 1984. URL: http://dx.doi.org/10.1145/971697.602266.
  9. R. Jin and G. Wang. Simple, fast, and scalable reachability oracle. Proceedings of the VLDB Endowment, 6(14):1978-1989, 2013. URL: http://dx.doi.org/10.14778/2556549.2556578.
  10. L. H. Karlsen and M. Giese. A Framework for Constructing Correct Qualitative Representations of Geometries using Mereology over Bintrees. Annals of Computer Science and Information Systems, 7:21-33, 2015. URL: http://dx.doi.org/10.15439/2015F183.
  11. L. H. Karlsen and M. Giese. An Efficient Representation of Qualitative Spatial Information using Bintrees. Technical report, Department of Informatics, University of Oslo, 2017. URL: http://hdl.handle.net/10852/53792.
  12. M. Koubarakis. Spatio-temporal databases: The CHOROCHRONOS approach, volume 2520. Springer Science &Business Media, 2003. URL: http://dx.doi.org/10.1007/b83622.
  13. K. Kyzirakos, M. Karpathiotakis, and M. Koubarakis. Strabon: a semantic geospatial DBMS. In ISWC'12, pages 295-311. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-35176-1_19.
  14. G. É. Ligozat. Reasoning about cardinal directions. Journal of Visual Languages &Computing, 9(1):23-44, 1998. URL: http://dx.doi.org/10.1006/jvlc.1997.9999.
  15. Z. Long, M. Duckham, S. Li, and S. Schockaert. Indexing large geographic datasets with compact qualitative representation. International Journal of Geographical Information Science, 30(6):1072-1094, 2016. URL: http://dx.doi.org/10.1080/13658816.2015.1104535.
  16. Z. Long, S. Schockaert, and S. Li. Encoding large RCC8 scenarios using rectangular pseudo-solutions. In Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning, pages 463-472. AAAI Press, 2016. Google Scholar
  17. Z. Long, M. Sioutis, and S. Li. Efficient path consistency algorithm for large qualitative constraint networks. IJCAI'16 Proceedings, 2016. URL: http://dx.doi.org/10.1142/S0218213015500311.
  18. Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, and Y. Theodoridis. R-trees: Theory and Applications. Springer Science &Business Media, 2010. URL: http://dx.doi.org/10.1007/978-1-84628-293-5.
  19. P. Nicholson. Space-Efficient Data Structures in the Word-RAM and Bitprobe Models. University of Waterloo, 2013. Google Scholar
  20. R. O. Obe and L. S. Hsu. PostGIS in Action. Manning Publications Co., Greenwich, CT, USA, 2nd edition, 2015. Google Scholar
  21. D. Papadias and T. Sellis. The semantics of relations in 2D space using representative points: Spatial indexes. In COSIT'93, pages 234-247. Springer, 1993. URL: http://dx.doi.org/10.1007/3-540-57207-4_16.
  22. D. A. Randell, Z. Cui, and A. G. Cohn. A spatial logic based on regions and connection. KR, 92:165-176, 1992. Google Scholar
  23. J. Renz. Maximal tractable fragments of the region connection calculus: a complete analysis. In IJCAI'99 Proceedings, pages 448-454. Morgan Kaufmann Publishers Inc., 1999. Google Scholar
  24. H. Samet. Object-based and image-based image representations. Foundations of Multidimensional and Metric Data Structures, pages 211-220, 2006. URL: http://dx.doi.org/10.1145/1031120.1031123.
  25. H. Samet and M. Tamminen. Bintrees, CSG Trees, and Time. SIGGRAPH Comput. Graph., 19(3):121-130, July 1985. URL: http://dx.doi.org/10.1145/325165.325211.
  26. M. Sioutis, J. Condotta, and M. Koubarakis. An efficient approach for tackling large real world qualitative spatial networks. International Journal on Artificial Intelligence Tools, 25(02):1550031, 2016. URL: http://dx.doi.org/10.1142/S0218213015500311.
  27. S. J. van Schaik and O. de Moor. A memory efficient reachability data structure through bit vector compression. In SIGMOD'11 Proceedings, pages 913-924. ACM, 2011. URL: http://dx.doi.org/10.1145/1989323.1989419.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact