¿De qué sirven los grupos, monoides y anillos en los cálculos de la base de datos?

¿Por qué una empresa como Twitter estaría interesada en conceptos algebraicos como grupos, monoides y anillos? Vea su repositorio en github: twitter / algebird .

Todo lo que pude encontrar es:

Implementaciones de monoides para algoritmos de aproximación interesantes, como el filtro Bloom , HyperLogLog y CountMinSketch . Estos le permiten pensar en estas operaciones sofisticadas como si fueran números, y sumarlas en hadoop o en línea para producir estadísticas y análisis potentes.

y en otra parte de la página de GitHub:

Originalmente se desarrolló como parte de la API de matriz de Scalding, donde las matrices tenían valores que son elementos de monoides , grupos o anillos . Posteriormente, estaba claro que el código tenía una aplicación más amplia dentro de Scalding y en otros proyectos dentro de Twitter.

¿Cuál podría ser esta aplicación más amplia? dentro de Twitter y por interés general?

Parece que las agregaciones de composición de bases de datos tienen una estructura de tipo monoide.

La misma pregunta sobre Quora: ¿Cuál es el interés de Twitter en el álgebra abstracta (con álgebird)?

Tengo experiencia en matemáticas pero no soy informático. Sería genial tener usos en el "mundo real" de monoides y semi-grupos. Normalmente se consideran construcciones teóricas inútiles y se ignoran en muchos cursos de álgebra abstracta (por falta de algo interesante que decir).

La respuesta principal es que al explotar la estructura de semi-grupos, podemos construir sistemas que se paralelizan correctamente sin conocer la operación subyacente (el usuario promete asociatividad).

Al usar Monoids, podemos aprovechar la dispersión (tratamos con muchas matrices dispersas, donde casi todos los valores son cero en algunos Monoid).

Al usar Rings, podemos hacer una matriz de multiplicación sobre otras cosas que no sean números (que en ocasiones lo hemos hecho).

El proyecto algebird en sí (así como el historial de problemas) explica con bastante claridad lo que está sucediendo aquí: estamos creando muchos algoritmos para la agregación de grandes conjuntos de datos, y el aprovechamiento de la estructura de las operaciones nos da una victoria en el lado de los sistemas (que suele ser el punto crítico cuando se intenta producir algoritmos en miles de nodos).

Resuelva los problemas del sistema una vez para cualquier Semigroup / Monoid / Group / Ring, y luego puede conectar cualquier algoritmo sin tener que pensar en Memcache, Hadoop, Storm, etc.

Los monoides son ubicuos en la programación, solo que la mayoría de los programadores no los conocen.

• Operaciones numéricas como suma y multiplicación.
• Multiplicación matricial.
• Básicamente, todas las estructuras de datos tipo colección forman monoides, donde la operación monoidal es concatenación o unión. Esto incluye listas, conjuntos, mapas de claves de valores, varios tipos de árboles, etc.
• $A$$A\to A$$A$$A$

$a\cdot b$$a$$b$ wrt algún orden dado.

Como los monoides son tan generales, permiten escribir funciones muy genéricas. Por ejemplo, plegarse sobre una estructura de datos se puede expresar como mapear cada uno de sus elementos a un monoide y luego usar la operación monoidal para combinarlos en un solo resultado.

$\underbrace{a\cdot\ldots\cdot a}_{n-\mbox{times}}$$O(\log n)$

• exponenciación rápida de números;
• $O(\log n)$ multiplicaciones );
• $O(1)$$O(\log(\min(n_1,n_2)))$ .
• etc.

Para obtener más ejemplos, consulte Ejemplos de monoides / semigrupos en programación .

Un problema importante en los sistemas de archivos distribuidos ( DFS ) es generar archivos a partir de bloques distribuidos. El área del código de borrado de la teoría de la información y el álgebra (grupos, anillos, álgebra lineal, ...) se usa ampliamente en sistemas de archivos distribuidos tolerantes a fallas, por ejemplo, en HDFS RAID (Sistema de archivos basado en Hadoop). Las redes sociales y las empresas en la nube se basan ampliamente en DFS, por lo que necesitan personas que sean expertos en álgebra y código de borrado para diseñar sistemas mejores y de alto rendimiento (como los códigos Reed-Solomon , etc.).

Este también es un buen póster para su aplicación (álgebra) en el almacenamiento en la nube: códigos nuevos para el almacenamiento en la nube

Si tu pregunta es

