Research On Optimal-Nearest-Neighbor And Reverse Visible Nearest Neighbor Queries

With the advances in mobile computing, wireless communication, and positioning technologies, many applications (such as traffic control, business trade, logistics, weather forecast, digital battlefield, etc.) accumulate a huge mass of spatial data. It is imperative for people to analyse the data, find the implicit knowledge and make a right dicision. Spatial database has become one of the leading positions in the area of database at the present age and has received more and more attention. Although numerous database specialists have been effort on the query processing techniques on spatial database and obtained a number of valuable results, there is a gap for satisfying various query requirements of the users as well as the increasingly new query requirements.Motivated by this problem, in this thesis, we introduce a new concept called "optimal distance" and a novel query processing termed as "optimal nearest neighbor query" which involves two datasets. In order to avoid accessing the nodes which are not the actual results, we propose three algorithms (including FP, RP, TS) .In addition, we use the reusing technology and develop two advanced algorithms, namely RFP and RRP, to decrease the I/O. Furthermore, we first formulize the reverse visible nearest neighbor query and present several algorithms to handle it. In particular, we sovel it respectively with naive-RVNN search (NR) and TPL-RVNN search (TR) which uses the TPL technology to reduce the memory space consumption and the CPU time. In addition, constrained reverse visible nearest neighbor and 8 reverse visible nearest neighbor are proposed with their processing methods. For each of the two kinds of novel query, an extensive experimental study with both real and synthetic datasets demonstrates the performance properties of the proposed algorithms in terms of efficiency and scalability.To sum up, our key contributions in this thesis are as follows:●We introduce the notion of ONN query and RVNN query, two alternative forms of NN search, which are useful types of queries in many practical applications involving spatial data for decision making.●We formalize the ONN queries and develop the Optimality metric that serves as the standard for Optimality evaluation.●We propose several algorithms to process ONN and RVNN queries efficiently.●We conduct extensive experiments with real and synthetic datasets under a variety of settings, to demonstrate the performance properties of our proposed algorithms in terms of efficiency and scalability.