Upcoming DB Seminar
[31 Oct 2005]
Speaker: Ken YIU
Venue: Room 308, Chow Yei Ching Building, HKU
Time: 4:00pm
Past DB Seminars
DB Seminar Schedule
|
31 Oct 2005
Efficient Quantile Retrieval on Multi-Dimensional Data
Speaker: Ken YIU
Abstract
Given a set of $N$ multi-dimensional points, we study the computation of $\phi N$-quantiles according to a ranking
function $F$, which is provided by the user at runtime. Specifically, $F$ computes a score based on the coordinates of
each point; our objective is to report the object whose score is the $\phiN$-th smallest in the dataset. $\phi
N$-quantiles provide a succinct summary about the $F$-distribution of the underlying data, which is useful for online
decision support, data mining, selectivity estimation, query optimization, etc. Assuming that the dataset is indexed by
a spatial access method, we propose several algorithms for retrieving a quantile efficiently. Analytical and
experimental results demonstrate that a branch-and-bound method is highly effective in practice, outperforming
alternative approaches by a significant factor.
|