• 데이터의 크기가 커졌다!
  • 메모리에 전부 들어가지 않는다

Scalable

스케일러블; 확장 가능한?

• Operationally
  • past: works even if data does not fit in main memory
  • now: we can use thousands of cheap computers
• Algorithmically:
  • past: N data → max N^m operations 다항 시간
  • now: N data → max N^m/k operations 다항 시간 알고리즘을 최대로 병렬화 한다.
  • soon: N data → max NlogN operations

Example: finding DNA seq

• Sequential search 하나 하나 비교해서 O(N) 걸린다

  

• Binary Search

  

  정렬한 뒤, 절반씩 쳐내면서 찾으면 O(log N) 걸린다.

Example: Read Trimming

데이터를 자르는 연산?

기본적으로 O(N)걸리고, 정렬을 해도(Index 사용) O(N) 걸린다

• → 병렬 처리 병렬 배럭수에 비례해 빨라진다

  

  

Example: Convert TIFF image to PNG

Example: Run THousands of simulations

Example: Find the most common word in each document

…

pattern?