Efficient indexing techniques for the update intensive environment

Yuni Xia, Purdue University

Abstract

For environments such as moving object and sensor databases where data is constantly evolving, traditional database index structures usually suffer from the need for frequent updates and result in poor performance. We propose and develop new indexing and querying techniques for the update intensive environment. Our approaches exploit properties of the applications such as the nature of the queries and the nature of data changes. Update intensive applications usually require monitoring of continuously changing data. Queries in these applications tend to be continuous queries with answers reported at multiple points in time. We introduce the Query Index (QI) and Velocity Constraint Index (VCI) for efficient and scalable execution of multiple continuous queries. Our work also exploits the nature of changes in data. We address common and important classes of data including moving object data and constantly evolving numerical data such as sensor data. Based on the nature of data changes, we introduce four new index structures---Q+Rtree and Change-tolerant Rtree (CTRtree) are developed for indexing moving object data and Mean Variance Tree (MVTree) and Forecasted Interval Index (FI-Index) are developed for indexing constantly evolving numerical data. The design of these index structures is based on not only the current values of the data being indexed, but also the nature of changes of data values. This approach maximizes the opportunity for the index to cover the updated values and reduces the number of expensive updates to the index structures. Experimental results establish the superior performance of the proposed index structures over traditional indexes. We also introduce the notion of change-tolerant indexing and design indexes with the explicit goal of optimizing both the update and query performance. The indexes trade slightly poorer query performance for a much superior update performance resulting in better overall performance.

Degree

Ph.D.

Advisors

Prabhakar, Purdue University.

Subject Area

Computer science

COinS