Discovery of influence sets in frequently updated databases

Abstract

An increasing number of organizations are currently working on ways to express and provide location information to services and applications. A location aware system knows the position of each component, and it is able to track devices through changes due to movement. In this context, data management issues such as efficient storage and retrieval of data through frequent updates pose new challenges. While we believe that spatial queries in general are going to gain in importance due to the emerging type of applications, we are particularly interested in the discovery of influence regions and influence sets around a query point. An influence set is formed by all points that have q as their nearest neighbor, and are located within the boundaries of an influence region. In this paper we propose for the first time a technique that reduces such a query to the more familiar nearest neighbor and range queries. These queries not only perform well in a dynamic environment, but also allow for their domain to be specified on demand. Additionally, the method we propose is based on already existing indexing and retrieval framework, thus facilitating integration with more complex location queries.