Abstract
Visibility computation is critical in spatial databases for realizing various interesting and diverse
applications such as defence-related surveillance, identification of interesting spots in tourist places, optimization of the placement of CCTV cameras for automated surveillance purposes and online warcraft
games. These applications in spatial databases often require identifying the locations around a target
object that have maximum visibility. This has several real-world applications such as finding the best
spots where tourists can gain a better view of the tourist attraction with the corresponding price of the
hotel rooms. Existing works mostly dealt with the variants of nearest neighbour queries such as KNN.
In the literature, the notion of Maximum Visibility (MV) query has been proposed, which identifies the
top-k individual query locations for which the visibility of target object is maximum in the presence
of obstacles. In particular, existing works solve the problem of identifying only individual locations
to maximize the visibility of a specific target object. However, in the presence of obstacles, one query
location would not be able to provide the maximum view of the target object. The single location that
gives the maximum view of target object among all locations may not provide the visibility of the parts
of target object which are obstructed by obstacles. In such cases, a set of locations could give the target
object a maximal view.
In this thesis, we propose an efficient approach to determine multiple query locations that maximizes
the visibility of target object altogether. We formulate a new query type called Multi-Location Visibility
(MLV) query and propose an apriori based algorithm to extract MLV queries. An MLV query determines
the top-k query locations from which the visibility of a given target object can be maximized subject to
the constraints of visibility, overlap and continuity.
The following are the issues in processing MLV query. First, determining potential candidate combinations from n query locations poses scalability issues as n increases. As n increases, the number
of combinations of query locations to be examined would essentially explode exponentially. Second,
computing visibility, overlap and continuity for every combination of locations is computationally expensive since the computations are spatial based. Hence, the challenges in developing the algorithm to
process MLV query include identifying heuristics to efficiently prune the search space to minimize the
combinations of query locations to be examined.
To process MLV query, we propose a Portion-Based Framework (PBF). The PBF provides opportunities for efficient determination of top-k candidate sets as well as for efficient computations of visibility,
overlap and continuity for each candidate set. The PBF is based on the concept of portion. We divide the given target object into equal-sized units, which we designate as portions. Thus, we model the given
target object as a set of portions. Then we propose efficient methodologies to compute the visibility,
overlap and continuity of each candidate set in terms of portions. The PBF facilitates the replacing of
complex and computationally expensive spatial operations by set-based operations, which are typically
faster by several orders of magnitude. Furthermore, we model the association of each portion and the
corresponding query locations from which that portion is visible as a transaction. Thus, we form a
set of portion transactions. The problem of extracting potential candidate sets of locations becomes the
problem of extracting combinations of query locations from the set of portion transactions. We leverage
the heuristics that are used to extract coverage patterns from a transactional database. On the basis of
the parameters such as visibility, overlap and continuity, we present an efficient apriori based pruning
algorithm for processing the MLV queries.
We have conducted an extensive performance evaluation using two real data-sets called British Ordinance Survey and Boston Downtown to demonstrate the effectiveness of the proposed scheme in terms
of query processing time, pruning efficiency, and target object visibility with respect to a recent existing
scheme. The experimental results show that the proposed approach performs significantly better, when
compared to the existing scheme in terms of processing time, pruning efficiency and the visibility. Overall, the proposed approach provides the scope for identifying a set of locations in an efficient manner
as compared to the existing approach. It can be extended to develop improved algorithms related to
visibility in several applications like robotics, multi-agent systems, online war-craft games, battle-field
scenarios, GIS, environment modeling, and surveillance applications.
