A Framework for Pattern Matching on Symbolic Trajectories and Tuples of Time-dependent Values

Valdés, Fabio

One of the striking developments since the beginning of this century is the proliferation of positioning technology devices in vehicles or with people. Large amounts of mobility data are recorded every day, entailing the necessity of efficient processing and analysis methods. Therefore, the management of such data, also called trajectories, has become a very active research field, particularly in the scope of spatiotemporal database management systems. Methods of associating semantic information to raw geographic trajectories by relating them to the spatial environment have been studied extensively. A question is how the resulting trajectories can be represented and especially queried in a convenient and efficient way. Moreover, in many cases, not only the geographic positions, but also additional time-dependent information regarding the moving entity are traced and/or generated, according to the purpose of the evaluation. For example, in the field of animal behavior research, besides the position of the monitored animal, biologists are interested in further data such as the altitude or the temperature at every measuring point. Other application domains comprise medical, logistic, or investigative information that can be recorded along with (or instead of) the geographic position of a person, animal, vehicle, etc. In this thesis, we propose a systematic and comprehensive study of annotated trajectory databases. A simple generic model called symbolic trajectory is defined to capture a wide range of meanings, either derived from a geometric trajectory or related to other time-dependent values. In its most essential form, a symbolic trajectory is just a time-dependent label; variants contain sets of labels, places, or sets of places. They are modeled as abstract data types and integrated into a well established framework of data types and operations for moving objects. Symbolic trajectories can represent, for example, the names of traversed roads obtained by map matching, transportation modes (walk, train, bus, etc.), a speed profile in symbolic form (e.g., fast, very fast, moderate), cells of a cellular network, certain behaviors of animals, names of restaurants within a certain distance, and so forth. Symbolic trajectories can be combined with geometric trajectories to obtain annotated trajectories. Besides the model, the main technical contribution of the thesis is a language for pattern matching and rewriting of symbolic trajectories, including efficient matching algorithms. A symbolic trajectory can be represented as a sequence of pairs of a time interval and a label. Such a pair is called a unit. A pattern consists of unit patterns (specifications for time interval and/or label) and wildcards, matching units and sequences of units, respectively, as well as regular expressions over such elements. It may further contain variables that can be used in conditions and in rewriting. Conditions and expressions in rewriting may use arbitrary operations available for querying in the host DBMS environment which makes the language extensible and highly expressive. We formally define the data model and syntax and semantics of the pattern language. Query operations are offered to integrate pattern matching, rewriting, and classification of symbolic trajectories into a DBMS querying environment. The implementation of the model using finite state machines and two indexes is described in detail. An experimental evaluation demonstrates the efficiency of the implementation. In particular, it shows considerable improvements in storage space and response time in a comparison of symbolic and geometric trajectories for several queries that can be executed on both types of trajectories. We also present in detail an approach for analyzing datasets with arbitrarily many time-dependent attributes. This can be considered as a major extension and generalization of our work on symbolic trajectories. For an efficient processing of different data types, a variable number of indexes of four different types that correspond to the data types of the attributes are applied. Again, we demonstrate the expressiveness and efficiency of our approach with a broad series of experiments using generated as well as real trajectories combined with geological raster data. A separate chapter is dedicated to a choice of application examples for pattern matching on symbolic trajectories and on tuples of time-dependent values.

