Apa gunanya grup, monoid, dan cincin dalam perhitungan basis data?

Mengapa perusahaan seperti Twitter tertarik pada konsep aljabar seperti grup, monoids, dan cincin? Lihat repositori mereka di github: twitter / algebird .

Yang bisa saya temukan adalah:

Implementasi Monoids untuk algoritme aproksimasi yang menarik, seperti filter Bloom , HyperLogLog , dan CountMinSketch . Ini memungkinkan Anda untuk memikirkan operasi canggih ini seperti jumlah Anda, dan menambahkannya dalam hadoop atau online untuk menghasilkan statistik dan analitik yang kuat.

dan di bagian lain dari halaman GitHub:

Awalnya dikembangkan sebagai bagian dari Matrix API Scalding , di mana Matriks memiliki nilai yang merupakan elemen Monoids , Grup , atau Cincin . Selanjutnya, jelas bahwa kode memiliki aplikasi yang lebih luas dalam Scalding dan proyek-proyek lain di Twitter.

Apa yang bisa menjadi aplikasi yang lebih luas ini? dalam Twitter dan untuk kepentingan umum?

Sepertinya agregasi komposisi basis data memiliki struktur seperti monoid.

Pertanyaan yang sama pada Quora: Apa minat Twitter dalam aljabar abstrak (dengan algebird)?

Saya memiliki latar belakang matematika tetapi saya bukan ilmuwan komputer. Akan lebih bagus jika menggunakan monoids dan semi-grup "dunia nyata". Ini biasanya dianggap konstruksi teoretis yang tidak berguna, dan diabaikan dalam banyak kursus aljabar abstrak (karena tidak ada yang menarik untuk dikatakan).

Jawaban utamanya adalah bahwa dengan mengeksploitasi struktur semi-grup, kita dapat membangun sistem yang paralel dengan benar tanpa mengetahui operasi yang mendasarinya (pengguna menjanjikan asosiatif).

Dengan menggunakan Monoids, kita dapat mengambil keuntungan dari sparsity (kita berurusan dengan banyak matriks yang jarang, di mana hampir semua nilai adalah nol di beberapa Monoid).

Dengan menggunakan Rings, kita bisa melakukan perkalian matriks atas hal-hal selain angka (yang kadang-kadang kita lakukan).

Proyek algebird itu sendiri (dan juga sejarah masalah) dengan cukup jelas menjelaskan apa yang terjadi di sini: kami sedang membangun banyak algoritma untuk agregasi kumpulan data besar, dan meningkatkan struktur operasi memberi kami kemenangan di sisi sistem (yang biasanya merupakan titik rasa sakit ketika mencoba memproduksikan algoritma pada 1000s node).

Selesaikan masalah sistem satu kali untuk Semigroup / Monoid / Group / Ring, dan kemudian Anda dapat menyambungkan algoritma apa pun tanpa harus memikirkan Memcache, Hadoop, Storm, dll ...

Monoids ada di mana-mana dalam pemrograman, hanya saja sebagian besar programmer tidak tahu tentang mereka.

• Operasi angka seperti penjumlahan dan perkalian.
• Perkalian matriks.
• Pada dasarnya semua struktur data seperti pengumpulan membentuk monoids, di mana operasi monoid adalah gabungan atau gabungan. Ini termasuk daftar, set, peta kunci nilai, berbagai jenis pohon dll.
• $A$$A\to A$$A$$A$

$a\cdot b$$a$$b$

Karena monoids sangat umum, mereka memungkinkan untuk menulis fungsi yang sangat umum. Misalnya, melipat struktur data dapat dinyatakan sebagai memetakan setiap elemennya menjadi monoid dan kemudian menggunakan operasi monoid untuk menggabungkannya ke satu hasil.

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

• eksponensial angka yang cepat;
• $O(\log n)$
• $O(1)$$O(\log(\min(n_1,n_2)))$
• dll.

Untuk lebih banyak contoh, lihat Contoh monoids / semi-grup dalam pemrograman .

Salah satu masalah penting dalam sistem file terdistribusi ( DFS ) adalah untuk menghasilkan file dari blok terdistribusi. Area kode Erasure dari teori informasi dan Aljabar (grup, cincin, aljabar linier, ...) digunakan secara luas dalam sistem file toleran kesalahan yang didistribusikan, misalnya dalam RAID HDFS (Sistem File Berbasis Hadoop). Jaringan sosial dan perusahaan Cloud secara luas didasarkan pada DFS, sehingga mereka membutuhkan orang-orang yang ahli dalam Aljabar dan Kode Penghapusan untuk merancang sistem yang lebih baik dan berkinerja tinggi (seperti kode Reed-Solomon , dll).

Ini juga poster yang bagus untuk aplikasi mereka (aljabar) dalam penyimpanan cloud: Novel Codes for Cloud Storage

