동적, 스트리밍, 온라인 알고리즘 비교 (Dynamic, Streaming, and Online Algorithm)

Photo by Ahmad Odeh on Unsplash

최근, 저널에 제출했던 논문에 대한 심사 결과를 받았습니다. 논문의 주제는 온라인 알고리즘인데 스트리밍 알고리즘에 대한 문헌 검토가 부족하니 이를 보충하라는 평가를 받았습니다. 논문을 쓸 때 참조했던 다른 논문들에서는 스트리밍 알고리즘에 대한 내용을 발견하지 못했었는데 이런 평가를 받아서 처음에는 적잖이 당황했습니다. 그런데 이 내용들을 공부해 보니 서로 비슷하면서도 다른 특징들이 있더군요. 우리말로 적힌 자료는 찾기 어려웠어서, 제 공부를 겸해 이번에 알게 된 내용들을 여기에 정리하고자 합니다.

 

아래 내용을 미리 요약을 하자면 다음과 같습니다.

• 동적 알고리즘(dynamic algorithm)은 입력에 무언가 추가되거나 삭제되는 등의 수정(update)이 발생하며 그때마다 바뀐 입력에 맞는 올바른 답을 유지하는 알고리즘을 일컫습니다. 성능을 평가하는 여러 척도가 존재하지만 가장 주요한 척도는 매번 수정이 일어날 때마다 기존의 답에서 새로운 답을 얻는데 소요되는 시간입니다.
• 스트리밍 알고리즘(streaming algorithm)은 입력이 데이터 스트림(data stream)으로 주어지나 알고리즘이 활용할 수 있는 메모리 공간이 스트림 전체는 담을 수 없는 매우 협소한 상태에서 스트림을 한 번 (혹은 몇 번) 순회하여 올바른 답을 출력하는 알고리즘을 말합니다. 단, 그래프 문제에서는 입력이 간선(edge)의 스트림으로 주어지며, 공간이 너무 적으면 풀 수 있는 문제가 없기에, 정점(vertex)에 대한 정보까지는 모두 저장할 수 있지만 간선에 대한 정보는 모두 저장하지 못하는 알고리즘을 대개 다루며, 이를 준스트리밍 알고리즘(semi-streaming algorithm)이라고 부릅니다.
• 온라인 알고리즘(online algorithm)은 처음에 입력의 일부만 주어지고 시간이 흐름에 따라 조금씩 남은 입력이 알려지는 상황에서, 새로운 입력이 들어올 때마다 매번 결정을 하는 알고리즘을 뜻합니다. 이때 많은 경우 과거에 결정한 내용은 번복할 수 없습니다. 온라인 알고리즘의 성능은 최종 결과와 비교했을 때 알고리즘이 얼마나 근사하는 답을 출력하는지에 따라 결정이 되며, 이 분석 기법을 경쟁성 분석(competitive analysis)이라고 합니다.

사실 세 개념이 칼로 무를 썰 듯이 딱 구분되는 것은 아닙니다. 어떤 온라인 알고리즘은 스트림을 한 번 순회하는 스트리밍 알고리즘으로도 볼 수 있고, 어떤 동적 알고리즘의 입력에 매번 무언가가 추가만 된다면 온라인 알고리즘처럼 볼 수도 있겠죠. 하지만 각 개념이 탄생한 배경과 추구하는 방향, 성능 평가의 척도 등은 서로 다릅니다. 그 때문에 위와 같이 개념을 나누어 놓는 것이 의미가 있습니다.

 

들어가기 전에 한 가지 짚고 넘어 가겠습니다. 구글, 다음, 네이버 등에 "동적 알고리즘"이나 "dynamic algorithm"을 검색하니 동적 계획법(dynamic programming)에 대한 내용이 많이 나오더라고요. 허나 이번에 제가 소개할 동적 알고리즘은 동적 계획법과는 완전히 무관한 내용이니 착오 없으시기 바랍니다.

동적 알고리즘(Dynamic Algorithm)

우리가 컴퓨터로 어떤 문제를 푼다고 합시다. 그러면 십중팔구 우리는 다음과 같은 과정을 떠올릴 겁니다.

1. 입력을 받는다.
2. 문제를 해결하는 어떤 알고리즘을 수행한다.
3. 답을 출력한다.

