Abstract
Iceberg queries have been recently identified as important queries for many applications. These queries can be characterized by their huge input-small output. The iceberg refers to the input, and the tip of it refers to the output. We present an efficient algorithm for computing an important class of iceberg queries. This algorithm uses a focusing technique for the query result using quantiling. The new algorithm almost always requires two or less scans over the input data, which outperforms other algorithms by a factor of two or more. It has several nice properties; it scales nicely with the data size; it is robust against the data distribution. Its memory and computational requirements are small. Further, it is easy to manage. We evaluate its performance using real and synthetic datasets. We believe that the presented algorithm is the algorithm of choice for computing the queries considered in this work.