CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Comparison of Advance Tree Data Structures

by Parth Patel, Deepak Garg
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 41 - Number 2
Year of Publication: 2012
Authors: Parth Patel, Deepak Garg
10.5120/5512-7504

Parth Patel, Deepak Garg . Comparison of Advance Tree Data Structures. International Journal of Computer Applications. 41, 2 ( March 2012), 11-21. DOI=10.5120/5512-7504

@article{ 10.5120/5512-7504,
author = { Parth Patel, Deepak Garg },
title = { Comparison of Advance Tree Data Structures },
journal = { International Journal of Computer Applications },
issue_date = { March 2012 },
volume = { 41 },
number = { 2 },
month = { March },
year = { 2012 },
issn = { 0975-8887 },
pages = { 11-21 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume41/number2/5512-7504/ },
doi = { 10.5120/5512-7504 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:28:33.789370+05:30
%A Parth Patel
%A Deepak Garg
%T Comparison of Advance Tree Data Structures
%J International Journal of Computer Applications
%@ 0975-8887
%V 41
%N 2
%P 11-21
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

B-tree and R-tree are two basic index structures; many different variants of them are proposed after them. Different variants are used in specific application for the performance optimization. In this paper different variants of B-tree and R-tree are discussed and compared. Index structures are different in terms of structure, query support, data type support and application. Index structure's structures are discussed first. B-tree and its variants are discussed and them R-tree and its variants are discussed. Some structures example is also shown for the more clear idea. Then comparison is made between all structure with respect to complexity, query type support, data type support and application.

References
  1. A. Guttman," R-trees: A Dynamic Index Structure for Spatial Searching" Proc. ACM SIGMOD, pp. 47–57, 1984.
  2. B. Bloom, "Space/Time Trade Offs in Hash Coding with Allowable Errors", Communication of ACM, vol. 13, no. 7, pp. 422-426, 1970.
  3. Douglas Comer, "The Ubiquitous B-Tree", ACM Computing Surveys, Vol 11, Fasc. 2, pp. 121–137, 1979.
  4. Hung-Yi Lin, "A Compact Index Structure with High Data Retrieval Efficiency", International Conference on Service Systems and Service Management, pp. 1–5, 2008.
  5. I. Kamel, C. Faloutsos, "Hilbert R-tree: An improved R-tree using fractals", Proc. 20th International Conference on Very Large Data Bases, pp. 500–509, 1994.
  6. Knuth, Donald, "Sorting and Searching, The Art of Computer Programming", Addison-Wesley, ISBN 0-201-89685-0 , Vol. 3 (Second ed. ), Section 6. 2. 4, Multiway Trees, pp. 481–491, 1998.
  7. Mao Huaqing, Bian Fuling, "Design and Implementation of QR+Tree Index Algorithms", International Conference on Digital Object Identifier, pp. 5987 - 5990, 2007.
  8. Mark Russinovich, "Inside Win2K NTFS, Part 1", Microsoft Developer Network, Retrieved 2008-04-18.
  9. N. Beckmann, H. P. Kriegel, R. Schneider, B. Seeger, "The R*-tree: an efficient and robust access method for points and rectangles", Proc. ACM SIGMOD international conference on Management of data, pp. 322-331, 1990.
  10. Paolo Ciaccia, Marco Patella, Pavel Zezula, "M-tree An Efficient Access Method for Similarity Search in Metric Spaces", Proc. 13th International Conference on Very Large Data Bases, 1997.
  11. R. A. Finkel, J. L. Bentley, "Quad trees: a data structure for retrieval on composite keys", Acta Informatica, vol 4, pp. ll-9, 1974.
  12. R. Bayer, E. McCreight, "Organization and Maintenance of Large Ordered Indexes", Acta Informatica, Vol. 1, Fasc. 3, pp. 173–189, 1972.
  13. Ramakrishnan Raghu, Gehrke Johannes, "Database Management Systems", McGraw-Hill Higher Education, edi. 2nd, pp. 267, 2000.
  14. Stefan Berchtold, D. A. Keim, Hans-Peter Kriegel, "The X-Tree: An Index Structure for High-Dimensional Data", Proc. 22th International Conference on Very Large Data Bases, pp. 28–39, 1996.
  15. Su Chen, Beng Chin Ooi, Kian-Lee Tan, M. A. Nascimento, "ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects", Proc. ACM SIGMOD international conference on Management of data, 2008.
  16. Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos, "The R+-Tree: A Dynamic Index for Multi-Dimensional Objects", Proc. VLDB 13th International Conference on Very Large Data Bases, pp. 507-518, 1987.
  17. Tei-Wei Kuo, Chih-Hung Wei, Kam-Yiu Lam "Real-Time Data Access Control on B-Tree Index Structures Data Engineering", Proc. 15th International Conference on Data Engineering, pp. 458 – 467, 1999.
  18. V. Markl "MISTRAL: Processing Relational Queries using a Multidimensional Access Technique", Infix Verlag, ISBN 3-89601-459-5, 1999.
  19. Yu Hua, Bin Xiao, Jianping Wang, "BR-Tree: A Scalable Prototype for supporting Multiple Queries of Multidimensional Data", IEEE Transactions on Computers, vol. 58, Issue 12, pp. 1585–1598, 2009.
  20. Ajit Singh, Dr. Deepak Garg "Implementation and Performance Analysis of Exponential Tree Sorting" International Journal of Computer Applications ISBN: 978-93-80752-86-3 Volume 24– No. 3, pp. 34-38 June 2011.
Index Terms

Computer Science
Information Sciences

Keywords

Index Structures B-tree R-tree Variants Query Type Complexity

Powered by PhDFocusTM