Estructuras de datos multidimensionales: un análisis de desempeño
DOI:
https://doi.org/10.17533/udea.redin.325924Palabras clave:
Estructuras de datos multidimensionales, procesamiento de consultas, GRID FILE, árbol KDB, árbol R.Resumen
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.Descargas
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Los artículos disponibles en la Revista Facultad de Ingeniería, Universidad de Antioquia están bajo la licencia Creative Commons Attribution BY-NC-SA 4.0.
Eres libre de:
Compartir — copiar y redistribuir el material en cualquier medio o formato
Adaptar : remezclar, transformar y construir sobre el material.
Bajo los siguientes términos:
Reconocimiento : debe otorgar el crédito correspondiente , proporcionar un enlace a la licencia e indicar si se realizaron cambios . Puede hacerlo de cualquier manera razonable, pero no de ninguna manera que sugiera que el licenciante lo respalda a usted o su uso.
No comercial : no puede utilizar el material con fines comerciales .
Compartir igual : si remezcla, transforma o construye a partir del material, debe distribuir sus contribuciones bajo la misma licencia que el original.
El material publicado por la revista puede ser distribuido, copiado y exhibido por terceros si se dan los respectivos créditos a la revista, sin ningún costo. No se puede obtener ningún beneficio comercial y las obras derivadas tienen que estar bajo los mismos términos de licencia que el trabajo original.
Twitter