이때 마지막 단계에서 답을 출력하면 그것으로 모든 상황이 종결됩니다. 따라서 다른 입력이 주어지면 우리는 위 과정을 다시금 밟아서 그 입력에 맞는 새로운 답을 도출해야 합니다.

Photo by Timon Studler on Unsplash

허나 세상은 항상 조금씩 계속 변화합니다. 매일 출퇴근 시간에는 답답하게 막힌 도로가 점점 풀리더니 나중에는 뻥 뚫리기도 하고, 한산하던 온라인 게임 내에서도 저녁이 오면 접속자가 몰려 게임이 버벅이는 상황이 발생하기도 하죠. 이렇게 점진적으로 변화하는 상황 속에서 우리는 그때마다 가장 적합한 답을 찾기를 원합니다. 이때 만약 우리가 앞에서 본 전통적인 알고리즘으로 그때그때 답을 찾는다면 어떻게 될까요? 매번 변화가 일어나면 그 자체가 하나의 새로운 입력이 되고, 따라서 그때마다 우리는 알고리즘을 백지부터 새로 돌려 답을 찾아야 합니다.

 

생각해 보면, 이는 매우 멍청한 방법입니다. 언젠가 우리가 현재 상태에 가장 알맞는 답을 갖고 있는데 상태가 아주 약간만 바뀌었다고 해 봅시다. 그러면 이전에 갖고 있던 답이 모르긴 몰라도 변화 후에도 여전히 올바른 답을 유추하는데 큰 도움이 될 겁니다. 이를 활용한다면 완전히 처음부터 시작하는 것보다 훨씬 빠른 속도에 필요한 답을 유지할 수 있을 것입니다.

 

이 아이디어를 정형화한 것이 바로 동적 문제(dynamic problem)와 동적 알고리즘(dynamic algorithm)입니다. 이러한 문제의 입력에는 일련의 수정(update)이 발생하게 되고, 이 문제를 해결하는 알고리즘은 입력이 수정될 때마다 무언가를 작업해 주었다가 답이 필요한 순간에 올바른 답을 출력해야 합니다.

 

그렇다면 어떤 동적 알고리즘을 좋다고 말할 수 있을까요? 그 성능을 평가하는 척도는 다양하지만, 그중에서도 결국 매 수정마다 수행 시간이 얼마큼 빠른지가 제일 중요한 척도라고 보입니다. 앞에서 설명한 대로 입력이 수정될 때마다 매번 전통적인 알고리즘을 수행하는 것보다 빠르게 대응하는 것이 동적 문제의 존재 의의라고 생각하기 때문입니다.

 

여기서 또 크게 두 가지 정도로 성능을 평가하는 방법이 나뉩니다. 바로, 최악 상황 분석(worst-case analysis)과 분할 상환 분석(amortized analysis)인데요. 전자는 수정이 일어날 때 최악의 경우 알고리즘이 동작하는 수행 시간이 얼마인지를 분석하는 것이며, 후자는 지금까지 알고리즘이 동작한 총 시간에서 현재까지 입력이 수정된 횟수를 나누어 매번 수정이 발생할 때 알고리즘이 평균적으로 소요하는 시간을 분석하는 것입니다. 당연히 최악 상황 분석을 통해 얻은 수치는 분할 상환 분석에서도 의미가 있지만 분할 상환 분석에서의 값은 일반적으로 최악 상황 분석을 할 때 아무런 도움이 되지 않습니다. 이에 대한 자세한 내용은 나중에 다루어 볼 기회가 있으면 좋겠네요.

예제: 동적 최소 신장 포레스트(Dynamic Minimum Spanning Forest)

컴퓨터 과학에서 동적 알고리즘이 가장 활발히 연구된 분야 중 하나는 네트워크(network) 분야입니다. 우리가 여러 사용자가 있는 어떤 망을 관리한다고 해보죠. 그러면 망이 시시각각 변한다는 것을 쉽게 떠올릴 수 있습니다. 사용자가 새로 들어오면 그 사용자가 망을 이용할 수 있도록 적절히 연결해 주어야 할테고, 어느 회선에 너무 많은 트래픽이 몰리면 이를 순회하도록 만들어 주기도 해야 합니다.

 

그러한 문제 중에서 가장 간단한 문제를 생각해 봅시다. 입력으로는 어떤 동적 그래프(dynamic graph) \(G = (V, E) \)와 간선 비용 \(c : E \to \mathbb{Q}\)가 주어지며, 이 그래프에는 다음의 수정을 적용할 수 있다고 합시다.

• \( \mathsf{insert}(u, v, c) \): \(u\)와 \(v\) 사이에 간선을 추가하고 그 비용 \(c(u, v)\)를 입력된 \(c\)로 한다.
• \( \mathsf{delete}(u, v) \): \(u\)와 \(v\) 사이의 간선을 제거한다.

우리의 목표는 매번 그래프가 수정되면, 그때의 최소 신장 포레스트(minimum spanning forest)를 유지하는 것입니다. 참고로 어떤 그래프의 연결 성분의 최소 신장 트리(minimum spannning tree)를 합치면 최소 신장 포레스트가 됩니다.

 

예를 들어 다음과 같이 어떤 그래프가 주어지고 우리 알고리즘이 이에 맞는 최소 신장 포레스트를 찾았다고 합시다.

그림 1.동적 그래프와 그 위의 최소 신장 포레스트의 예시.

여기서 \(\mathsf{insert}(a,d,5)\)가 발생하면, 우리 알고리즘은 다음과 같이 동작해야 합니다.

그림 2. \(\mathsf{insert}(a, d, 5)\)를 수행하는 동작 예시.

반면, 처음 상태에서 \( \mathsf{delete}(b, e) \)가 일어나면, 우리 알고리즘은 다음과 같이 동작해야겠죠.

그림 3. \( \mathsf{delete}(b, e) \)를 수행하는 동작 예시.

일반적으로 최소 신장 포레스트는 거의 \( O(|E|) \) 시간에 해결할 수 있습니다. 따라서 위 동작을 모두 아선형(sublinear) 시간에 할 수 있는지가 관건이죠. 실지로 위 작업을 \( O(\sqrt{|E|}) \) 시간에 수행시키는 알고리즘이 이 문제를 해결하는 자명하지 않은 첫 번째 알고리즘이었고, 이후 향상된 성능을 보이는 다양한 알고리즘이 만들어 졌습니다. 아직 해당 논문들을 제대로 읽어 보지는 않아서 더 이상의 설명을 드리기는 어렵군요. 나중에 기회가 되면 포스팅해 보도록 하겠습니다.

스트리밍 알고리즘(Streaming Algorithm)

앞에서 컴퓨터로 문제를 해결하는 단계는 다음과 같다고 하였습니다.

1. 입력을 받는다.
2. 문제를 해결하는 어떤 알고리즘을 수행한다.
3. 답을 출력한다.

다시, 첫 번째 단계를 살펴 보죠. 이전 절에서는 입력이 고정되어 있다는 점을 꼬집었다면, 이번에는 입력의 크기로 시비를 걸어 봅시다. 사실 위와 같이 전통적인 알고리즘에서 우리는 입력이 모두 메모리에 올라간다고 가정합니다. 이는 동적 알고리즘에서도 동일하죠.

Photo by nik radzi on Unsplash

과거에는 그랬을지 몰라도, 현재는 다릅니다. 여러분의 SSD의 모든 자료를 16GB뿐인 RAM에 몽땅 올리는 것은 불가능하겠죠. 우리집 컴퓨터만 해도 이럴진데 구글이나 아마존 같은 거대 공룡 기업들이 운용하는 데이터의 양은 어떨까요? 그들이 하루에 처리하는 데이터 양은 페타바이트(PB) 단위라고 합니다. 하루에요. 따라서 모든 입력이 메모리에 올라간다는 가정은 어떤 상황에서는 전혀 가망이 없습니다.

 

이를 타개하기 위한 기법이 바로 데이터 스트림(data stream)입니다. 가장 쉬운 예시로는 유튜브와 같은 동영상 스트리밍 서비스가 있습니다. 유튜브 영상 전체의 크기가 어느 정도 할 것 같나요? 저는 잘 모릅니다만 요새 유튜브가 최대 2K까지 지원을 하는 것 같으니, 못해도 기가바이트 단위일 겁니다. 그런데 만약 영상을 볼 때 영상 전체를 다운로드하고 그 후에야 재생이 된다면 어떨까요? 아주 느리고 불편할 겁니다. 대신 영상 정보를 (모종의 방법으로) 길게 나열하고, 앞에서부터 순차적으로 넣어서 그때그때 처리하게 한다면 많은 공간을 사용하지 않고도 충분히 영상을 시청할 수 있게 되는 것이죠.

 

