prof. dr hab. Jacek Cichoń

Katedra Podstaw Informatyki WIT Politechnika Wrocławska

Big Data

Wykład przeznaczony jest dla studentów stopnia studiów informatycznych na Wydziale Podstawowych Problemów Techniki. Odbywa się w czwartki w godz. - na platformie MIcrosoft Teams. Na stronie tej znajdziesz informacje o zasadach zaliczenia, realizowanym materiale, literaturze oraz listę zadań.

Koniec strony

Zasady zaliczania kursu

Zasady zaliczenia ćwiczeń ustalicie z prowadzącym ćwiczenia. Ocena z ćwiczeń będzie oceną bazową z kursu. Jak ktoś będzie chciał podwyższyć tę ocenę, to będzie musiał ze mną odbyć indywidualny egzamin.

Literatura

$ \def\RR{\mathbb{R}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\CC{\mathbb{C}} \def\NN{\mathbb{N}} \def\IFF{\leftrightarrow} \newcommand{\span}[1]{\mathrm{span}(#1)} \newcommand{\IS}[2]{\langle\,#1,#2\rangle} \newcommand{\sgn}[1]{\mathrm{sgn}(#1)} $

Zagadnienia omówione na wykładzie

07.10.2021: Wstęp

  1. Mało procyzyjny opis problematyki Big Data
  2. Problem "Word Count"
    Link do "stop words" dla języka polskiego: StopWordsPL.txt. Linki do "stop words" dla innych języków znajdziecie na stronie WIKI
  3. Pojęcie TF-IDF
  4. Podstawowy model MAP-REDUCE: procesy typu MAPPER - funkcja haszująca - procesy typu REDUCER.
  5. Mnożenie macierzy przez wektor przechowywany w pamięci: 
    MAPPER(i,j,aij) {
    emit (i,aij * xj)
}
REDUCER(i,L) {
    emit(i, sum(L))
}
  6. Word-count problem: 
    MAPPER(L) {
    split text L into words [w1, w2, ... wn]
    emit (w1,1); emit (w2,1); ... ; emit (wn,1);
}
REDUCER(w,L) {
    emit(w,L.length)
}
Przykład sesji w języku Scala (wy macie coś podobnego, ale znacznie lepszego, zrobić w języku Python): 
val T = "ALA ma kota. ALA ma psa. Ala ma kota i kanarka"
val t = T.toLowerCase
var G = t.filterNot(x=>".;".contains(x)).split("\\s+").map(x=>(x,1))
val A = G.groupBy(x=>x._1).mapValues(x=>x.length)
var X = A.toSeq
X.sortWith((x,y)=>x._2>y._2)
  1. Zadanie: załóżmy, że chcemy pomnożyć macierz $M$ przez wektor $X$, który nie mieści się w pamięci mapperów, ale mieści się po $\frac13$ części tego wektora. Jak to możemy zrobić w paradygmecie Map-Reduce?
  2. Notatki z wykładu: BD01.pdf

14.10.2021: Map-Reduce

  1. Uwagi o przypadkowych zależnościach w dużych zasobach informacyjnych
  2. Obliczanie agretatów: suma, min, max
  3. Pojęcia composera: reducer działający po stronie mappera.
    Uwaga: stosować go można (aby mieć kontrolowalny wynik) do operacji łącznych i przemiennych
  4. Obliczanie sredniej i wariancji 
      mapper(x) {emit (h(x),1,x,x*x);}
    gdzie, np. h(x)= ostatnie 10 cyfr liczby x$
  5. Obliczanie sumy, przekroju i różnicy zbiorów za pomocą map-reduce.
  6. Operacje bazo-danowe. Join R(A,B) i S(B,C) 
    map ("X", x, y) { if ("X" == "R") emit(y->(1,x)) else emit(x->(2,y)) }
reduce(x->L) { 
  pogrupuj L: [1 -> L1, 2 -> L2]
  forall(a <- L1; c <- L2)
    emit((a, x, c) -> (a, x, c))
}
  7. Złożenie grafu skierowanego: graf jest reprezentowany przez listę par wierzchołków reprezentujących krawędzie:
    map (a,b) { emit(a->("to",b)); emit(b->("from",a)) }
reduce(x->L) { 
  pogrupuj L: ["from" -> L1, "to" -> L2]
  forall(a <- L1; c <- L2)
    emit((a,c) -> (a,c))
}
Notatki z wykładu: BD02.pdf

21.10.2021: Map-Reduce

  1. Różne metody mnożenia macierzy w modelu Map-Reduce
  2. Jedna z metod mnożenia macierzy kwadratowych $M = [m_{i,j}]$ i $N= [n_{i,j}]$ rozmiaru $n\times n$ 
    STEP I:
map ("X", i, j, x) { if ("X" == "M") emit(j -> (1,i,x)) else emit(i->(2,j,x)) }
reduce(x->L) { 
  pogrupuj L: [1 -> L1, 2 -> L2]
  forall((1,i,x) <- L1; (2,k,y) <- L2)
    emit((i, k) -> x*y)
}
STEP II : mapper = identity
reduce ((i,k) ->L) {emit ((i,j) -> Sum(L))}
  3. $$M_{n,n}(M_{m,n}(K)) \sim M_{n\cdot m,n\cdot m}(K)$$
  4. Paradoks urodzinowy: $E[B_n] = \sqrt{\frac{\pi n}{2}} - \frac12 + O(n^{-1/2})$
  5. Coupon Collector Problem: $E[L_n] = n \cdot H_n \approx n \ln(n)$
  6. Pojęcie hash-table.
Notatki z wykładu: BD03.pdf.

4.11.2021: Funkcje haszujące.

  1. Naturalne wymagania stawiane funkcją haszującym.
  2. Projekcje w losowych kierunkach z płaszczyzny na podprzestrzeń jednowymiarową.
  3. Pojęcie k-uniwersalnej rodziny haszującej
  4. Tw. Jeśli $\mathcal{H}$ jest 2 uniwersalna o wartościach w $\{0,\ldots,n-1\}$, oraz $|X|=k$ i $L$ jest długością wyszukiwania w hasz-tablicy w ktorej umieściliśmy elementy $X$ to $E[L] \leq k/n$.
    Liczbę $\alpha = k/n$ nazywamy wspołczynnikiem zapełnienia tablicy.
  5. Przykład 2-uniwersalnej rodziny:
    mamy ustaloną liczbę $n$ oraz liczbę pierwszą $p \gt n$; definiujemy $\mathcal{H} = \{\phi_{a,b}: a \in \ZZ_{p}^{+} \land b \in \ZZ_p\}$, gdzie $$ \phi_{a,b}(x) = (a x + b \mod p) \mod n $$ Jest to 2-uniwersalna rodzina funkcji haszujących ze zbioru $\{0,\ldots,p-1\}$ do $\{0,\ldots,n-1\}$.
    Uwaga: pewną trudność sprawiało nam to, że liczba pierwsza $p$ nie jest podzialna przez $n$.
  6. Pojęcie silnie k-uniwersalnej rodziny haszującej
  1. Zadanie: napisz w dowolnym języku programowania generator liczb losowych z rozkładu jednostajnego z odcinka $[0,\pi)$
  2. Pytanie: dlaczego pojęcie funkcji 2-uniwersalnej nie ma sensu ?
  3. Notatki z wykładu: BD04.pdf.

18.11.2021: Funkcje haszujące i Filtry Blooma.

  1. Konstrukcja rodziny funkcji k-silnie niezależnej rodziny funkcji haszujących.
  2. Przykład: konstrukcja ciała liczbowego o $2^8$ elementach.
  3. Filtry Blooma
  4. Wzór na "false positive": $$\Pr[\mathrm{False Positive}] \approx \left(1-\left(1-\frac1m\right)^{kn}\right)^k ~,$$ gdzie: $m$ = rozmiar tablicy, $n$ = liczba wstawianych obiektów, $k$ = liczba funkcji haszujących
  5. Tw. Dla ustalonych $m$ i $n$ liczba $k \approx \ln 2 \cdot \frac{m}{n}$ minimalizuje $\Pr[\mathrm{False Positive}]$
  6. Zasada: jeśli używasz list lub zbiorów, a pamięć jest jest istotnym ograniczeniam oraz efekt fałszywych alarów nie jest istotnym problemem, to rozważ zastosowanie filtrów Blooma
  1. Notatki z wykładu: BD05.pdf.
  2. Orginalny artykuł Burtona Bloom'a z roku 1970: Bloom.pdf
  3. Fajny artykuł Andrei Brodera and Michaela Mitzenmachera z roku 2005: im2005b.pdf

02.12.2021: Podobieństwo Jaccarda.

  1. Przypomnienie pojęcia przestrzeni metrycznej
  2. Przekształcenia metryk:
    1. Tw. Jeśli $d$ jest metryką, $f:[0,\infty)\to [0,\infty)$ jest funkcją wklęsłą , niemalejącą oraz $f(x)\gt 0$ dla $x\gt 0$, to funkcja $f\circ d$ jest również metryką.
    2. Tw (Steinhaus). Jeśli $d$ jes metryką na zbiorze $X$, $a \in X$ oraz $$ \rho(x,y) = \frac{2 d(x,y)}{d(x,a)+d(y,a)+d(x,y)} ~, $$ to $\rho$ jest metryką na zbiorze $X\setminus\{a\}$.
  3. Tw. Funkcja $d_J(A,B) = \frac{|A\triangle B|}{|A\cup B|}$ jest metryką na przestrzeni skończonych podzbiorów ustalonego $\Omega$
  4. Pojęcia podobieństwa
  5. Def. Podobieństwo Jaccarda: $J(A,B)= \frac{|A\cap B|}{|A\cup B|}$ = $(1-d_J(A,B))$
  6. Dla $\Omega=\{1,\ldots, L\}$ , $A \subseteq \Omega$ i permutacji $\pi$ zbioru $\Omega$ określamy $$ m(\pi, A) = \min\{k: \pi(k) \in A\}~. $$
  7. Twierdzenie: $\Pr_{\pi}[m(\pi,A)=m(\pi,B)] = J(A,B)$.
    Dowód tego twierdzenia powinniście znać.
Notatki z wykładu: BD06.pdf.