Research Article | OPEN ACCESS
An Approach to Indexing and Retrieval of Spatial Data with Reduced R+ Tree and K-NN Query Algorithm
1S. Palaniappan, 2T.V. Rajinikanth and 3A. Govardhan
1Department of CSE, Saveetha University, Chennai
2Department of CSE, SNIST, Hyderabad
3Department of SIT, JNTUH, Kukatpally, Hyderabad-500085, Telangana, India
Research Journal of Applied Sciences, Engineering and Technology 2015 2:138-150
Received: September ‎13, ‎2014 | Accepted: November ‎26, ‎2014 | Published: May 20, 2015
Abstract
Recently, “spatial data bases have been extensively adopted in the recent decade and various methods have been presented to store, browse, search and retrieve spatial objects”. In this study, a method is plotted for retrieving nearest neighbors from spatial data indexed by R+ tree. The approach uses a reduced R+ tree for the purpose of representing the spatial data. Initially the spatial data is selected and R+ tree is constructed accordingly. Then a function called joining nodes is applied to reduce the number of nodes by combining the half-filled nodes to form completely filled. The idea behind reducing the nodes is to perform search and retrieval quickly and efficiently. The reduced R+ tree is then processed with KNN query algorithm to fetch the nearest neighbors to a point query. The basic procedures of KNN algorithm are used in the proposed approach for retrieving the nearest neighbors. The proposed approach is evaluated for its performance with spatial data and results are plotted in the experimental analysis section. The experimental results showed that the proposed approach is remarkably up a head than the conventional methods. The maximum time required to index the 1000 data points by the R+ tree is 10324 ms. The number of nodes possessed by reduced R+ tree is also less for 1000 data points as compared to the conventional R+ tree algorithm.
Keywords:
Indexing, KNN algorithm, query, R+ tree, spatial data,
References
-
Achakeev, D. and B. Seeger, 2012. A class of R-tree histograms for spatial databases. Proceeding of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL '12), pp: 450-453.
CrossRef
-
Ashton, K., 2009. That ‘Internet of Things’ thing. RFID J., 22(2009): 97-114.
-
Butenuth, M., G. Gsseln, M. Tiedge, C. Heipke, U. Lipeck and M. Sester, 2007. Integration of heterogeneous Spatial data in a federated database. ISPRS J. Photogramm., 62(5): 328-346.
CrossRef
-
Calì, A., D. Lembo and R. Rosati, 2003. Query rewriting and answering under constraints in data integration systems. Proceeding of the International Joint Conference on Artificial Intelligence, pp: 16-21.
-
Chong, E.I., J. Srinivasan, S. Das, C. Freiwald, A. Yalamanchi, M. Jagannath, A.T. Tran, R. Krishnan and R. Jiang, 2003. A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B+-trees. SIGMOD Rec., 32(2): 78-88.
CrossRef
-
Corral, A. and J. Almedros-Jimenez, 2007. A performance comparison of distance-based query algorithms using R-trees in spatial databases. Inform. Sciences, 177(11): 2207-2237.
CrossRef
-
Cuzzocrea, A. and A. Nucita, 2011. Enhancing accuracy and expressive power of range query answers over incomplete spatial databases via a novel reasoning approach. Data Knowl. Eng., 70(8): 702-716.
CrossRef
-
Doytsher, Y., B. Galon and Y. Kanza, 2012. Querying socio-spatial networks on the world-wide web. Proceeding of the 21st International World Wide Web Conference (WWW). Lyon, France, pp: 329-332.
CrossRef
-
Gaede, V. and O. Gunther, 1998. Multidimensional access methods. ACM Comput. Surv., 30(2): 170-231.
CrossRef
-
GEOMAPP, 2010. Retrieved from: www.geomapp.net.
Direct Link
-
Guttman, A., 1984. R-trees: A dynamic index structure for spatial searching. Proceeding of the ACM SIGMOD International Conference on Management of Data. Boston, Massachusetts, pp: 47-57.
CrossRef
-
Ives, Z.G., D. Florescu, M. Friedman, A. Levy and D.S. Weld, 1999. An adaptive query execution system for data integration. Proceeding of the ACM International Conference on Management of Data, pp: 299-310.
CrossRef
-
Jagadish, H.V., B.C. Ooi, K.L. Tan, C. Yu and R. Zhang, 2005. iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM T. Database Syst., 30(2): 364-397.
CrossRef
-
Kim, J.H., Y.H. Kim, S.W. Kim and S.H. Ok, 2002. An efficient processing of queries with joins and aggregate functions in data warehousing environment. Proceeding of the 13th International Workshop on Database and Expert Systems Applications. Aix-en-Provence, France, pp: 785-794.
CrossRef
-
Kollios, G., D. Gunopulos and V.J. Tsotras, 1999. On indexing mobile objects. Proceeding of the 18th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’99), pp: 261-272.
CrossRef
-
Lai, L., Z. Liu and L. Yan, 2002. K-nearest neighbor search algorithm by using R-tree. Comput. Eng. Des., 23(9).
-
Lin, H.Y., 2010. Efficient and compact indexing structure for processing of spatial queries in line-based databases. Data Knowl. Eng., 64(1): 365-380.
CrossRef
-
Liu, Y., Z. Zhu and S. Shi, 2001. A new space k-nearest neighbor query strategy. J. Shanghai Jiao Tong Univ., 35(9).
-
Liu, Y., S. Bo, Q. Zhang and Z. Hao, 2004. Multi-object nearest neighbor queries. Comput. Eng., 30(11): 66-68.
-
Papadias, D. and Y. Theodoridis, 1997. Spatial relations, minimum bounding rectangles and spatial data structures. Int. J. Geogr. Inf. Sci., 11(2): 111-138.
CrossRef
-
Papadopoulos, D., G. Kollios, D. Gunopulos and V.J. Tsotras, 2002. Indexing mobile objects on the plane. Proceedings of the 13th International Workshop on Database and Expert Systems Applications (DESA’02), pp: 693-697.
CrossRef
-
Shekhar, S. and S. Chawla, 2003. Spatial Databases: A Tour. Prentice-Hall, New Jersey.
-
Spatialkey, 2012. Retrieved from: http://support. spatialkey.com/spatialkey-sample-csv-data/.
Direct Link
-
Tang, J., Z.B. Zhou and Q. Wang, 2012. K-NN query algorithm based on PB-tree with the parallel lines division. Commun. Mobile Comput., 1(1): 1-10.
CrossRef
-
Taniar, D. and J.W. Rahayu, 2003. Global B+-tree indexing in parallel database systems. Lect. Notes Comput. Sc., 2690: 701-708.
CrossRef
-
Yanagisawa, Y., J. Akahani and T. Satoh, 2003. Shape-based similarity query for trajectory of mobile objects. Proceeding of the 4th International Conference on Mobile Data Management. Melbourne, Australia, pp: 63-77.
CrossRef
Competing interests
The authors have no competing interests.
Open Access Policy
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Copyright
The authors have no competing interests.
|
|
![](http://www.maxwellsci.com/images/RJASET-maxw.jpg) |
ISSN (Online): 2040-7467
ISSN (Print): 2040-7459 |
![Submit Manuscript](../images/sub.jpg) |
Information |
|
|
|
Sales & Services |
|
|
|