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

1. 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    
2. Ashton, K., 2009. That ‘Internet of Things’ thing. RFID J., 22(2009): 97-114.
   
3. 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    
4. 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.
   
5. 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    
6. 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    
7. 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    
8. 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    
9. Gaede, V. and O. Gunther, 1998. Multidimensional access methods. ACM Comput. Surv., 30(2): 170-231.
   CrossRef    
10. GEOMAPP, 2010. Retrieved from: www.geomapp.net.
    Direct Link
11. 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    
12. 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    
13. 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    
14. 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    
15. 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    
16. Lai, L., Z. Liu and L. Yan, 2002. K-nearest neighbor search algorithm by using R-tree. Comput. Eng. Des., 23(9).
    
17. 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    
18. Liu, Y., Z. Zhu and S. Shi, 2001. A new space k-nearest neighbor query strategy. J. Shanghai Jiao Tong Univ., 35(9).
    
19. Liu, Y., S. Bo, Q. Zhang and Z. Hao, 2004. Multi-object nearest neighbor queries. Comput. Eng., 30(11): 66-68.
    
20. 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    
21. 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    
22. Shekhar, S. and S. Chawla, 2003. Spatial Databases: A Tour. Prentice-Hall, New Jersey.
    
23. Spatialkey, 2012. Retrieved from: http://support. spatialkey.com/spatialkey-sample-csv-data/.
    Direct Link
24. 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    
25. Taniar, D. and J.W. Rahayu, 2003. Global B+-tree indexing in parallel database systems. Lect. Notes Comput. Sc., 2690: 701-708.
    CrossRef    
26. 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.