Jakie są zastosowania grup, monoidów i pierścieni w obliczeniach baz danych?

Dlaczego firma taka jak Twitter byłaby zainteresowana koncepcjami algebraicznymi, takimi jak grupy, monoidy i pierścienie? Zobacz ich repozytorium na github: twitter / algebird .

Mogłem tylko znaleźć:

Implementacje Monoidów dla interesujących algorytmów aproksymacyjnych, takich jak filtr Bloom , HyperLogLog i CountMinSketch . Pozwalają ci myśleć o tych wyrafinowanych operacjach, takich jak liczby, i dodawać je w hadoopie lub Internecie, aby tworzyć potężne statystyki i analizy.

oraz w innej części strony GitHub:

Został pierwotnie opracowany jako część API Matrix Scaldinga , gdzie Matryce miały wartości, które są elementami Monoidów , Grup lub Pierścieni . Następnie stało się jasne, że kod ma szersze zastosowanie w Scaldingu i innych projektach na Twitterze.

Czym może być ta szersza aplikacja? na Twitterze i w interesie ogólnym?

Wygląda na to, że agregacje kompozycji baz danych mają strukturę monoidopodobną.

To samo pytanie dotyczące Quory: Jakie są zainteresowania Twittera algebrą abstrakcyjną (z algebirem)?

Mam doświadczenie matematyczne, ale nie jestem informatykiem. Byłoby wspaniale mieć zastosowanie w świecie rzeczywistym monoidów i półgrup. Są one zwykle uważane za bezużyteczne konstrukcje teoretyczne i są ignorowane w wielu abstrakcyjnych kursach algebry (z powodu braku czegoś interesującego do powiedzenia).

Główną odpowiedzią jest to, że wykorzystując strukturę półgrupową, możemy budować systemy, które działają poprawnie równolegle, nie znając operacji podstawowej (użytkownik obiecuje skojarzenie).

Używając Monoidów, możemy skorzystać z rzadkości (mamy do czynienia z wieloma rzadkimi macierzami, w których prawie wszystkie wartości są zerowe w niektórych Monoidach).

Korzystając z pierścieni, możemy dokonywać mnożenia macierzy na rzeczach innych niż liczby (co czasami zrobiliśmy).

Sam projekt algebird (a także historia problemów) dość jasno wyjaśnia, co się tutaj dzieje: budujemy wiele algorytmów do agregacji dużych zestawów danych, a wykorzystanie struktury operacji daje nam zwycięstwo po stronie systemowej (co zwykle stanowi problem przy próbie produkcji algorytmów na tysiącach węzłów).

Rozwiązuj problemy systemowe raz dla dowolnej półgrupy / monoid / grupy / pierścienia, a następnie możesz podłączyć dowolny algorytm bez konieczności myślenia o Memcache, Hadoop, Storm itp.

Monoidy są wszechobecne w programowaniu, tyle że większość programistów o nich nie wie.

• Operacje liczbowe, takie jak dodawanie i mnożenie.
• Mnożenie macierzy.
• Zasadniczo wszystkie struktury danych podobne do kolekcji tworzą monoidy, gdzie operacją monoidalną jest konkatenacja lub połączenie. Obejmuje to listy, zestawy, mapy kluczy do wartości, różne rodzaje drzew itp.
• Dla danego typu funkcje A → A wraz z funkcją tożsamości na A tworzą monoid endomorfizmu $A$$A\to A$$A$$A$

Niektóre inne operacje nie tworzą monoidów, ale półgrupy. Dobrym przykładem jest poszukiwanie minimalnego elementu sekwencji elementów: reprezentuje minimum a i b wrt pewnej podanej kolejności.$a\cdot b$$a$$b$

Ponieważ monoidy są tak ogólne, pozwalają na pisanie bardzo ogólnych funkcji. Na przykład zawinięcie w strukturze danych można wyrazić jako odwzorowanie każdego jej elementu na monoid, a następnie użycie operacji monoidalnej w celu połączenia ich w jeden wynik.

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

• szybki potęgowanie liczb;
• $O(\log n)$
• $O(1)$$O(\log(\min(n_1,n_2)))$
• itp.

Aby uzyskać więcej przykładów, zobacz Przykłady monoidów / półgrup w programowaniu .

Jednym z ważnych problemów w rozproszonych systemach plików ( DFS ) jest generowanie plików z rozproszonych bloków. Obszar kodu usuwania z teorii informacji i algebry (grupy, pierścienie, algebra liniowa, ...) jest szeroko stosowany w rozproszonych systemach plików odpornych na uszkodzenia, na przykład w HDFS RAID (system plików oparty na Hadoop). Firmy działające w sieciach społecznościowych i w chmurze są w dużej mierze oparte na DFS, dlatego potrzebują ludzi, którzy są mistrzami w algebrze i kodzie usuwania, aby projektować lepsze i wydajniejsze systemy (takie jak kody Reeda-Solomona itp.).

Jest to również dobry plakat dla ich aplikacji (algebry) w magazynie w chmurze: Nowe kody dla magazynu w chmurze

Jeśli twoje pytanie brzmi

Jakie są przykłady grup, monoidów i pierścieni w obliczeniach?

