Computing Influence in Location-based Data Sets

Spatial databases have become a critical part of modern applications. Some important applications of a spatial database include Geographic Information System (GIS), Computer Aided Design(CAD), image processing and robotics. Spatial queries retrieve the required geographic data from spatial databases. In this thesis, we classify spatial queries into two categories based on their objective with regards to the notion of influence. The first category consists of the queries that aim to find the important/influential facilities. Some queries that fall into this category include range queries, k nearest neighbor queries, top-k queries and skyline queries. The second category is to find the influenced users. Queries in this category include reverse k nearest neighbor (RkNN) queries, reverse top-k queries and reverse skyline queries. In this thesis, we present efficient algorithms to solve queries in both categories