Efficient processing of Top-k queries on spatial and temporal data

Abstract

Spatial and temporal databases play a vital role in many applications in different areas such as Geographic Information Systems (GIS), stock market, wireless sensor network, traffic monitoring and internet applications, etc. Due to their importance, a huge amount of work has focused on efficiently computing various spatial and temporal queries. Among the applications, end-users are more interested in the most important query answers in the potentially enormous answer space. Therefore, different types of information systems use various techniques to rank query answers and return the most important query results to users. Observed in real world scenario, top-k results are more interesting to users and a top-k query is a natural way to be asked to reflect a user s preference in terms of a user-defined scoring function. In this thesis, we provide efficient solutions for the top-k queries under various settings and different criteria for users preferences. Specifically, we tackle three types of top-k queries in a systematic way. Below is a brief description of our contributions.

We are the first to study the efficient monitoring of top-k pairs queries over data streams. We present the first approach to answer a broad class of top-k pairs and top-k objects queries over sliding windows. Our framework handles multiple top-k queries and each query is allowed to use a different scoring function, a different value of k and a different size of the sliding window. Furthermore, the framework allows the users to define arbitrarily complex scoring functions and supports out-of-order data streams.

We are the first to study the top-k loyalty queries. We propose a measure named loyalty that reflects how persistently an object satisfies the criteria. Formally, the loyalty of an object is the total time (in past T time units) it satisfied the query criteria. We propose an optimal approach to monitor the loyalty queries over sliding windows that continuously report k objects with the highest loyalties. We also experimentally verify the effectiveness of the proposed approach by comparing it with a classic sweep line algorithm.

We are the first to study the I/O efficient solution for depth-related problems which can be used for retrieving the top-k objects with linear scoring functions. Half-plane depth of a plane is the number of objects lying in the plane. Location depth of a point p is the minimum half-plane depth of any plane that is bounded by any line passing through p. We propose disk-based algorithms for a few important depth-related problems namely k-depth contour, k-snippet and k-upper envelope. We show that one of our proposed algorithms is I/O optimal for k-snippet and k-upper envelope problems.