This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
teaching:mfe:is [2016/04/07 13:11] kgouda |
teaching:mfe:is [2016/04/13 16:19] msakr [A Generic Similarity Measure For Symbolic Trajectories] |
||
|---|---|---|---|
| Line 123: | Line 123: | ||
| In this master thesis project, due to the hardness of graph edit distance (computing graph edit distance is known to be NP-hard problem), the student will investigate the current approaches that deals with problem complexity while searching for similar (sub-)structures. At the end, the student should be able to empirically analyze and contrast some of the interesting approaches. | In this master thesis project, due to the hardness of graph edit distance (computing graph edit distance is known to be NP-hard problem), the student will investigate the current approaches that deals with problem complexity while searching for similar (sub-)structures. At the end, the student should be able to empirically analyze and contrast some of the interesting approaches. | ||
| + | |||
| + | =====A Generic Similarity Measure For Symbolic Trajectories===== | ||
| + | Moving object databases (MOD) are database systems that can store and manage moving object data. A moving object is a value that changes over time. It can be spatial (e.g., a car driving on the road network), or non-spatial (e.g., the temperature in Brussels). Using a variety of sensors, the changing values of moving objects can be recorded in digital formats. A MOD, then, helps storing and querying such data. There are two types of MOD. The first is the trajectory database, that manages the history of movement. The second type, in contrast, manages the stream of current movement and the prediction of the near future. This thesis belongs to the first type (trajectory databases). The research in this area mainly goes around proposing data persistency models and query operations for trajectory data. | ||
| + | |||
| + | A sub-topic of MOD is the study of semantic trajectories. It is motivated by the fact that the semantic of the movement is lost during the observation process. You GPS logger, for instance, would record a sequence of (lon, lat, time) that describe your trajectory. It won't, however, store the purpose of your trip (work, leisure, …), the transportation mode (car, bus, on foot, …), and other semantics of your trip. Research works have accordingly emerged to extract semantics from the trajectory raw data, and to provide database persistency to semantic trajectories. | ||
| + | |||
| + | Recently, Ralf Güting et al. published a model called “symbolic trajectories”, which can be viewed as a representation of semantic trajectories: | ||
| + | Ralf Hartmut Güting, Fabio Valdés, and Maria Luisa Damiani. 2015. Symbolic Trajectories. ACM Trans. Spatial Algorithms Syst. 1, 2, Article 7 (July 2015), 51 pages. | ||
| + | A symbolic trajectory is a very simple structure composed of a sequence of pairs (time interval, label). So, it is a time dependent label, where every label can tell something about the semantics of the moving object during its associated time interval. We think this model is promising because of its simplicity and genericness. | ||
| + | |||
| + | The goal of this thesis is to implement a similarity operator for symbolic trajectories. There are three dimensions of similarity in symbolic trajectories: temporal similarity, value similarity, and semantic similarity. Such an operator should be flexible to express arbitrary combinations of them. It should accept a pair of semantic trajectories and return a numerical value that can be used for clustering or ranking objects based on their similarity. Symbolic trajectories are similar to time series, except that labels are annotated by time intervals, rather than time points. We think that the techniques of time series similarity can be adopted for symbolic trajectories. This thesis should assess that, and implement a similarity measure based on time series similarity. The implementation is required to be done as an extension to PostGIS. We have already implemented some temporal types and operations on top of PostGIS, where you can start from. | ||
| + | |||
| + | Here is a list of deliverables that should guide you working on this thesis. It is, however, fine to suggest modifications to this list during the work. | ||
| + | * Reporting on the state of art of semantic trajectory similarity measures. | ||
| + | * Reporting on the state of art in time series similarity measures. | ||
| + | * Assessing the application of time series similarity to symbolic trajectories. | ||
| + | * Implementing symbolic trajectories on top of PostGIS. | ||
| + | * Implementation and evaluating the proposed symbolic trajectory similarity operator. | ||
| + | |||
| + | |||
| + | |||
| + | * Contact : [[ezimanyi@ulb.ac.be|Esteban Zimanyi]] | ||