Location-Based R-Tree and Grid-Index for Nearest Neighbor Query Processing

Location Based Services (LBS) is a service that integrates mobile device's location and other information relating with current location to the user. Geospatial data identifies the geographic location of features and boundaries on Earth. Spatial index can be used for indexing geographic data. Spatial indexes can improve spatial query efficiency. Using spatial index method is suitable for huge volume of data. There are many spatial index methods such as R-tree, B-tree, kd-tree, Quad-tree, Grid index. In this study, nearest neighbors (NN) that can be used by various levels of people (e.g. stores, clinics, mini-marts, schools, convenience stores, bazaars, etc.,) are showed with detailed information. This study uses R-tree method to get detailed NN results efficiently. But R-tree will generate much overlapping and coverage between MBR. So R-tree by combining with Grid-partition index is used because grid-index can reduce the overlap and coverage between MBR. The query performance will be efficient by using these methods.