Etiquetas del centro

En informática , las etiquetas de hub o el algoritmo de etiquetado de hub son una técnica de aceleración que consume muchos menos recursos que la tabla de búsqueda, pero sigue siendo extremadamente rápida para encontrar las rutas más cortas entre nodos en un grafo , que puede representar, por ejemplo, redes de carreteras. ^{[ 1 ]}

Este método permite, como máximo, con dos sentencias SELECT y el análisis de dos cadenas de caracteres, calcular la ruta más corta entre dos vértices de un grafo. Para un grafo orientado como un grafo de carreteras, esta técnica requiere el cálculo previo de dos tablas a partir de estructuras construidas mediante el método de jerarquías de contracción . Finalmente, estas dos tablas calculadas tendrán tantas filas como nodos haya en el grafo. Para cada fila (cada nodo), se calculará una etiqueta.

Una etiqueta es una cadena de texto que contiene la información de distancia entre el nodo actual (el nodo de la fila) y todos los demás nodos a los que se puede acceder mediante una búsqueda ascendente en la estructura multinivel relativa. La ventaja de estas distancias es que todas representan las rutas más cortas.

Así pues, para futuras consultas, la búsqueda de la ruta más corta comenzará desde el origen en la primera tabla y el destino en la segunda. A partir de ahí, se buscarán dentro de las etiquetas los nodos comunes con la información de distancia asociada. Solo se conservará la suma más pequeña de distancias como resultado de la ruta más corta.

• Nodos de tránsito
• Jerarquías de contracción
• Dimensión de la autopista