Ad-hoc top-k query answering for data streams.
Published: 2007
Language: eng
Number of pages: 48
ISBN-13: 9780494272954
Description: 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.
Notes: Source: Masters Abstracts International, Volume: 45-06, page: 3192.

Thesis (M.Sc.)--University of Toronto, 2007.

Electronic version licensed for access by U. of T. users.

ROBARTS MICROTEXT copy on microfiche.