[Colloq] PhD Thesis Defense, Tian Xia

[Rachel Kalweit]

College of Computer and Information Science
Presents:

PhD Thesis Defense

Tian Xia

who will speak on:
Subspace and Relaxed Skyline Query Processing

Friday, July 27, 2007
10:00am
166 West Village H

Abstract:
The skyline query is important in many applications such as 
multi-criteria decision making, data mining, and user-preference 
queries. Given a set of dimensional objects, the objects that are not 
dominated by others are called skyline objects. An object t is said to 
dominate another object t', if t is better than or equal to t' on all 
dimensions, and is strictly better than t' on at least one dimension. A 
skyline query finds all skyline objects in a dataset. In the database 
context, skyline queries can be divided into three categories: 
conventional skyline queries, subspace skyline queries, and skyline 
variant queries.

In this thesis, we first investigate subspace skyline query processing 
with efficient update support in dynamic environments. A skyline query 
issued on a subset of d dimensions is called a subspace skyline query. 
In practice, each point may have many attributes for skyline analysis, 
and various users can ask skyline queries on arbitrary subsets of the 
dimensions, depending on their interests. In an online system that 
accepts multiple concurrent subspace skyline queries, the query response 
time is important. Because of the heavy query load and unpredictability 
of the subspaces, on-the-fly computation from scratch is unsatisfactory 
in query performance. On the other hand, to simply pre compute and store 
all subspace skylines will incur expensive update costs. To achieve both 
fast query response and efficient update support, we propose the 
compressed skycube, a very concise representation of all skylines. 
Equipped with a new query processing algorithm and a new object-aware 
update scheme, the compressed skycube provides an efficient and scalable 
solution for online skyline query systems.

Furthermore, we investigate the drawbacks of the conventional skyline 
definition. Skylines do not always provide useful query results to 
users. For example, a skyline query may return too few or too many 
objects to users. Existing methods of various skyline queries have at 
least one of the following drawbacks: (1) the size of skyline objects 
can not be controlled, or can be only increased or only decreased but 
not both; (2) skyline objects do not have built-in ranks; (3) skylines 
do not reflect users' weights (preferences) at different dimensions. In 
this thesis, we propose a unified and comprehensive approach, the 
epsilon-skyline, to effectively solve all the above drawbacks. In 
particular, we define a flexible epsilon-dominance relation, such that 
epsilon-skyline sizes can be smaller or larger than the conventional 
skyline sizes. Moreover, epsilon-skyline objects have an integrated 
order and are responsive to users' weights. We thoroughly explore the 
properties of epsilon-skylines and propose several different algorithms 
(generic and index-based) to compute epsilon-skylines.

Committee members:
Prof. Donghui Zhang (Advisor)
Prof. Betty Salzberg
Prof. Harriet Fell
Prof. Peter Tarasewich
Prof. George Kollios (Boston University)