Estructuras de datos multidimensionales: un análisis de desempeño
DOI:
https://doi.org/10.17533/udea.redin.325924Keywords:
Estructuras de datos multidimensionales, procesamiento de consultas, GRID FILE, árbol KDB, árbol R.Abstract
En los sistemas manejadores de datos multidimensionales es necesario construir índices para agilizar las consultas. Debido a la existencia de múltiples estructuras definidas para representar los índices, se dificulta la decisión acerca de cuál estructura utilizar. Este artículo muestra los resultados de una evaluación del proceso de consulta por rangos sobre varias estructuras de datos multidimensionales, con base en el comportamiento del número de accesos a disco. Las estructuras de datos evaluadas fueron: el GR.ID FILE, el árbol KDB y el árbol R. Los experimentos revelan que para rangos pequeños, independientemente de la escalabilidad, el comportamiento del número de accesos a disco mostrado por el árbol R es similar al del GRJD FILE. A medida que la extensibilidad aumenta, el árbol R muestra un menor número de accesos a disco. Para el caso del GRJD FILE, el número de accesos a disco crece linealmente con una pendiente alta, a medida que aumenta la extensibilidad, lo que limita su uso a rangos pequeños. En el caso del árbol KDB, el comportamiento del número de accesos a disco no depende de la extensibilidad. Del resultado del experimento se deduce que de las tres estructuras evaluadas, la más recomendable, para el propósito de disminuir el número de accesos a disco en consultas por rango, es la estructura del árbol R.Downloads
References
Beckrnann N., et al. "The R •-tree: an efficient and roust access method for points and rectangles". ACM SIGMOD, mayo de 1990. pp 322-331. DOI: https://doi.org/10.1145/93605.98741
Guttman A. "R-trees: a dynamic index structure for spatial searching". Proc. ACM SJCMOD, Junio de 1984. pp. 47-57. DOI: https://doi.org/10.1145/971697.602266
Karnel, l., et al. ··on packing R-trees". 1n Proc. 2nd lnternational Conferenc e on lnformation and Knowledge Manageme.tll. Arlington, V A. noviembre de 1993. pp. 490-499.
Kamel, l., et al. "1-lilben R-tree Using Fractals". In Proc 20th lnternational Conference 011 VLDB. Santiago Chile, 1994. pp. 500-509.
Sellis, T., et al. "The R•-tree: a dynamic index for multi-dimensional objects". In Proc 13th lnternatio11al Conference 011 VLDB. England, September, 1987. pp. 507-518.
Roussopoulos, N .• et al. "Direct Spatial on Pictorial Databascs Using Packed R-trees·•. Proc. ACM SICMOD. May, 1985. DOI: https://doi.org/10.1145/318898.318900
1-Iinrichs, K. "'Toe Grid File System: implementation and case studies for applications". Dissertatio11 No. 7734, Eidgenossische Technische 1-lochschule, Zuerich. 1985.
Robinson, J.T. "The KDB Tree: Search Structure for Large Multidimensional Dynamic Indexes". Proc. ACM SJCMOD 1981. Int Conference Ma11ageme11t of Data. Abril de 1981. pp. 10-18. DOI: https://doi.org/10.1145/582318.582321
NievergelT, J., et al. "The Grid File: An adaptable, symmetric multikey file structure"'. ACM tra11s. Database System. 9, 1. Marzo de 1984. pp 38-71. DOI: https://doi.org/10.1145/348.318586
Gaede, V. et al. Multidime11sional Access Methods. Berlín. 1997.
Downloads
Published
How to Cite
Issue
Section
License
Revista Facultad de Ingeniería, Universidad de Antioquia is licensed under the Creative Commons Attribution BY-NC-SA 4.0 license. https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en
You are free to:
Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material
Under the following terms:
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
NonCommercial — You may not use the material for commercial purposes.
ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
The material published in the journal can be distributed, copied and exhibited by third parties if the respective credits are given to the journal. No commercial benefit can be obtained and derivative works must be under the same license terms as the original work.
Twitter