Efficient processing of maximum visibility facility selection query in spatial databases

Abstract

The widespread availability of realistic 3D models of cities, buildings etc. provides an op- portunity to answer many real-life queries involving visibility in the presence of 3D obstacles. For example, ”Where to place security cameras to ensure better surveillance of a building?”, or ”Where to place billboards in a city to maximize visibility from the surrounding space?”, these applications require measuring and maximizing visibility of the data space in the presence of obstacles. In this paper, we formulate the above problem of maximizing visibility by introducing the MVFS query. In the MVFS query, we are given a set of obstacles, a set of n locations where a facility (i.e., camera, billboard, watch tower etc.) can be established, the visibility range of the facility, and an integer k, we select k locations from the given n locations to establish facilities such that the aggregated visibility coverage of the surrounding data space is maximized. We develop two exact algorithms for the MVFS problem that use various acceleration techniques to speedup the computation. We also outline a greedy approximation algorithm with proven ap- proximation ratio of 1− 1 . Usually real 3D models consist of a huge number of objects/obstacles. Consequently we develop several scalable algorithms for the MVFS problem which are suitable for datasets with huge number of obstacles that do not fit in main memory. To deal with the huge obstacle set, first we propose a naive disk resident implementation of the above greedy approxi- mation algorithm and then we develop two improved algorithms that result in less IO overhead than the naive greedy implementation. We also address several variants of the MVFS problem so that our proposed algorithms can be applied to more generalized and realistic scenarios. We conduct comprehensive empirical analysis to investigate the performance of our proposed algo- rithms. The experimental results show that the greedy approximation algorithm runs orders of magnitude faster than the exact algorithms and incurs an average approximation error of less than

4

0.1%. In case of disk resident algorithms, the experiments show that the acceleration techniques used in the improved algorithms considerably reduce the IO overhead in comparison with the naive greedy implementation.