스트리밍 알고리즘(streaming algorithm)은 이러한 데이터 스트림이 입력으로 주어집니다. 대신 알고리즘이 가용할 수 있는 메모리 공간은 매우 작습니다. 대개, 데이터 스트림의 길이를 \(N\)이라고 했을 때, \( O(\log^c N) \) 정도의 공간을 가정합니다. 이때 \(c\)는 특정한 상수를 의미하며, 이는 데이터 스트림 내용 전체를 올리기에는 턱도 없는 수치죠.

 

이러한 상황에서 스트리밍 알고리즘의 목표는 데이터 스트림을 한 번 (혹은 몇 번) 돌아서 주어진 공간 내에서 원하는 답을 찾는 것입니다. 이때 전체 스트림을 한 번만 도는 알고리즘을 원 패스(one-pass) 알고리즘, 수차례 도는 알고리즘을 멀티 패스(multi-pass) 알고리즘이라고 부릅니다.

예제: 빠진 숫자 찾기

다음 간단한 문제를 함께 봅시다.

영희에게는 1부터 N까지가 적힌 카드가 정확히 한 장씩 있습니다. 어느 날, 철수가 영희의 카드를 가지고 놀다가 한 장을 잃어버렸죠. 화가 난 영희는 철수보고 잃어버린 카드를 사오라고 했습니다. 여기서 문제는 무슨 카드를 잃어버렸는지 철수가 모른다는 점이죠. 게다가 카드를 마구잡이로 가지고 논 탓에 카드들이 몽땅 뒤섞여 버렸습니다. 과연 모든 카드를 정확히 한 번씩만 보고 잃어버린 카드의 숫자를 알아낼 수 있을까요?

만약 N이 작다면 메모리에 길이가 N인 배열을 만들고 카드의 숫자가 나올 때마다 해당하는 배열 칸에 곱표를 치면 됩니다. 최종적으로 곱표가 없는 칸이 답이 되겠죠. 하지만 N이 무진장 크다면 메모리에 길이가 N인 배열을 만들 수 없겠죠. 따라서 그보다 훨씬 똑똑한 방법이 필요합니다.

 

방법은 다음과 같습니다. 철수가 \(i\) 번째로 본 카드의 숫자를 \( \pi_i \)라고 하겠습니다. 그리고 매 \(i\) 번째 카드를 본 후에는 다음 값을 기록해 놓습니다. \[ \frac{N(N+1)}{2} - \sum_{j = 1}^i \pi_i \tag{1} \] 첫 번째 항은 1부터 N까지를 모두 더한 값이고, 두 번째 항은 지금까지 본 숫자들의 합입니다. 그러면 마지막 카드를 본 후에 기록된 값이 곧 빠진 숫자가 된다는 것을 쉽게 알 수 있습니다.

 

문제는 공간입니다. 철수가 사용한 공간의 크기는 얼마쯤일까요? N의 값을 표현하기 위해서 필요한 비트(bit) 수는 \( \log N \) 정도입니다. 매번 식 1이 계산된 값은 \(N^2\)을 넘지 않을 것이므로 이를 표현하는데 필요한 비트 수는 \(  2 \log N \)을 넘지 않습니다. 따라서 \( O(\log N) \) 비트 정도의 공간을 사용하게 되죠. 이는 스트리밍 알고리즘의 정의에 부합합니다.

그래프 스트림(Graph Stream)과 준스트리밍 알고리즘(Semi-Streaming Algorithm)

