| The efficient evaluation of top-k queries has been an active research topic and many different instantiations of the problem, in a variety of settings, have been studied. However, current techniques are not directly applicable to highly dynamic environments and on-line applications, like data streams.; Recently, techniques supporting top-k queries on data streams have been introduced. Such techniques are restrictive however, as they can only efficiently report top-k answers with respect to a pre-specified (as opposed to ad-hoc) set of queries. In this thesis we introduce a novel geometric representation for the top-k query problem that allows us to raise this restriction. Utilizing notions of geometric arrangements, we design and analyze algorithms for incrementally maintaining and querying a data set organized in an arrangement representation under streaming updates. The performance of our core technique is augmented by incorporating tuple pruning strategies. A thorough experimental study evaluates the efficiency of the proposed technique. |