¿Cuáles son ejemplos de grupos, monoides y anillos en la computación?

$+$$\min$$\cdot$$+$

Si bien esto puede parecer solo teórico desde una perspectiva algebraica, nos permite utilizar bibliotecas de álgebra lineal muy optimizadas para problemas de gráficos. Combinatorial BLAS es una de esas bibliotecas.

El conjunto de todas las palabras sobre un alfabeto finito junto con la concatenación forma el monoide libre $(\Sigma^*, \cdot)$. Por lo tanto, todo el campo del lenguaje formal se puede ver a través del lente algebraico, y a veces se enseña así.

A cambio, las consideraciones sobre los lenguajes formales han dado lugar al analizador Earley que se puede extender para analizar en semirrelaciones . Esto es útil en el procesamiento del lenguaje natural y otras áreas que usan modelos estocásticos para los idiomas (formales).

Tengo experiencia en matemáticas pero no soy informático. Sería genial tener usos en el "mundo real" de monoides y semi-grupos. Normalmente se consideran construcciones teóricas inútiles y se ignoran en muchos cursos de álgebra abstracta (por falta de algo interesante que decir).

Hay demasiado interesante para decir. Sin embargo, es más un tema de matemática discreta y combinatoria que para álgebra abstracta y análisis, al menos para los temas menos triviales. También está la cuestión de cuánto tiene que saber sobre un determinado tema antes de poder decirle a otra persona que sería un tema matemático interesante relacionado con los monoides y los semigrupos. Por ejemplo, encuentro interesantes los siguientes temas (relacionados con semigrupos):

• semigrupos finitos y teoría de Krohn-Rhodes
• simetrías parciales, semigrupos inversos, grupoides y cuasicristales
• semirremolques y geometría tropical
• órdenes parciales y funciones de Möbius
• funciones submodulares y descomposiciones (como Dulmage-Mendelsohn)

¿Sé mucho sobre cada uno de estos temas? Probablemente no. También hay muchos más temas matemáticos relacionados con monoides y semigrupos, algunos de ellos son más internos a la teoría del semigrupo en sí (como las relaciones de Green), otros son más generales y no específicos de los semigrupos (semigrupos universales, teoremas de homomorfismo e isomorfismo, estructuras de cociente y congruencias), pero también importante desde un punto de vista matemático. Los temas que he citado anteriormente en su mayoría tienen aplicaciones del "mundo real", pero hay más temas relacionados que también tienen aplicaciones del "mundo real".

Lo anterior no es una respuesta a la pregunta real, sino que solo aborda el "... normalmente se consideran construcciones teóricas inútiles ... por falta de algo interesante que decir ..." comentario. Así que enumeré algunos puntos "interesantes", afirmó que en su mayoría tienen aplicaciones del "mundo real", y ahora Hi-Angel solicita un poco de información sobre esas aplicaciones. Pero debido a que "hay demasiado interesante para decir", no esperes demasiado de esa información: el teorema de Krohn-Rhodes es un teorema de descomposición para semigrupos finitos. Sus aplicaciones implican la interpretación del producto de la corona como una especie de composición (de transductores) en conexión con la teoría de autómatas y lenguajes regulares, y ocurre en la clasificación de lenguajes regulares usando pseudovariedadesMark V Lawson: dos clases magistrales y material de base contenían (404 ahora) buen material sobre Semigrupos inversos . La base de sus aplicaciones es su conexión con el semigrupo inverso simétrico , es decir, el conjunto de todas las biyecciones parciales en un conjunto. También se puede comenzar con caracterizaciones algebraicas básicas de semigrupos inversos, pero este enfoque corre el riesgo de descuidar las conexiones a órdenes parciales que son importantes para muchas aplicaciones. Algún día tendré que bloguear sobre una aplicación específica de semigrupos inversos como "jerarquía" utilizada para comprimir diseños de semiconductores . Las aplicaciones de semirremolques ya se han descrito en las otras respuestas (y la geometría tropical nos llevaría lejos de la informática). Debido a que los monoides y los semigrupos también están relacionados con órdenes parciales, temas tan agradables como Möbius funcionan como se describe en Combinatorics: The Rota Way también están relacionados. Y luego también se relacionan temas de Matrices y Matroids para el Análisis del sistema como la descomposición de Dulmage-Mendelsohn , que fueron una de mis motivaciones para estudiar la teoría de la red (y las estructuras jerárquicas ocultas).