A Framework for Constructing Correct Qualitative Representations of Geometries using Mereology over Bintrees

• Autorzy: Leif Harald Karlsen , Martin Giese
• Języki publikacji: EN

Abstrakty

EN

In this paper we explore how bintrees can function as a suitable representation for mereological objects, and how such objects can be used to construct correct representations of geometries, with respect to qualitative queries constructed from a given set of mereological relations. We will show how these correct representations can be stored and queried by a traditional relational database using relational algebra, or similar tuple- based databases. We will define a model theoretic semantics for the bintrees and show how we can construct these correct representations as solutions to constraint networks with variables ranging over bintrees. Furthermore, we make an algorithm for solving the constraints and prove its correctness. The framework presented in the paper is not limited to only constructing representations of geometries, but representations of any objects where a part-of relationship is natural.(original abstract)

Słowa kluczowe

EN

Fractal analysis

PL

Geometria fraktalna

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 7
• Strony: 21--33

Twórcy

autor

Leif Harald Karlsen

• University of Oslo

autor

Martin Giese

• University of Oslo

Bibliografia

• M. Koubarakis, Spatio-temporal databases: The CHOROCHRONOS approach. Springer Science & Business Media, 2003, vol. 2520. [Online]. Available: http://dx.doi.org/10.1007/b83622
• H. Samet and M. Tamminen, "Bintrees, csg trees, and time," SIGGRAPH Comput. Graph., vol. 19, no. 3, pp. 121-130, Jul. 1985. [Online]. Available: http://doi.acm.org/10.1145/325165.325211
• R. Casati and A. C. Varzi, Parts and places: The structures of spatial representation. MIT Press, 1999. [Online]. Available: http://dx.doi.org/10.1215/00318108-110-3-479
• S. Abiteboul, R. Hull, and V. Vianu, Foundations of databases. Addison-Wesley Reading, 1995, vol. 8.
• A. G. Cohn, B. Bennett, J. Gooday, and N. M. Gotts, "Qualitative spatial representation and reasoning with the region connection calculus," GeoInformatica, vol. 1, no. 3, pp. 275-316, 1997. [Online]. Available: http://dx.doi.org/10.1023/A:1009712514511
• C.-Y. Huang and K.-L. Chung, "Fast operations on binary images using interpolation-based bintrees," Pattern Recognition, vol. 28, no. 3, pp. 409-420, 1995. [Online]. Available: http://dx.doi.org/10.1016/ 0031-3203(94)00102-r
• Y. E. Ioannidis and R. Ramakrishnan, "Efficient transitive closure algorithms." in VLDB, vol. 88, 1988, pp. 382-394. [Online]. Available: http://dx.doi.org/10.1016/0020-0190(94)90128-7
• R. Agrawal, A. Borgida, and H. V. Jagadish, "Efficient management of transitive relationships in large data and knowledge bases," vol. 18, no. 2, 1989. [Online]. Available: http://dx.doi.org/10.1145/66926.66950
• J. F. Allen, "Maintaining knowledge about temporal intervals," Communications of the ACM, vol. 26, no. 11, pp. 832-843, 1983. [Online]. Available: http://dx.doi.org/10.1016/b978-1-4832-1447-4.50033-x
• K. Aizawa and S. Tanaka, "A constant-time algorithm for finding neighbors in quadtrees," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 31, no. 7, pp. 1178-1183, 2009. [Online]. Available: http://dx.doi.org/10.1109/tpami.2008.145