Qualitative spatial and temporal representation and reasoning : efficiency in time and space
- Publication Type:
- Thesis
- Issue Date:
- 2017
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Qualitative Spatial and Temporal Reasoning (QSTR) provides a human-friendly abstract way to describe and to interpret spatial and temporal information. To describe the qualitative information, QSTR makes use of qualitative relations between entities and usually stores them in a qualitative constraint network (QCN). The QCNs are then used as the basis to process qualitative spatial and temporal information, including qualitative reasoning and query answering.
Time efficiency of reasoning techniques in QSTR is critical for applications to deal with qualitative spatial and temporal information in large-scale datasets. In this thesis, we present a special family of tractable subclasses of relations, called distributive subalgebras. We show that several efficient algorithms are applicable to the QCNs over distributive subalgebras for solving important reasoning problems. We also identify maximal distributive subalgebras for popular relation models in QSTR and point out their connections with several previously identified important subclasses.
Regarding the network representation in QSTR, there are two important problems, which in turn affect the time efficiency of other applications.
First, the network representation can have redundant relations, which will significantly increase the efforts needed for tasks whose efficiency is strongly related to the number of relations in a network. Fortunately, for any QCN over distributive subalgebras of qualitative calculi PA, RCC5, and RCC8, we show that essentially it has a unique subset consisting of non-redundant relations, which expresses the same qualitative information as the original QCN. We also devise an efficient algorithm to construct such subsets.
Second, the network representation sometimes requires a large storage space when encoding large-scale data. This could severely limit the ability of relation retrieval for any two given spatial entities. In fact, when the size of a QCN becomes large, it might be too costly or even infeasible to fit the QCN into fast accessible storage and relation retrieval will become inefficient. We propose two alternative representation techniques to compactly encode qualitative spatial relations between regions. For this purpose, the first technique uses minimum bounding rectangles (MBRs) to encode both topological relations and directional relations, while the second technique focuses on encoding topological relations by generating axis-aligned rectangles for spatial entities. We show that for large real-world datasets of regions, these two techniques can significantly reduce the storage size of qualitative spatial information and in the meantime the relations between regions can be efficiently inferred from those simple geometric shapes.
Please use this identifier to cite or link to this item: