Problema majoritatii

[•Cosmin]

Comentarii la postul http://infoarena.ro/blog/problema-majoritatii

[•wefgef]

Apare un bad macro din cauza ca ai == pe acolo.

[•Cosmin]

Rezolvat

[•mpatrascu]

Ah, heavy hitters   Chiar la ce lucram azi in drum spre facultate.

Problema e intr-adevar importanta pt baze de date de toate felurile (din cate aud si google). Uite cam ce se poate face:

1. Usor de demonstrat, si complet deterministic [ca la elementul majoritar]: Daca cauti elemente cu densitate mai mare de 1/k, poti sa faci un pass prin date, cu memorie O(k), si la sfarsit sa obtii o lista cu O(k) elemente candidate. Stii ca toate elem de densitate > 1/k apar intre candidati, dar candidatii pot sa aiba si valori mai mici.

2. evident daca faci inca un pass poti sa verifici marimea fiecarui candidat si sa pastrezi chiar heavy hitters reali.

3. Mai interesant (si mai greu), problema se poate si daca ai un stream de date cu +1 si -1 amestecate (adica ai m operatii, fiecare incrementeaza sau decrementeaza countul de la un element, si apoi vrei sa afli elementele de count mai mare de m/k). Iti trebe spatiu O(k lg m), si randomizare. Vezi http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec4/lec4.pdf

4. Si mai interesant, problema se poate face in diverse norme L_p, care sunt superutile la estmat k-th frequency moments. Frequency moment inseamna (aproximativ) ca ai un stream de additions si deletions la mai multe tabele intr-o baza de date, si vrei sa estimezi marimea joinului intre k dintre ele. Surprinzator chiar poti face asta tinand minte putine informatii (spre exemplu radical din m, pt k=3)...

5. Daca stie cineva sa faca heavy hitters in L_2^2(L_1) [negative type metrics over L1]  sa-mi zica si mie    Problema asta e utila la calculat edit distance cu comunicare putina (avem doua copii putin modificate de la un fisier, pe doua calculatoare in retea, si vrem sa facem sincronizare care sa ne coste in functie de cat de diferite sunt fisierele -- nu vrei sa tranferi tot fisierul de fiecare data).

-mip

[•Cosmin]

Nu am auzit sa fie la Google folosita problema, doar mi se parea interesanta. Mersi pentru materialele inrudite, nici nu stiam ca asa i-ar zice la problema acum stiu sa ma mai documentez. Articolul ce il scrisesem era o colectie de solutii ce le vazusem sau le gasisem de-a lungul timpului, nu stiam ca se face research pe langa ea. Adica nu la un nivel mai mare decat ca si curiozitate matematica.

Cu chestiile cu L_2^(L_1) nu le am, daca apareau intr-un paper care il citeam, ma documentam acolo pe loc si dupaia uitam, deci cu 5. m-ai cam pierdut in ceata .