Efficient visibility analysis for massive observers

Abstract

Many applications in Geographic Information System (GIS) apply visibility analysis as a key subroutine, and thus the time spent on visibility analysis is the bottleneck for all these applications, such as navigation, aviation, landscape, and military etc. The new challenge to the scalability of visibility analysis for large datasets shows, most of academic works in GIS only consider a few thousands of observer objects, while many works in industry and science have to face on millions (even billions) of observer objects. In this paper, we devise a novel computation framework which consists of three components, i.e., optimized line-of-sight algorithm, R∗-tree filter and MapReduce-based segmented computation. The proposed solution can support GIS systems to conduct efficient visibility analysis for massive observers. Finally, we demonstrate the efficiency and the scalability of our proposed solutions by synthetic datasets. The results show that our proposed solution achieves at least an order of magnitude speedup over existing solutions.