PROJECT TITLE :

Range-Based Nearest Neighbor Queries with Complex-Shaped Obstacles - 2018

ABSTRACT:

During this Project, we study a novel variant of obstructed nearest neighbor queries, namely, vary-based mostly obstructed nearest neighbor(RONN) search. As a natural generalization of continuous obstructednearest-neighbor(CONN), an RONN query retrieves a collection of obstructed nearest neighbors corresponding to every point in a very specified range. We have a tendency to propose a new index, specifically binary obstructed tree (called OB-tree), for indexing complex objects in the obstructed area. The novelty of OB-tree lies in the idea of dividing the obstructed space into non-obstructedsubspaces, planning to efficiently retrieve highly qualified candidates for RONN processing. We develop an algorithm for construction of the OB-tree and propose a space division scheme, known as optimal obstacle balance (OOB2) theme, to handle the tree balance downside. Accordingly, we propose an economical algorithm, called RONN by OB-tree Acceleration (RONN-OBA), which exploits the OB-tree and a binary traversal order of data objects to accelerate query processing of RONN. Additionally, we extend our work in many aspects regarding the form of obstacles, and range-based k NN queries in obstructed space. At last, we have a tendency to conduct a comprehensive performance analysis using both real and synthetic datasets to validate our ideas and therefore the proposed algorithms. The experimental result shows that the RONN-OBA algorithm outperforms the two R-tree primarily based algorithms and RONN-OA significantly.