jeden przykład, który mogę wymyślić z ręki, dotyczy algorytmów wyszukiwania ścieżek w teorii grafów. Jeśli zdefiniujemy semowanie za pomocą jako i jako , wówczas możemy użyć mnożenia macierzy z macierzą przyległości, aby znaleźć wszystkie pary najkrótszych ścieżek. Ta metoda jest faktycznie opisana w CLRS.$+$$\min$$\cdot$$+$

Chociaż może się to wydawać jedynie teoretyczne z perspektywy algebraicznej, pozwala nam wykorzystywać bardzo mocno zoptymalizowane biblioteki algebry liniowej do rozwiązywania problemów graficznych. Jednoczęściowa biblioteka BLAS jest jedną z takich bibliotek.

Zbiór wszystkich słów nad pewnym skończonym alfabetem wraz z konkatenacją tworzy wolny monoid . Dlatego całe pole języka formalnego można postrzegać przez soczewkę algebraiczną, a czasem tak się uczy.$(\Sigma^*, \cdot)$

W zamian za rozważenia dotyczące języków formalnych uzyskano parser Earley, który można rozszerzyć o analizę składniową w semirings . Jest to przydatne w przetwarzaniu języka naturalnego i innych obszarach wykorzystujących modele stochastyczne dla (formalnych) języków.

Mam doświadczenie matematyczne, ale nie jestem informatykiem. Byłoby wspaniale mieć zastosowanie w świecie rzeczywistym monoidów i półgrup. Są one zwykle uważane za bezużyteczne konstrukcje teoretyczne i są ignorowane w wielu abstrakcyjnych kursach algebry (z powodu braku czegoś interesującego do powiedzenia).

Jest zbyt wiele interesujących do powiedzenia. Jest to jednak bardziej dyskretna matematyka i kombinatoryka niż abstrakcyjna algebra i analiza, przynajmniej w przypadku mniej trywialnych tematów. Jest też pytanie, ile musisz wiedzieć na dany temat, zanim będziesz mógł powiedzieć komuś innemu, że byłby to interesujący temat matematyczny związany z monoidami i półgrupami. Na przykład uważam następujące tematy (związane z półgrupami) za interesujące:

• półgrupy skończone i teoria Krohna-Rhodesa
• częściowe symetrie, odwrotne półgrupy, grupoidy i kwazikryształy
• półpozycje i tropikalna geometria
• zamówienia częściowe i funkcje Möbiusa
• funkcje podmodularne i (jak Dulmage-Mendelsohn) dekompozycje

Czy wiem dużo o każdym z tych tematów? Prawdopodobnie nie. Istnieje również wiele innych zagadnień matematycznych związanych z monoidami i półgrupami, niektóre z nich są bardziej wewnętrzne w stosunku do samej teorii półgrup (takie jak relacje Greena), inne są bardziej ogólne i nie są specyficzne dla półgrup (uniwersalne półgrupy, twierdzenia o homomorfizmie i izomorfizmie, struktury ilorazowe i gratulacje), ale także ważne z matematycznego punktu widzenia. Tematy, które cytowałem powyżej, mają głównie zastosowania w „świecie rzeczywistym”, ale jest więcej powiązanych tematów, które również mają aplikacje w „świecie rzeczywistym”.

Powyższe nie jest odpowiedzią na prawdziwe pytanie, ale odnosi się jedynie do uwagi „… są zwykle uważane za bezużyteczne konstrukcje teoretyczne… z uwagi na brak jakichkolwiek ciekawych rzeczy do powiedzenia…”. Wymieniłem więc kilka „interesujących” punktów, twierdząc, że w większości mają one aplikacje „z prawdziwego świata”, a teraz Hi-Angel prosi o trochę informacji o tych aplikacjach. Ale ponieważ „jest zbyt wiele interesujących do powiedzenia”, nie oczekuj zbyt wiele od tych informacji: Twierdzenie Krohna-Rhodesa jest twierdzeniem o rozkładzie dla półgrup skończonych. Jego zastosowania obejmują interpretację produktu wieniec jako swego rodzaju kompozycji (przetworników) w powiązaniu z teorią automatów i zwykłych języków,Mark V Lawson: dwa wykłady instruktażowe i materiał w tle zawierały (obecnie 404) dobry materiał na półgrupach odwrotnych . Podstawą ich zastosowania jest ich połączenie z symetryczną odwrotną półgrupą , tj. Zestawem wszystkich częściowych wstrząsów na zbiorze. Można również zacząć od podstawowych charakterystyk algebraicznych odwrotnych półgrup, ale takie podejście grozi zaniedbaniem połączeń z częściowymi porządkami, które są ważne dla wielu aplikacji. Pewnego dnia będę musiał blogować o konkretnym zastosowaniu odwrotnych półgrup jako „hierarchii” używanej do kompresji układów półprzewodników. Zastosowania półirowań zostały już opisane w innych odpowiedziach (a geometria tropikalna odciągnęłaby nas od informatyki). Ponieważ monoidy i półgrupy są również powiązane z częściowymi porządkami, tak fajne tematy jak funkcje Möbiusa, jak opisano w Combinatorics: The Rota Way są również powiązane. Później powiązane zostały również tematy z Matryc i Matroidów do analizy systemu, takie jak rozkład Dulmage-Mendelsohna , które były jedną z moich motywacji do studiowania teorii sieci (i ukrytych struktur hierarchicznych).