Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 2 of 2
-
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.
-
ItemOnline time series approximation and prediction( 2012)In recent years, there are rapidly increasing research interests in the management of time series data due to its importance in a variety of applications such as network traffic management, telecommunications, finance, sensor network and location based services. In this thesis, we focus on two important problems of the management of time series data: the online time series approximation problem and the online time series prediction problem. The time series approximation can reduce the space and the computational cost of storing and transmitting time series data, and also reduce the workload of the data processing. Segmentation is one of the most commonly used methods to meet this requirement. However, while most of the current segmentation methods aim to minimize the holistic error between the approximation and the original time series, few works try to represent time series as compact as possible with an error bound guarantee on each data point. Moreover, in many real world situations, the patterns of the time series do not follow a constant rule such that using only one type of functions may not yield the best compaction. Motivated by these observations, we propose an online segmentation algorithm which approximates time series by a set of different types of candidate functions (poly nomials of different orders, exponential functions, etc.) and adaptively chooses the most compact one as the pattern of the time series changes. A challenge in this approach is to determine the approximation function on the fly (“online”). Thereby, we further present a novel method to efficiently generate the compact approximation of a time series in an online fashion for several types of candidate functions. This method incrementally narrows the feasible coefficient spaces of candidate functions in coefficient coordinate systems such that it can make each segment as long as possible given an error bound on each data point. Extensive experimental results show that our algorithm generates more compact approximations of the time series with lower average errors than the state-of-the-art algorithm. The time series prediction aims to predict future values of the time series according to their previously observed values. In this thesis, we focus our work on a specific branch of the time series prediction: the online locational time series prediction problem, i.e, predicting the final locations of the locational time series according to their current observed locational time series values on the fly. This problem is also called the destination prediction problem and the systems used to solve this problem are the called destination prediction systems. However, most of current destination prediction systems are based on the traveling histories of specific users so they are too ad hoc to accurately predict other users’ destination. In our work, we propose the first generic destination prediction solution to provide the accurate destination prediction services to all users based on the given user queries (i.e., the users’ current partial traveling trajectories) without knowing any traveling histories of the users. Extensive experiments validate that the prediction result of our method is more accurate than that of the competing method.