Spatiotemporal Representation and Databases

Question 1

Explain topological relationships.

Answer 1

Topological relationships define spatial relations that are cognitively important. Researcher intuitions determine the necessary types of topological relationships.

Question 2

Explain the topological relations between two polygons.

Answer 2

See figure

Question 3

Explain metric relationships

Answer 3

Metric information refines spatial relations. Metrics include size, shape, distance or direction.

Question 4

What is a stixel and for what is it useful?

Answer 4

Rectangular elements formed by neighboring image points. Useful for urban scene representation and motion detection in a 6D-vision process.

Question 5

Indicate the differences between data model and process model.

Answer 5

Data modelling conceptualises the external world using a data model.

• A data model defines categories, classes of information and attributes.
• Describes how information is structured in a database and used.
• Data must be geo-referenced based on a global or local datum.

Process modelling (simulation model) represents dynamic phenomena and continuous fields. It is more difficult than entity modelling, since simulation models are often based on incomplete or subjective data.

Question 6

Indicate the difference between vector data model and raster data model.

Answer 6

 Vector data model: Uses points, lines, polygons, polyhedrons and compound entities.

 Raster data model: Uses a matrix composed of equal size elements (pixels or voxels) at a fixed resolution. Values are stored in the elements.

Question 7

Explain the intersection model of non-disjoint entities.

Answer 7

Each entity has an interior, a boundary and an exterior.

The exterior fills the “universe”, which is the space occupied by the entity itself and its boundary.

There are 9 topological relations.

Question 8

Enumerate the temporal relations.

Answer 8

 Association between elements (e.g. temporal distance, topological relations)

 Combination of elements from different temporal distributions (These are temporal overlays based on Boolean set operators)

 Transformation between temporal scales (generalisation and extrapolation)

Question 9

Explain the differences between location-based, entity-based and time-based representations of spatial-temporal relations.

Answer 9

Location-based representations: The location of the representation remains consistent. Changes are stored based on the location, but time intervals may be inconsistent. It describes “changes that happen at this location”.

 Spatial snapshots taken at intervals in a time series. Everything is included even if there were no changes since the last snapshot. The time interval between snapshots may not be uniform.

Drawbacks: Large redundancy, long retrieval time, missing events between intervals

Entity-based representation: Changes are stored based on an entity that remains consistent, even when other things change. It describes “changes that happen to this entity”.

 Changes in the geometry and semantics are treated separately. Any changes are incrementally recorded. This allows individual entities, components of those entities and the vector topology to be clearly maintained over time.

Drawbacks: Difficult to maintain the identity of individual entities, especially when entities split or merge through time.

Time-based representation: Changes are captured based on the passage of time, which continues even if entities change. It describes “changes that happen at this time”.

 The time associated with each change is stored in increasing temporal order from an initial state. Changes can include variations in locations and features (i.e. geometric and semantic characteristics).

Question 10

What is data structure?

Answer 10

 Data structure is the way data is stored in a computer. A well-designed data structure allows computer operations to be performed efficiently (e.g. fast execution and little memory space).

Question 11

Name examples of data structures.

Answer 11

Array (matrix)

 Group of items can be accessed by indexing. Usually, items have the same data type and the array occupies a contiguous (adjacent and mostly connected) area of storage.
 Multi-dimensional arrays can be accessed using more than one index, one for each dimension
 Fixed-sized (static) arrays: Size cannot change once its storage has been allocated
 Dynamic arrays: Resizable

Stack (an elevator)

 Last In First Out (LIFO)
 Two basic operations: Push and pop. Push adds an item to the top of the stack. Pop removes the top item.
 Only the top item is visible and accessible to the user. All other items remain hidden.

Queue (Traffic queue by a traffic light)

 Linear data structure
 First In First Out (FIFO)
 Basic operations: Addition of items to the rear position and removal of items from the front position.

Linked list (manufacturing process)

 Sequence of items, each containing arbitrary data fields and one or two “links” pointing to the next and/or previous items.
 Order of the linked items may be different from the order that the data items are stored in memory
 Linked lists permit insertion and removal of items at any point in the list

Tree (hierarchy) Family Tree

 Data structure with a set of linked nodes. A node may contain values, pointers or a tree of its own
 Each node in a tree has zero or more child nodes below it in the tree. A node that has a child is called a parent node. A node has at most one parent
 The height of a node is the length of the longest downward path to a leaf from that node.
 The height of the root is the height of the tree.
 The depth of a node is the length of the path to its root.

Graph (network) (Munich UBahn Network)

 Consisting of nodes and edges. The edges establish relationships between the nodes
 Informally, G = (V, E)
V: Vertices
E: Edges connecting the vertices