CFP last date
22 April 2024
Call for Paper
May Edition
IJCA solicits high quality original research papers for the upcoming May edition of the journal. The last date of research paper submission is 22 April 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A State-of-Art in R-Tree Variants for Spatial Indexing

by Lakshmi Balasubramanian, M. Sugumaran
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 42 - Number 20
Year of Publication: 2012
Authors: Lakshmi Balasubramanian, M. Sugumaran
10.5120/5819-8132

Lakshmi Balasubramanian, M. Sugumaran . A State-of-Art in R-Tree Variants for Spatial Indexing. International Journal of Computer Applications. 42, 20 ( March 2012), 35-41. DOI=10.5120/5819-8132

@article{ 10.5120/5819-8132,
author = { Lakshmi Balasubramanian, M. Sugumaran },
title = { A State-of-Art in R-Tree Variants for Spatial Indexing },
journal = { International Journal of Computer Applications },
issue_date = { March 2012 },
volume = { 42 },
number = { 20 },
month = { March },
year = { 2012 },
issn = { 0975-8887 },
pages = { 35-41 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume42/number20/5819-8132/ },
doi = { 10.5120/5819-8132 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:31:50.826017+05:30
%A Lakshmi Balasubramanian
%A M. Sugumaran
%T A State-of-Art in R-Tree Variants for Spatial Indexing
%J International Journal of Computer Applications
%@ 0975-8887
%V 42
%N 20
%P 35-41
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Nowadays, indexing has become essential for fast retrieval of results. Spatial databases are used in many applications which demand faster retrieval of data. These data are multi-dimensional. Designing index structure for spatial databases is current area of research. R-Tree is the most widely used index structure for multi-dimensional data. Many variants of R-Tree has evolved with each performing better in some aspect like query retrieval, insertion cost, application specific and so on. In this work, state-of-art of variants in R-Tree is presented. This paper provides an idea of the present development in spatial indexing and paves way for the researchers to explore and analyze the difficulties and trade-offs in the work. The R-Tree variants are classified according to the way they are different from the original R-Tree either in the process of construction or whether it is a hybrid of R-Tree and some other structure or whether it is an extension of R-Tree to support many other applications.

References
  1. A. Guttman, "R-trees: A Dynamic Index Structure for Spatial Searching", Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57, 1984.
  2. Timos K. Sellis, Nick Roussopoulos and Christos Faloutsos, "The R+-Tree: A Dynamic Index for Multi-Dimensional Objects", Proceedings of 13th International Conference on Very Large Data Bases, pp. 507-518, 1987.
  3. N. Beckmann, H. -P. Kriegel, R. Schneider and B. Seeger, "The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles", Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 322-331, 1990.
  4. X. Xu, J. Han and W. Lu, "RT-Tree: An Improved R-tree Index Structure for Spatiotemporal Databases", Proceedings of the 4th International Symposium on Spatial Data Handling, pp. 1040-1049, 1990.
  5. I. Kamel and C. Faloutsos, "On Packing R-Trees", Proceedings of the 2nd International Conference on Information and Knowledge Management, pp. 490-499, 1993.
  6. I. Kamel and C. Faloutsos, "Hilbert R-Tree - An Improved R-tree using Fractals", Proceedings of the 20th International Conference on Very Large Data Bases, pp. 500-509, 1994.
  7. L. Arge, "The Buffer Tree: A New Technique for Optimal I/O Algorithms", Proceedings of the 4th International Workshop on Algorithms and Data Structures, pp. 334-345, 1995.
  8. Stefan Berchtold, Daniel A. Keim and Hans-Peter Kriegei, "The X-tree: An Index Structure for High-Dimensional Data", Proceedings of the 22nd International Conference on Very Large Data Bases, pp. 28-39, 1996.
  9. Y. Theodoridis, M. Vazirgiannis and T. Sellis, "Spatio-Temporal Indexing for Large Multimedia Applications", Proceedings of the 3rd IEEE International Conference on Multimedia Computing and Systems, pp. 441-448, 1996.
  10. S. Leutenegger, J. M. Edgington and M. A. Lopez, "STR - A Simple and Efficient Algorithm for R-Tree Packing", Proceedings of the 13th IEEE International Conference on Data Engineering, pp. 497-506, 1997.
  11. A. Kumar, V. J. Tsotras and C. Faloutsos, "Designing Access Methods for Bitemporal Databases", IEEE Transactions on Knowledge and Data Engineering, vol. 10, no. 1, pp. 1-20, 1998.
  12. M. A. Nascimento, J. R. O. Silva and Y. Theodoridis, "Evaluation of Access Structures for Discretely Moving Points", Proceedings of the 1st International Symposium on Spatiotemporal Database Management, pp. 171-188, 1999.
  13. Mengchu Cai and Peter Revesz, "Parametric R-Tree: An Index Structure for Moving Objects", Proceedings of the 10th International Conference on Management of Data, 2000.
  14. S. Saltenis, C. S. Jensen, S. Leutenegger and M. Lopez, "Indexing the Positions of Continuously Moving Objects", Proceedings of ACM SIGMOD Conference on Management of Data, pp. 331-342, 2000.
  15. Y. Tao and D. Papadias, "Efficient Historical R-Trees", Proceedings of the 13th International Conference on Scientific and Statistical Database Management, pp. 223-232, 2001.
  16. G. Kollio et. al. , "Indexing Animated Objects Using Spatiotemporal Access Methods", IEEE Transactions on Knowledge and Data Engineering, vol. 13, no. 5, pp. 758-777, 2001.
  17. Dongseop Kwon, Sangjun Lee and Sukho Lee, "Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree", Proceedings of the 3rd International Conference on Mobile Data Management, pp. 113–120, 2002.
  18. S. Prabhakar et. al. , "Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects", IEEE Transactions on Computers, vol. 51, no. 10, pp. 1124-1140, 2002.
  19. Jianhua Qiu, Xuebing Tang and Huaguo Huang, "An Index Structure based on Quad-Tree and R*-Tree—R*Q-Tree", Journal of Computer Applications, vol. 23, no. 8, pp. 124-126, 2003.
  20. Y. Xia and S. Prabhakar, "Q+R-Tree: Efficient Indexing for Moving Object Databases", Proceedings of 8t hInternational Conference on Database Systems for Advanced Applications, pp. 175-182, 2003.
  21. Yufei Tao, Dimitris Papadias and Jimeng Sum, "The TPR*-tree: An Optimized Spatio-Temporal Access Method for Predictive Queries", Proceedings of the 29th International Conference on Very Large Data Bases, pp. 790-801, 2003.
  22. E. Frentzos, "Indexing Objects Moving on Fixed Networks", Proceedings of the 8th International Symposium on Spatial and Temporal Databases, pp. 289-305,2003.
  23. L. Arge, M. deBerg, H. J. Haverkort and K. Yi, "The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree", Proceedings of ACM SIGMOD Conference on Management of Data, pp. 347-358, 2004.
  24. V. T. Almeida and R. H. Guting, "Indexing the Trajectories of Moving Objects in Networks", Proceedings of the 16th International Conference on Scientific and Statistical Database Management, pp. 115-118, 2004.
  25. Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos and Yannis Theodoridis, R-Trees: Theory and Applications, London: Springer, 1st Edition, 2006.
  26. TAN Ning and SHI Yue-xiang, "Optimization Research of Multi-Dimensional Indexing Structure of R*-Tree", Proceedings of the International Conference on Information Technology and Applications, pp. 612-615, 2009
  27. P. Anandha Kumar et. al. , "Location Based Hybrid Indexing Structure - R k-d Tree", Proceedings of the 1st International Conference on Integrated Intelligent Computing, pp. 140-145, 2010.
  28. Guobin Li and Jine Tang, "A New HR-Tree Index based on Hash Address", Proceedings of the 2nd International Conference on Signal Processing Systems, pp. 35-38, 2010.
  29. Guobin Li and Jine Tang, "A New DR-tree K-Nearest Neighbor Query Algorithm based on Direction Relationship", Proceedings of the International Conference on Environmental Science and Information Application Technology, pp. 246-250, 2010.
  30. Guobin Li and Jine Tang, "A New Method about Spatial Data Query based on the R*Q-Tree", Proceedings of the 6th International Conference on Neural Computing, pp. 1044-1047, 2010.
  31. Mehdi Sharifzadeh and Cyrus Shahabi, "VoR-Tree: R-Trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries", Journal Proceedings of VLDB Environment, vol. 3, no. 1, pp. 1231-1243, 2010.
  32. Amer Al-Badarneh and Abdullah Al-Alaj, "A Spatial Index Structure using Dynamic Recursive Space Partitioning", Proceedings of the International Conference on Innovations in Information Technology, pp. 255-260, 2011.
  33. Pan Jin and Quanyou Song, "A Novel Index Structure R*Q-Tree based on Lazy Splitting and Clustering", Proceedings of the International Conference on Computer Science and Automation Engineering, pp. 405-407, 2011.
  34. Quanyou Song, "An Improved Spatial Index based on the R*Q-Tree", Proceedings of the International Conference on Business Management and Electronic Information, pp. 786-789, 2011.
Index Terms

Computer Science
Information Sciences

Keywords

R-tree Spatial Index Spatio-temporal Index R-tree Variants

Powered by PhDFocusTM