LOCATION-BASED NEAREST NEIGHBOUR SEARCH USING GRID-BASED SPATIAL INDEXING

Abstract

With the rapid development of mobile technology, location-based services (LBS) have become essential useful services to provide geographic information to mobile users. Location-based services (LBS) support the relevant geo-location information services that are navigation services, emergency services, information services, tracking, and management services. The mobile users extract the desired location information from their location position by using LBS content provider. LBS content provider needs to facilitate location information services for the users' satisfaction. Nearest neighbour search is the important part for location-based services to retrieve geo-location objects. To respond quickly location data, an index structure is essential for constructing spatial database. Therefore, many researchers have also been studied the spatial data structure for location-based nearest neighbour search. The focus of the research is to develop location-based nearest neighbour queries on the spatial database. To retrieve the nearest location objects effectively, an indexing technique is required to construct the data efficiently. Most of the location based services content providers use spatial databases to provide useful information that depends on the application areas of location-based services (LBS). The system offers the users the geolocation objects based on user's location position. The geolocation objects possess the location position and its attribute data. The system supports location-based keyword search and specific service type search for client users. Most of users prefer to find location objects what are existing nearby and within the particular distance from their current location. Therefore, The system develop for client users that provides range query and k-nearest neighbour query (kNN) that can retrieve location data accurately. This system is to provide location information efficiently according to the user preferences services from the specific location. This research uses nearest neighbor search algorithms for range query and k-nearest neighbor (kNN) query. Users can choose query types both range query and kNN query to retrieve geo-information data. In addition, the system supports to user not only spatial keyword search but also category-based search from user desired location. In the system, the spatial access method is necessary that is to support efficient storing and retrieving of geolocation objects in the spatial database. Using indexing techniques in the spatial database allows the clients to retrieve data quickly. The system uses R-tree indexing technique based on the Grid index structure for accessing objects effectively. R-tree index structure has been widely used in the research projects of spatial databases among variants access methods. R-tree index structure is a dynamic index structure for the spatial database. R-tree also supports various queries such as finding all records in a particular range and the objects which cover a certain area. The system is designed to support spatial queries efficiently and it also supports speed up computational performance. In this research, location data from townships in Yangon Region were used to develop the proposed system. The proposed index structure constructed the geo-data to support nearest neighbour queries efficiently. The geo-data are two-dimensional objects which compose latitude and longitude values and their attribute values. The location objects are enclosed in a minimum bounding box rectangle which is the coordinate of the lower-left corner and the coordinate of the upper-right corner. The main property of R-tree is to minimize the area of each enclosing rectangle in the index structure. For this reason, the proposed system uses R-tree that can be optimized for query processing in the spatial database. The implementation of this research developed on the client-server model. The main service of the server system is implemented on the cloud services for web hosting and creating the data in the cloud database.