Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 2 of 2
-
ItemEffective, efficient and private similarity search in spatiotemporal trajectory datasets( 2019)Location-aware devices have become an integral part of our daily lives. With their widespread use, a tremendous amount of data in the form of spatiotemporal trajectory datasets have become available. The analysis of large-scale trajectory datasets has tremendous benefits for applications such as public transport, traffic management, urban planning and sports. However, many of those applications require one to accomplish a similarity search in such large datasets. A similarity search in spatiotemporal trajectory datasets is to find top k most similar trajectories to a given query trajectory. Similarity search in such large-scale and rich datasets has two main requirements: efficiency and effectiveness. Also, depending on the source of trajectory data, we may need to consider the privacy of people who provided their trajectories. However, a fundamental building block for the similarity search is the computation of similarity between a query trajectory and dataset trajectories. Existing work for similarity computation focuses mainly on the spatial aspects of trajectories, but more rarely takes into account time in conjunction with space. It this thesis, we define an effective similarity measure to compare trajectories in both space and time dimensions. Also, trajectory similarity search is computationally expensive, if it requires one to accomplish a one-by-one similarity comparison between the query trajectory and dataset trajectories. To address this problem, we propose an efficient indexing structure to eliminate distant trajectories from the query trajectory without requiring a similarity comparison. Finally, we focus on the privacy in trajectory similarity search. We propose a method for anonymising trajectories before we return them as the answer set of the query trajectory. Our method anonymises trajectories while it maintains their utility.
-
ItemTowards small-effort adaptions to off-the-shelf spatial and temporal indexes for modern database applications( 2012)Modern database applications demand high throughput of queries on complex data, such as the increasingly common types of spatial and temporal data. Many structures have been proposed for indexing spatial and temporal data and as standalone implementations they often achieve high levels of performance. However they are generally difficult to implement in an existing DBMS, which makes them very expensive to adopt. For example, Oracle took more than 5 years to implement the R-tree spatial index structure in their commercial DBMS. This thesis examines the techniques that exist in off-the-shelf spatial and temporal indexes with an emphasis on achieving large performance gains with minimal changes. In the domain of spatial data we propose a new index structure called Size Separation Indexing (SSI). This structure builds on the B+-tree, which is present in almost all DBMSs. Through extensive experimentation we show that SSI performs at least as well as all current spatial indexes and better than most on both a flat filesystem and on top of a DBMS. In the domain of temporal data we extend the TSB-tree, which is also based on the B+ -tree. In recent work the TSB-tree has been integrated into Microsoft SQL Server and we introduce the memory Hierarchy-aware Version tree which significantly improves on the performance of the TSB-tree for almost all query types and is scalable to huge datasets. Because our structures build upon existing indexes, we argue that they are better suited for implementation in current systems than other structures, reducing costs and increasing performance.