Jika pertanyaan Anda

Apa contoh kelompok, monoids, dan cincin dalam perhitungan?

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

Meskipun ini mungkin tampak hanya teoritis dari perspektif aljabar, ini memungkinkan kita untuk memanfaatkan pustaka aljabar linier yang sangat dioptimalkan untuk masalah grafik. BLAS kombinatorial adalah salah satu perpustakaan tersebut.

$(\Sigma^*, \cdot)$

Sebagai imbalannya, pertimbangan pada bahasa formal telah menghasilkan parser Earley yang dapat diperluas hingga parse pada semiring . Ini berguna dalam pemrosesan bahasa alami dan area lain menggunakan model stokastik untuk bahasa (formal).

Saya memiliki latar belakang matematika tetapi saya bukan ilmuwan komputer. Akan lebih bagus jika menggunakan monoids dan semi-grup "dunia nyata". Ini biasanya dianggap konstruksi teoretis yang tidak berguna, dan diabaikan dalam banyak kursus aljabar abstrak (karena tidak ada yang menarik untuk dikatakan).

Agak terlalu menarik untuk dikatakan. Namun, ini lebih merupakan topik matematika dan kombinatorik diskrit daripada aljabar dan analisis abstrak, setidaknya untuk topik yang kurang sepele. Ada juga pertanyaan seberapa banyak Anda harus tahu tentang topik tertentu sebelum Anda dapat memberi tahu orang lain itu akan menjadi topik matematika yang menarik terkait dengan monoids dan semi-grup. Sebagai contoh, saya menemukan topik-topik berikut (terkait dengan semi-grup) menarik:

• semigroup terbatas dan teori Krohn-Rhodes
• simetri parsial, semigroup terbalik, groupoid dan quasicrystals
• semir dan geometri tropis
• perintah parsial dan fungsi Möbius
• fungsi submodular dan (Dulmage-Mendelsohn suka) dekomposisi

Apakah saya tahu banyak tentang masing-masing topik ini? Mungkin tidak. Ada juga banyak lagi topik matematika yang berkaitan dengan monoids dan semi-grup, beberapa di antaranya lebih internal ke teori semi-grup itu sendiri (seperti hubungan Green), yang lain lebih umum dan tidak spesifik untuk semi-grup (semigroup universal, teorema homomorfisme dan isomorfisme, struktur hasil dan kongruensi), tetapi juga penting dari sudut pandang matematika. Topik yang saya kutip di atas sebagian besar memiliki aplikasi "dunia nyata", tetapi ada lebih banyak topik terkait yang juga memiliki aplikasi "dunia nyata".

Di atas bukanlah jawaban untuk pertanyaan sebenarnya, tetapi hanya membahas "... biasanya dianggap konstruksi teoretis tidak berguna ... karena kurangnya sesuatu yang menarik untuk dikatakan ..." komentar. Jadi saya mendaftarkan beberapa poin "menarik", mengklaim bahwa kebanyakan dari mereka memiliki aplikasi "dunia nyata", dan sekarang Hi-Angel meminta sedikit info tentang aplikasi tersebut. Tetapi karena "ada terlalu banyak yang menarik untuk dikatakan," jangan berharap terlalu banyak dari info itu: Teorema Krohn-Rhodes adalah teorema dekomposisi untuk semi- grup terbatas. Penerapannya melibatkan interpretasi produk karangan bunga sebagai semacam komposisi (transduser) sehubungan dengan teori automata dan bahasa reguler,Mark V Lawson: dua kuliah tutorial dan materi latar berisi (404 sekarang) materi bagus tentang Semigroup Invers . Dasar untuk aplikasi mereka adalah koneksi mereka ke semigroup terbalik simetris , yaitu himpunan semua biopsi parsial pada satu set. Kita juga bisa mulai dengan karakterisasi aljabar dasar dari semigroup terbalik, tetapi pendekatan ini berisiko mengabaikan koneksi ke perintah parsial yang penting untuk banyak aplikasi. Suatu hari saya harus menulis blog tentang aplikasi spesifik dari semigroup terbalik sebagai "hierarki" yang digunakan untuk mengompresi tata letak semikonduktor.. Aplikasi semir telah dijelaskan dalam jawaban lain (dan geometri tropis akan membawa kita jauh dari ilmu komputer). Karena monoids dan semi-grup juga terkait dengan perintah parsial, topik-topik bagus seperti fungsi Möbius seperti yang dijelaskan dalam Combinatorics: The Rota Way juga terkait. Dan kemudian juga topik dari Matriks dan Matroid untuk Analisis Sistem seperti dekomposisi Dulmage-Mendelsohn menjadi terkait, yang merupakan salah satu motivasi saya untuk mempelajari teori kisi (dan struktur hierarkis tersembunyi).