빅데이터를 다루기 위해서, 즉 Stream Data를 다루기 위해서 Moment라는 개념을 정리해 둘 필요가 있다. 여러 물리량을 다루는 데 있어서 모멘트라는 개념이 많이 쓰이기도 하기 때문에 낯설지는 않은 개념이겠지만, 확실하게 짚고 넘어가는 것이 좋다. m(i)를 특정한 값 i가 Stream 에 등장한 횟수라고 정의할 때, kth Moment는 아래 그림과 같이 스트림에 있는 N개의 m(i)를 각각 k승 한 값들의 합으로 나타낼 수 있다. 이 모멘트는 k값에 따라 각기 다른 특정한 의미를 갖는데, 모멘트를 정의하는데 사용했던, m(i)의 의미를 생각해보면 쉽게 이해할 수 있다. 0th moment = m(i)의 값이 의미가 없어지므로, 스트림 내에서 서로 다른 원소의 개수를 의미한다. 1st mome..

Stream 형태의 무한한 데이터를 다루기 위한 알고리즘 중의 하나는 '필터링 알고리즘'이다. 스트림에서 X라는 속성을 가지는 데이터들을 걸러내는 알고리즘으로써 여러 메일들의 스트림을 입력받았을 때, 스팸메일을 걸러주는 프로그램등이 이 필터링 알고리즘을 적용한 예에 속한다. Filtering Data Streams 이전 포스팅의 예제와 마찬가지로 데이터 스트림의 각 원소는 Tuple(튜플, 순서쌍)의 형태로 입력이 된다. 이때 필터링 알고리즘의 문제는 S라는 Key set이 들어왔을 때, 입력되는 튜플들의 스트림 중 S에 속하는 튜플들을 걸러내는 것이 된다. 이를 해결하기 위한 가장 명백한(Obvious) 방법은 해시 테이블(Hash Table)을 이용하는 것이다. 해시 함수는 같은 키 값이 들어오면 무..