Please use this identifier to cite or link to this item:
Title: Algorithms for multi-point range query and reverse nearest neighbour search
Keywords: database, reverse nearest neighbor, spatial queries
Issue Date: 25-Mar-2009
Citation: NG HOONG KEE (2009-03-25). Algorithms for multi-point range query and reverse nearest neighbour search. ScholarBank@NUS Repository.
Abstract: This thesis delves into two major areas of database research, namely (i) spatial database queries specifically for transportation and routing, and (ii) the reverse nearest neighbour (RNN) queries. Novel algorithms are introduced in both areas which outperforms the current state-of-the-art methods for the same types of queries. Firstly, this research work focuses on a type of proximity query called the multi-point range query (MPRQ). We showed that MPRQ is a natural extension to standard range queries and can be deployed in a wide range of applications, from real-life traveller information systems to computational biology problems. Motivation for MPRQ comes from the need to solve this type of query in a real-life traveller information system (the Route Advisory System (RADS) application, as well as its cousin web service Earth@sg Route Advisory Service at We researched various techniques used to solve MPRQ and discovered three approaches, presented their algorithms and analysed each of them in detail. Extensive, in-depth experiments were carried out to understand the MPRQ in a wide variety of problem parameters and MPRQ performs well in all of them against the conventional technique for solving MPRQ, i.e. the repeated range query (RRQ), used in proximity query systems today. Naturally, we extended MPRQ for external memory because in the real world, almost all applications deal with data that can never fit into internal memory. MPRQ also outperforms spatial join approaches for answering similar queries, such as the Slot Index Spatial Join (SISJ). Secondly, this thesis lent contribution to RNN queries in the form of a hierarchical, novel data structure to find exact RNN results in metric space. The data structure is called RNN-C tree, making use of kNN graphs and inherent data clustering to find RNN. The RNN query is related to the nearest neighbour (NN) queries but is much harder to solve. Besides the RNN-C tree, we also presented severalalgorithms based on the grid file to find approximate RNN results, but is much faster. In some time-critical applications, sometimes approximate results are a good tradeoff between accuracy and response time. To the best of our knowledge, ours is also the first attempt to adapt the grid file data structure for solving RNN queries. As RNN is related to NN, the grid file becomes a natural choice as it can return NN results efficiently.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
NgHK.pdf2.21 MBAdobe PDF



Page view(s)

checked on Apr 20, 2019


checked on Apr 20, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.