Abstract
Recently, querying and analyzing data streams are widely applied in various applications. Most of these applications issue continuous top-k queries over multiple data streams. A top-k query is one that finds the k highest ranked answers to a user defined aggregate function such as max, min, or sum functions. In previous works, most methods focus on one-time top-k query algorithms. One-time top-k queries mean that the top-k query is only executed once. These one-time top-k query algorithms are not appropriate for processing continuous top-k queries. Many operations can be executed for nothing if the answer remains unchanged. There are algorithms for processing the continuous top-k query, but they lack of the mechanisms for sharing information to reduce the heavy bandwidth load for processing multiple continuous top-k queries. In this thesis, we propose a method for efficiently processing multiple continuous top-k queries. For example, assume that there are m servers, each with identical copies of the web content. We keep the pages that have been sent from the servers. The hit of each page is limited to a specific range. These pages and ranges are maintained in the structure named Ranked List Table in the coordinator so that the coordinator can try to decide the most popular pages by summing up the range of each page. Besides, we prove the correctness of the top-k results in the thesis when the coordinator calculates the top-k results by using the structure. However, the top-k result may not be decided by using the structure. We also propose a heuristic access order strategy to schedule the order of accessing servers so that the coordinator can get the accurate hits of the pages to decide the top-k result as early as possible. Our preliminary experimental results show that our approach is practical and efficient.