IIIT Hyderabad Publications |
|||||||||
|
Multi-location Visibility Query and It’s ProcessingAuthor: Lakshmi Gangumalla Date: 2020-05-16 Report no: IIIT/TH/2020/44 Advisor:P Krishna Reddy AbstractVisibility 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. Full thesis: pdf Centre for Data Engineering |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |