Representación gráfica comprimida?

Question

Estoy trabajando en un proyecto paralelo ahora que implica la codificación de todos los enlaces entre las páginas de Wikipedia. He extraído esta información en un disco, pero el uso de memoria requerido para codificar la estructura de este gráfico es bastante ridículo: hay millones de nodos y decenas de millones de enlaces. Si bien esta estructura cabe en la memoria, no estoy seguro de qué haría si hubiera, digamos, mil millones de enlaces o mil millones de páginas.

Mi pregunta es: ¿hay alguna manera de comprimir sin pérdidas un gráfico demasiado grande para caber en la memoria para que quepa en la memoria? De lo contrario, ¿existe un buen algoritmo con pérdidas que, para alguna definición de "estructura", no pierda demasiada estructura del gráfico original?

Answer 1

Los gráficos como los gráficos de enlaces y los gráficos sociales están muy bien estudiados y suelen tener propiedades estadísticas que permiten representaciones comprimidas eficientes.

Una de estas propiedades, por ejemplo, es que para bordes salientes la codificación diferencial de la lista de adyacencia tiene una baja distribución de potencia, es decir, hay muchos valores muy pequeños y muy pocos valores grandes, por lo que la mayoría universal codes funcionan bastante bien. En particular, la clase de zeta codes es probablemente óptima en este contexto, y en el documento los autores comprimieron el gráfico de enlace de un pequeño rastreo web con aproximadamente 3 bits por enlace.

Su código (para Java, Python y C++) es available in their webpage como un marco de compresión de gráficos, por lo que debería poder experimentar con él sin mucha codificación.

Este algoritmo es algo viejo (2005) y ha habido avances en el campo, pero no tengo los indicadores para los documentos en este momento, las mejoras no son significativas y no creo que haya ninguna código disponible y probado que los implementa.

Answer 2

¿Qué hay de simplemente escribir sus nodos, enlaces y asociaciones a un sistema de base de datos escalable existente (MySQL, SQL Server, Oracle, etc.)? Puede crear índices y procedimientos almacenados para un procesamiento de nivel de base de datos más rápido, si es necesario.

Si no puede seguir esta ruta por alguna razón, tendrá que ingresar y sacar datos de la página (¡como lo hacen los sistemas DB!). Comprimir los datos es una ayuda de banda a corto plazo en muchos casos. Si por alguna razón no puede elevar el techo RAM, solo se está comprando tiempo limitado, por lo que le recomiendo no comprimirlo.

Answer 3

En términos generales, si tiene N nodos y un promedio de X enlaces de salida por nodo, X mucho más pequeño que N, necesitará XN en N bits de información para representar esto, a menos que pueda encontrar patrones en la estructura de enlace (que luego puedes aprovechar para reducir la entropía). XN In N está dentro de un orden de magnitud de la complejidad de su lista de adyacencia de 32 bits.

hay algunos trucos que usted puede hacer para reducir el tamaño un poco más:

• códigos de Huffman para codificar Uso destinos de vínculos. Asigne códigos más cortos a páginas de referencia frecuente y códigos más largos a páginas poco frecuentes.
• Encuentra una manera de dividir el conjunto de páginas en clases. Almacene cada enlace entre páginas dentro de la misma clase que "0" + "# dentro de la clase"; enlaces entre páginas en diferentes categorías como "1" + "clase de destino" + "# dentro de clase".

Vale la pena consultar los enlaces de Giuseppe, pero solo el experimento le dirá qué tan bien esos algoritmos son aplicables a Wikipedia.

Answer 4

Si no necesita mutabilidad, eche un vistazo a cómo BGL representa un gráfico en un compressed sparse row format. De acuerdo con los documentos, "minimiza el uso de memoria a O (n + m) donde n y m son el número de vértices y bordes, respectivamente". Boost Graph Library incluso tiene an example que refleja su caso de uso.

Antes de ir más lejos con esto, realmente debe averiguar cómo piensa interrogar su gráfico. ¿Necesita enlaces que apuntan a la página, así como enlaces de una página? ¿Necesita poder encontrar de manera eficiente la cantidad de enlaces en una página determinada? Para obtener una lista bien pensada de operaciones gráficas básicas, consulte Boost Graph Library's (BGL) concepts. Puede asignar esto a los requisitos para diferentes algoritmos. Dijkstra's shortest path, por ejemplo, requiere un gráfico que modele "Gráfico de lista de vértices" y "Gráfico de incidencia".

Answer 5

Hace un tiempo formaba parte de a paper sobre la compresión de gráficos web para que cupieran en la memoria. Lo reducimos a alrededor de 6 bits por enlace.

Answer 6

En su caso, usted está tratando de comprimir un gráfico SINGLE en una memoria en lugar de una familia de gráficos general y grande. Cuando solo tiene un gráfico para comprimir, puede encontrar cualquier presentación algorítmica arbitraria para él y esto se convierte en un problema de Kolmogorov complexity. En general, no puede comprimir gráficos aleatorios de manera eficiente porque son aleatorios y, por lo tanto, no se pueden predecir y, cuando no se pueden predecir, no se pueden comprimir. Esto proviene de la teoría de la información básica; es lo mismo que no puedes comprimir imágenes con ruido aleatorio.

Suponga que tiene 2 (mil millones) páginas y cada uno tiene exactamente 2 enlaces salientes y que los enlaces son verdaderamente distribuida al azar. Los enlaces en cada página representan casi 16 * 30 bits de información (no totalmente porque los 16 enlaces son todos distintos y esto agrega una cantidad minúscula de redundancia). Entonces tiene 2 * 16 * 30 = 2 * 120 = 15 GB de información allí, y la teoría de la información dice que no puede encontrar una representación GENERAL más pequeña. Necesita usar la estructura particular del gráfico de Wikipedia para obtener debajo de ese límite inferior teórico de la información.