Estructuras de datos multidimensionales: un análisis de desempeño

Authors

  • Luis Hernando Silva-Flórez Universidad de Antioquia
  • Ana Clara Vélez-Torres Universidad de Antioquia

Keywords:

Estructuras de datos multidimensionales, procesamiento de consultas, GRID FILE, árbol KDB, árbol R.

Abstract


En los sistemas manejadores de datos multidimensionales es necesario cons­truir índices para agilizar las consultas. Debido a la existencia de múltiples es­tructuras 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, independiente­mente 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 dis­co. 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úme­ro de accesos a disco no depende de la extensibilidad. Del resultado del experi­mento 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.
|Abstract
= 80 veces | PDF (ESPAÑOL (ESPAÑA))
= 18 veces|

Downloads

Download data is not yet available.

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.

Guttman A. "R-trees: a dynamic index structure for spatial searching". Proc. ACM SJCMOD, Junio de 1984. pp. 47-57.

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. San­tiago 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.

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.

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.

Gaede, V. et al. Multidime11sional Access Methods. Berlín. 1997.

Published

2000-11-08

How to Cite

Silva-Flórez, L. H., & Vélez-Torres, A. C. (2000). Estructuras de datos multidimensionales: un análisis de desempeño. Revista Facultad De Ingeniería Universidad De Antioquia, (21), 102–115. Retrieved from https://revistas.udea.edu.co/index.php/ingenieria/article/view/325924