Resumen

La aplicación de una tecnología de compresión de datos de grafos adecuada para almacenar y manipular datos de grafos con decenas de miles de nodos y aristas es un requisito previo para analizar datos de grafos a gran escala. El esquema tradicional de representación del árbol K2 divide mecánicamente la matriz de adyacencia, lo que provoca la división del intervalo denso, con la consiguiente sobrecarga adicional de almacenamiento. A medida que aumenta el tamaño de los datos del grafo, el tiempo de consulta del árbol K2 sigue aumentando. Teniendo en cuenta los problemas anteriores, proponemos un esquema de representación compacta de datos de grafos basado en la agrupación en malla y el árbol K2. En primer lugar, dividimos la matriz de adyacencia en varias cuadrículas del mismo tamaño. A continuación, filtramos y fusionamos continuamente estas cuadrículas hasta que la densidad de las mismas satisface el umbral de densidad dado. Por último, para cada cuadrícula grande que cumple la densidad, se realiza una representación compacta del árbol K2. Sobre esta base, presentamos el algoritmo de consulta de nodos vecinos relevantes. Los resultados experimentales muestran que, en comparación con el mejor algoritmo K2-BDC actual, nuestro esquema puede lograr una mejor relación entre tiempo y espacio.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:árbol, matriz de adyacencia, datos de grafos, tecnología adecuada de compresión de datos de grafos, algoritmo de consulta de nodos vecinos relevantes, sobrecarga de almacenamiento adicional, esquema de representación compacta, mejor k2 actual, aumentos de datos de grafos, datos de grafos a escala
• Keywords:tree, adjacency matrix, graph data, appropriate graph data compression technology, relevant node neighbor query algorithm, additional storage overhead, compact representation scheme, current best k2, graph data increases, scale graph data