Influence computation in spatial databases

Abstract

Influence computation plays a vital role in various applications such as marketing, cluster and outlier analysis and decision support systems. According to different preferences metric applied, several types of queries have been proposed and studied in the past decades. In this thesis, we provide efficient solutions for influence computation by considering the following query types: reverse k nearest neighbour (RkNN) query and its variation impact set query and distance based reverse top-k query. Below is a brief description of our contributions. We first study the RkNN query. We propose a novel algorithm called SLICE that utilizes the strength of region-based pruning and overcomes its limitation. SLICE is significant more efficient than the existing algorithms. We also propose an improved version of the most popular RkNN algorithm TPL called TPL++ that replaces the original filtering technique with a carefully developed cheaper yet more powerful filtering strategy and significant improves its performance. Besides, we are the first to present a comprehensive experimental study comparing the most notable RkNN algorithms. We also study a variation of RkNN query by relaxing the constraint that all users have the same value of k. We formally define such query as impact set query. We are the first to study the problem using query logs. We identify the limitations of the existing algorithms and propose an efficient algorithm that utilizes a novel access order and none-trivial observations to address these limitations. Our extensive experimental study demonstrates that our algorithm significantly outperforms existing algorithms. Last, we study distance based reverse top-k query which is a natural extension of reverse k nearest neighbors queries involving multiple criteria. We provide a pruning and verification based framework to answer distance based reverse top-k query and several optimizations are proposed to improve the efficiency.