Eine der auffälligsten technischen Entwicklungen seit Beginn dieses Jahrhunderts ist die massenhafte Verbreitung von mobilen Endgeräten zur Positionsbestimmung für Menschen oder Fahrzeuge. Täglich werden große Mengen von Bewegungsdaten aufgezeichnet, was die Notwendigkeit effizienter Verarbeitungs- und Analysemethoden mit sich bringt. Die Verarbeitung solcher Daten, die auch Trajektorien genannt werden, ist daher zu einem sehr aktiven wissenschaftlichen Betätigungsfeld geworden, insbesondere im Hinblick auf Datenbankmanagementsysteme für raumzeitliche Daten. Es existieren bereits zahlreiche Untersuchungen über die Anreicherung geometrischer Trajektorien mit semantischen Informationen. Offen ist allerdings, wie die daraus resultierenden Trajektorien dargestellt und vor allem zweckmäßig und effizient analysiert werden können. Weiterhin sind in vielen Fällen nicht nur die geometrischen Positionen von Interesse, sondern es werden zusätzliche zeitabhängige Informationen mit Bezug zu dem beweglichen Objekt aufgezeichnet und/oder aus anderen Quellen gewonnen, je nachdem, welches Ziel die Analyse verfolgt. Beispielsweise interessieren sich Biologen im Bereich der Verhaltensforschung neben der Position des beobachteten Tieres auch für die Höhe oder die Temperatur an jedem Messpunkt. In anderen Anwendungsbereichen werden medizinische oder logistische Parameter sowie relevante Informationen für eine polizeiliche Ermittlung gemeinsam mit (oder anstelle von) der geographischen Position einer Person, eines Tieres, eines Fahrzeugs usw. aufgezeichnet. In dieser Arbeit wird eine systematische und umfassende Untersuchung von annotierten Trajektorien in Datenbanken durchgeführt. Wir definieren ein einfaches generisches Modell, das wir symbolische Trajektorie nennen und das ein breites Spektrum verschiedener Bedeutungen abdeckt. Diese werden entweder direkt von der geometrischen Trajektorie abgeleitet oder stehen mit anderen zeitabhängigen Werten in Beziehung. In ihrer einfachsten Form ist eine symbolische Trajektorie lediglich eine zeitabhängige Bezeichnung, während andere Varianten Mengen von Bezeichnungen, Orte oder Mengen von Orten enthalten. Alle Varianten werden als abstrakte Datentypen modelliert und in ein bewährtes System von Datentypen und Operationen für bewegliche Objekte eingefügt. Symbolische Trajektorien können beispielsweise die durch Kartenabgleich (Map Matching) ermittelten Namen verwendeter Straßen, Transportmittel (Fußweg, Zug, Bus usw.), ein Geschwindigkeitsprofil in symbolischer Form (z.B., schnell, sehr schnell, moderat), Zellen eines Mobilfunknetzes, bestimmte Verhaltensweisen von Tieren oder Namen von Restaurants innerhalb eines bestimmten Radius repräsentieren. Symbolische Trajektorien und geometrische Trajektorien können zu annotierten Trajektorien zusammengesetzt werden. Abgesehen von der Modellierung besteht der wichtigste Beitrag dieser Arbeit aus einer Sprache für den Mustervergleich und die musterabhängige Neuschreibung symbolischer Trajektorien inklusive effizienter Vergleichsalgorithmen. Eine symbolische Trajektorie lässt sich als Folge von Paaren von einem Zeitintervall und einer Bezeichnung darstellen. Ein solches Paar nennen wir ein Element. Ein Muster besteht aus sogenannten Elementmustern (Spezifikationen für ein Zeitintervall und/oder eine Bezeichnung) und Platzhaltern, die mit Elementen bzw. Folgen von Elementen einer symbolischen Trajektorie übereinstimmen können, sowie regulären Ausdrücken über diesen Bestandteilen. Weiterhin kann ein Muster Variablen enthalten, mit deren Hilfe sich Bedingungen und Neuschreibungsregeln formulieren lassen. Da in beiden beliebige Operationen aus der zugrundeliegenden Datenbankumgebung verwendet werden können, ist die Sprache erweiterbar und höchst ausdrucksstark. Sowohl das Datenmodell als auch die Syntax und Semantik der Mustersprache werden formal definiert. Wir führen Anfrageoperationen ein, die den Mustervergleich, die musterabhängige Neuschreibung und die Klassifikation symbolischer Trajektorien in eine Datenbankumgebung einbetten. Die Implementierung des Modells mit Hilfe endlicher Automaten und zweier Indexe wird detailliert beschrieben. Eine experimentelle Auswertung zeigt die Effizienz der Implementierung, insbesondere im Hinblick auf Speicherplatz- und Laufzeitvorteile in einem Vergleich von Lösungsansätzen mit symbolischen und geometrischen Trajektorien für einige Anfragen, die mit beiden Arten von Trajektorien beantwortet werden können. Außerdem stellen wir, als wesentliche Erweiterung und Verallgemeinerung der Untersuchung symbolischer Trajektorien, ein Konzept zur Analyse von Datenmengen mit beliebig vielen zeitabhängigen Attributen vor. Zur effizienten Verarbeitung verschiedener Datentypen wird eine variable Anzahl von Indexen verschiedener Typen verwendet, abhängig von den Datentypen der Attribute. Erneut demonstrieren wir die Ausdrucksstärke und Effizienz unseres Ansatzes mit zahlreichen Experimenten unter Verwendung von generierten sowie aufgezeichneten Trajektorien kombiniert mit geologischen Rasterdaten. Ein separates Kapitel ist einer Auswahl von Anwendungsbeispielen für den Mustervergleich auf symbolischen Trajektorien sowie auf Tupeln zeitabhängiger Werte gewidmet.

Vorschau

Zitieren

Zitierform:

Valdés, Fabio: A Framework for Pattern Matching on Symbolic Trajectories and Tuples of Time-dependent Values. Hagen 2017. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe