09.09.2020: Wstęp

1. Trzy główne typy danych którymi będziemy się zajmować:
   • wąska tablica $T[n,m]$ taka, że $n\cdot m$ nie mieści się pamięci komputera ale liczba kolumn $m$ jest mała
   • szeroka tablica $T[n,m]$ taka, że $n\cdot m$ nie mieści się pamięci komputera ale liczba wierszy $n$ jest mała
   • tablica $T[n,m]$, która mieśli się w pamięci komputera , ale interesują nas (na przykład) wszystkie podzbiory zbioru kolumn $\{1,\ldots,m\}$.
2. Losowe koincydencje w dużych zestawach danych
   • Jeśli 10000 ludzi rzuca 10 razy monetą, to około 10 z nich wylosuje ustalony ciąg $(i_1,\ldots,i_{10}) \in \{0,1\}^{10}$
   • Oszacowaliśmy, że codziennie około 20 osób w Polsce rano widzi czarnego kota i w tym dniu zostaje wyrzuconych z pracy
3. Funkcje hash'ujące
   1. Zamiana łańcuchów na liczby naturalne $$h((a_0,\ldots,a_n)) = \sum_{i=0}^{n} ord(a_i)\cdot 256^i$$
   2. Pojęcie funkcji hash'ującej: $h:\Omega \to \{0,\ldots,n-1\}$
   3. Kolizja: taka para $x,y \in \Omega$, że $x \neq y$ i $h(x)=h(y)$
   4. Obserwacja: jeśli $h:\Omega\to \{0,\ldots,n-1\}$, to istnieje $a\in\{0,\ldots,n-1\}$ takie, że $|h^{-1}(\{a\})| \geq \frac{|\Omega|}{n}$.
      Zatem: jeśli $\Omega| \gt n$, to kolizje są nieuniknione
   5. Ortogonalne projekcje skończonych podzbiorów $P$ przestrzeni $\RR^2$ na podprzestrzenie jednowymiarowe: $$\pi_{\alpha}(x,y) = a \cos\alpha + y\sin\alpha, \quad \alpha\in [0,\pi)$$ Pokazaliśmy, że jeśli $P$ jest ustalonym skończonym podzbiorem $\RR^2$, to $$ \Pr[\pi_\alpha\text{ jest różnowartościowa na } P] = 1 $$ Zatem: z prawdopodobieństwem 1 losowa projekcja nie ma kolizji na $P$.
   6. Pojęcie uniwersalnej rodziny hash'ującej: rodzina $\mathcal{H}$ funkcji z $\Omega$ w $\{0,\ldots,n-1\}$ jest uniwersalnie hash'ująca jeśli dla dowolnych $x,y \in \Omega$ mamy $$ \Pr_{h\in\mathcal{H}}[h(x) = h(y)] \leq \frac{1}{n} $$ gdzie $$ \Pr_{h\in\mathcal{H}}[h(x) = h(y)] = \frac{|\{h\in\mathcal{H}: h(x)=h(y)\}|}{|\mathcal{H}|} $$ (od tego zaczniemy następny wykład)
4. Zadanie HELLO WORLD dla Big Data: wydobycie najczęściej występujących słów w wybranej książce

16.09.2020: Funkcje hash'ujące i filtry Blooma

1. Przykład rodziny uniwersalnej: $\mathcal{H} = [n]^{\Omega}$
2. Przykład: rodzina $f_a(x) = (a x \mod p) \mod n$, gdzie $p$ jest liczbą pierwszą i $a\in\{1,\ldots,n\}$ jest prawie uniwersalna ze stałą $C=2$
3. Def. Rodzina $\mathcal{H}$ funkcji haszujących jest $k$-niezależną rodziną funkcji haszujących jeśli dla dowolnej parami róznych $x_1,\ldots, x_k$ elementów $\Omega$ oraz dowonych $y_1,\ldots,y_k$ z $[n]$ mamy $$ \Pr_{h\in\mathcal{H}}[h(x_1)=y_1 \land \ldots h(x_k) = y_k] = \frac{1}{n^k} $$
4. Konstrukcja: dla $a = (a_0,\ldots,a_{k-1}) \in \ZZ_p^k$ kładziemy $$ h_a(x) = \sum_{i=0}^{k-1} a_i x^i \mod p $$ Wtedy $\mathcal{H}=\{h_a:a\in\ZZ_p^k\}$ jest $k$-niezależną rodziną funkcji z $\ZZ_p$ do $\ZZ_p$. Jeśli złożymy tę rodziną z funkcją $\phi(x) = x \mod n$, to otrzymamy "prawie" $k$-niezależną rodziną funkcji haszujących z $\ZZ_p$ w $[n]$.
   Możemy zastąpić owo "prawie" przez "dokładnie", jeśli zamienimy $\ZZ_p$ przez ciało o $2^m$ elementach oraz $n=2^a$ dla $a\lt m$ !!!!!
5. Filtry Blooma: lektura A. Broder and M. Mitzenmacher Network Applications of Bloom Filters: A Survey
   Wykres funkcji $f(p) = - \ln(p)\ln(1-p)$ któa pojawiła się podczas analizy filtów Blooma
   

23.10.2020: Model obliczeń "Map-Reduce"

1. Paradoks urodzinowy: $E[B_n] = \sqrt{\frac{\pi n}{2}} + \frac32 + O(n^{-1/2}) \approx \sqrt{n}$
2. Coupon Collector Problem: $E[C_n] = n H_n \approx n \ln(n)$
3. Fakt: dla $m \gt n (\ln(n))^2$ rozkład ilości $m$ kul w $n$ urnach jest zbliżony do jednostajnego, czyli w każdej urnie mamy $\approx \frac{m}{n}$ kul.
4. Podstawowe klasy funkcji haszujących:
   1. kryptograficzne: MD5 (przetarzała), SHA-XXX
   2. MumurHash - popolarna obecnie funkcja do aplikacji Big Data
5. Podstawowy model: procesy typu MAPPER - funkcja haszująca - procesy typu REDUCER.
   Musisz przeczytać: MapReduce: Simplified Data Processing on Large Clusters
6. Word-count problem w modelu Map-Reduce

   map(L){
     dla wszystkich słów w z linii L do 
     emit((w,1))
   };
   reduce(w,L) {
     emit(w,length(L))
   };
   

7. Mnożenie macierzy przez wektor $x$ przechowywany w pamięci:

   map(i,j,a){
     emit((i,a*x[j]))
   };
   reduce(i,L){
     emit((i, sum(L)))
   }
   

30.10.2020: Map-Reduce

06.11.2020: Map-Reduce

21.11.2020: Sampling

27.11.2020: Zliczanie

04.12.2020: Algorytm HyperLogLog

11.12.2020: Locality Sensitive Hashs Functions Families

1. Odległość Jaccarda: $d_J(A,B) = \frac{|A\triangle B|}{|A \cup B|}$
2. Podobieństwo Jaccarda:
   $$ J(A,B) = \frac{|A\cap B|}{|A \cup B|} $$ Uwaga: $J(A,B) = 1 - d_J(A,B)$.
3. Tw.
   $$ \Pr_{\sigma}[h_A(\sigma) = h_B(\sigma)] = J(A,B) $$