그래프 문제에도 스트리밍 알고리즘을 적용해 볼 수 있습니다. 이때 입력으로 주어지는 스트림은 대개 간선이 하나씩 들어오는 스트림이며, 이를 그래프 스트림(graph stream)이라고도 합니다. 그런데 \( O(\log^c |E|) = O(\log^c |V|) \)이기 때문에 스트리밍 알고리즘이 가용할 수 있는 공간의 크기가 너무 작습니다. 따라서 스트리밍 알고리즘으로는 간단한 그래프 문제도 해결하지 못한다는 것이 증명되었다고 합니다. 이는 너무 빡빡하기 때문에 그래프 스트림에서는 일반적으로 가용할 수 있는 공간을 \( O(|V| \log^c |V|) \)로 확장해 줍니다. 이는 정점에 관련된 정보는 충분히 담을 수 있지만 간선에 관련된 정보(즉, 그래프 스트림 전체 정보)는 모두 담을 수 없는 크기입니다. 이 정도의 공간을 가용할 수 있는 스트리밍 알고리즘을 준스트리밍 알고리즘(semi-streaming algorithm)이라고 부르며, 많은 그래프 문제에 대한 흥미로운 결과들이 이 알고리즘을 기초로 발견되었습니다.

온라인 알고리즘(Online Algorithm)

Photo by Tegan Mierle on Unsplash

온라인 알고리즘(online algorithm)은 동적 알고리즘과 스트리밍 알고리즘과는 결이 또 다릅니다. 살다 보면 우리에게는 무언가를 결정해야 하는 순간이 찾아 옵니다. 오늘 점심은 무엇을 먹을지나 이 주식을 구매할지와 같은 비교적 개인적인 순간은 물론 회사의 의사 결정이나 국가의 중차대한 정책의 시행과 같은 사회 전반에 큰 영향을 주는 순간까지 매우 넓은 스펙트럼을 보이죠. 문제는 많은 경우 그 결정을 뒤집을 수 없거나, 만약 뒤집는다고 하더라도 너무 많은 비용을 감내해야 한다는 점입니다. 하지만 이런 상황 속에서도 여전히 우리는 최대한 좋은 선택을 하고자 하죠. 이러한 현상을 컴퓨터 과학의 세계에 투영한 결과물이 바로 온라인 알고리즘입니다.

 

탐욕 알고리즘(greedy algorithm)이 아닌 한, 대개의 경우 전체 입력을 보기 전에 미리 결정하게 되면 최종 최적해에 비해 좋지 않은 답을 출력할 수 밖에 없겠죠. 따라서 최종 최적해에 비해 얼마큼 좋은 답을 출력했는지가 온라인 알고리즘의 성능을 판단하는 주요 척도가 됩니다. 이 비율을 경쟁비(competitive ratio)라고도 부르며, 이러한 분석 방식을 경쟁성 분석(competitive analysis)이라고도 합니다.

 

온라인 알고리즘에 대한 설명은 이 정도로 마무리하겠습니다. 이에 대해 더 자세한 설명이 필요하신 분은 아래 포스트를 참고하시기 바랍니다.

2020/03/14 - [온라인 알고리즘/Basic] - 온라인 알고리즘 (Online Algorithm)

온라인 알고리즘 (Online Algorithm)

마치며

이 글에서는 동적 알고리즘, 스트리밍 알고리즘, 온라인 알고리즘을 서로 비교해 보았습니다. 서로가 완전히 배타적으로 각자의 영역을 갖고 있는 것은 아니지만, 각 패러다임의 연구가 시작된 배경 혹은 알고리즘의 목표나 제약 조건 등은 확연히 차이를 보입니다.

	동적 알고리즘	스트리밍 알고리즘	온라인 알고리즘
개요	동적으로 변화하는 입력에 대해 효율적으로 대응하는 방법	매우 큰 데이터 스트림이 입력될 때 작은 공간으로 해결하는 방법	과거의 선택을 번복할 수 없을 때 최대한 좋은 결과를 내는 방법
주요 척도	매 수정마다의 수행 시간	패스의 횟수, 수행 시간, 사용 공간, 답의 근사비	답의 경쟁성
제약 조건	딱히 없음	\(O(\log^c n)\)의 공간	선택의 비번복성 (혹은 번복의 최소화)

글을 마치는 이때, 저널에 수정본을 다시 제출하였습니다. 이번에는 좀더 좋은 결과가 있기를 기대합니다. 글에 잘못된 점이 있거나 궁금하신 점이 있으시면 알려주세요. 특히 이번에는 제가 평소 공부하던 분야랑은 또 다른 분야여서 잘못 이해한 내용이 있을 수도 있겠다 싶기는 합니다. 긴 글을 읽어 주셔서 고맙습니다. :)

참조

[1] Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano. "Dynamic graphs." (2004): 36-1.

 

[2] Shanmugavelayutham Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005.