무작위 알고리즘(Randomized Algorithms)
무작위 알고리즘은 무작위 표본 추출(random sampling)과 스케칭(sketching) 기법의 형태로, 대규모 고차원 데이터 스트림을 처리하는 데 활용됩니다. 무작위성을 도입하면 기존의 결정론적(deterministic) 알고리즘보다 더 단순하면서도 효율적인 알고리즘을 설계할 수 있다는 점이 큰 장점입니다.
무작위 알고리즘은 항상 올바른 답을 반환하지만 실행 시간이 매번 달라지는 경우 라스베가스(Las Vegas) 알고리즘이라고 합니다. 반면 몬테카를로(Monte Carlo) 알고리즘은 실행 시간에 상한이 존재하지만 항상 참값을 보장하지는 못합니다. 실무에서는 주로 몬테카를로 방식의 알고리즘이 활용됩니다. 무작위 알고리즘의 본질은 결정론적 알고리즘들의 집합 위에 확률 분포를 정의한 것으로 이해할 수 있습니다.
무작위 알고리즘의 결과는 확률 변수(random variable)로 나타나므로, 이 확률 변수의 꼬리 확률(tail probability)에 대한 상계를 구할 수 있습니다. 즉, 확률 변수가 기댓값에서 크게 벗어날 확률이 작다는 것을 의미합니다. 이때 가장 핵심적인 도구가 체비쇼프 부등식(Chebyshev's Inequality)입니다.
평균 μ와 표준편차 σ(분산 σ2)를 갖는 확률 변수 X에 대해 체비쇼프 부등식은 다음과 같습니다.
$$\mathrm{P(|X-\mu|>k)<\frac{\sigma^2 }{k^2}}$$
여기서 k는 임의의 양의 실수입니다. 이 부등식은 확률 변수의 분산을 이용해 편차의 상계를 구하는 데 사용됩니다. 또한 여러 개의 독립적인 확률 변수를 함께 활용하면 결과에 대한 신뢰도를 높일 수 있으며, 이들이 서로 완전히 독립인 경우에는 체르노프 경계(Chernoff bound)를 적용할 수 있습니다.
X1, X2, …, Xn이 독립적인 포아송 시행(Poisson trials)이라고 하겠습니다. 포아송 시행에서는 시행마다 성공 확률이 서로 다를 수 있습니다. X가 X1부터 Xn까지의 합이라면, 체르노프 경계의 약한 형태는 다음과 같이 말해줍니다.
$$\mathrm{P[X>(1+\delta)\mu]< e^{-\mu\delta^2}}$$
여기서 δ ∈ (0, 1]입니다. 이 식은 값이 평균에서 멀어질수록 해당 사건의 확률이 지수적으로 감소함을 보여주며, 따라서 크게 벗어난 나쁜 추정치가 나올 가능성은 극히 낮아집니다.
데이터 스트림 관리 시스템(Data Stream Management System)
데이터 스트림 관리 시스템(DSMS)에는 여러 개의 데이터 스트림이 존재합니다. 이들은 온라인 상에서 도착하며 연속적(continuous)이고 시간 순서(temporally ordered)를 따르며, 잠재적으로 무한할 수 있습니다. 데이터 스트림의 요소는 한 번 처리되면 버려지거나 아카이브되며, 메모리에 명시적으로 저장하지 않는 한 다시 가져올 수 없습니다.
스트림 데이터 질의 처리 아키텍처는 세 가지 요소로 구성됩니다. 바로 최종 사용자(end-user), 질의 처리기(query processor), 그리고 스크래치 공간(scratch space, 주기억장치와 디스크를 포함)입니다. 사용자가 DSMS에 질의를 보내면, 질의 처리기는 이 질의를 받아 스크래치 공간에 저장된 데이터를 이용해 처리한 후 결과를 사용자에게 반환합니다.
질의는 일회성 질의(one-time query)와 연속 질의(continuous query)로 나눌 수 있습니다. 일회성 질의는 특정 시점의 데이터 집합 스냅샷에 대해 한 번만 계산되며, 그 결과가 사용자에게 반환됩니다. 반면 연속 질의는 새로운 데이터 스트림이 계속 도착하는 동안 지속적으로 평가됩니다.