고유 항목 수를 효율적으로 세는 새 알고리듬

• CVM 알고리듬은 긴 데이터 스트림에서 서로 다른 항목 수를 근사해, 목록 전체를 저장하지 않고도 고유 항목 수를 추정함
• 전체 입력이 메모리를 넘는 고유 항목 문제(distinct elements problem) 에 초점을 맞추며, 중복 입력이 많은 대규모 로그나 이벤트 스트림에 적용될 수 있음
• 제한된 메모리에 일부 항목만 남기고 공간이 찰 때마다 무작위 삭제를 반복해, 각 항목이 남을 확률을 균등하게 맞춤
• Hamlet 예시에서는 메모리 100단어로 5회 평균 3,955개를 추정해 실제 고유 단어 수 3,967개에 가까웠고, 메모리 1,000단어에서는 평균 3,964개로 개선됨
• 메모리가 커질수록 정확도가 높아지며, 모든 고유 항목을 담을 만큼 충분하면 100% 정확도도 가능함

---

긴 데이터 스트림에서 고유 항목 세기

• 목표는 항목이 하나씩 들어오는 긴 목록에서 중복을 제거한 고유 항목 수를 효율적으로 추정하는 것임
• 가장 단순한 방식은 지금까지 본 모든 항목을 저장하고, 새 항목이 들어올 때마다 기존 목록과 비교하는 것임
  • 야생동물 조사에서는 이미 본 동물 사진 목록을 계속 확인해야 함
  • Facebook의 일일 로그인 사용자 수처럼 목록이 수십억 단위가 되면 저장과 비교가 어려워짐
• CVM은 Sourav Chakraborty, Vinodchandran Variyam, Kuldeep Meel의 이름에서 따온 알고리듬임
• 단어, 컨베이어 벨트의 상품, 고속도로의 차량처럼 항목이 순차적으로 들어오는 목록에 적용될 수 있음

CVM 알고리듬의 핵심 아이디어

• CVM은 모든 항목을 저장하지 않고, 제한된 메모리에 들어가는 일부 항목만 유지함
• 각 고유 항목이 최종 목록에 남을 확률을 통제하기 위해 무작위성을 사용함
• Andrew McGregor는 이 알고리듬이 매우 단순하고 구현하기 쉬워, 실제 고유 항목 문제의 기본 접근법이 될 수도 있다고 봄

Hamlet 예시로 본 동작 방식

• Hamlet에는 총 30,557개의 단어가 있으며, 알고리듬은 이 중 고유 단어 수를 추정함
• 메모리가 100단어짜리 화이트보드라고 가정하면, 처음에는 반복 단어를 건너뛰며 첫 100개 고유 단어를 적음
• 공간이 가득 차면 각 단어마다 동전을 던짐
  • 앞면이면 단어를 유지함
  • 뒷면이면 단어를 삭제함
  • 이 예비 단계 뒤에는 약 50개의 고유 단어가 남음

라운드가 지날수록 엄격해지는 유지 조건

• Round 1에서는 새 단어를 계속 추가하고, 이미 목록에 있는 단어가 다시 나오면 동전을 던져 뒷면일 때 삭제함
• 목록이 다시 100단어로 차면 100번의 동전 던지기 결과에 따라 약 절반을 삭제하며 Round 1이 끝남
• Round 2부터는 단어가 살아남기 더 어려워짐
  • 반복 단어가 나오면 뒷면일 때 삭제함
  • 앞면이 나오면 한 번 더 동전을 던지고, 두 번째도 앞면일 때만 유지함
• 세 번째 라운드에서는 앞면이 연속 3번 필요하고, 네 번째 라운드에서는 연속 4번 필요함
• 일반적으로 k번째 라운드가 끝날 때 각 단어가 남아 있을 확률은 1/2^k가 됨

추정값 계산과 실험 결과

• 최종 목록에 남은 단어 수를 남아 있을 확률로 나누면 전체 고유 단어 수를 추정할 수 있음
• 예를 들어 6라운드 뒤 61개 단어가 남았다면, 확률 1/2^6으로 나눠 3,904개라는 추정값을 얻음
• Hamlet의 실제 고유 단어 수는 3,967개임
• 메모리 크기가 커질수록 추정값이 실제값에 가까워짐
  • 메모리 100단어로 5회 실행한 평균 추정값은 3,955개
  • 메모리 1,000단어로는 평균 추정값이 3,964개
• Variyam과 동료들은 이 기법의 정확도가 메모리 크기에 따라 확장됨을 수학적으로 증명함

단순하지만 비자명한 해결책

• CVM은 40년 넘게 연구된 고유 항목 문제에서 중요한 진전으로 평가됨
• William Kuszmaul은 아주 기본적이고 잘 연구된 문제에도 단순하지만 쉽게 떠올리기 어려운 해법이 남아 있을 수 있다고 봄

[GN⁺]

Hacker News 의견들

• 이 알고리즘의 DNF 부피 세기 버전 구현에 저자들과 함께 참여했음. 관련 글은 여기: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
  코드는 여기: https://github.com/meelgroup/pepin
  종종 전체 시간의 30%가 파일 읽기 입출력에 쓰일 정도로 알고리즘이 말도 안 되게 빠름. 참고로 Knuth도 알고리즘에 기여했고, 그의 노트는 여기: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
  TAOCP 작업에서 한 달을 통째로 빼서 이걸 했고, 상상하는 그대로 믿기 어려울 만큼 뛰어났음

  • 정말 흥미롭고, 비범하게 재능 있는 사람들에 관심이 많음. Knuth가 그렇게 대단하다고 느낀 이유가 궁금함. 특별한 순간이 있었는지, 아이디어를 이해하는 속도였는지, 아니면 쉽게 설명하는 능력이었는지 궁금함
  • 이건 멍청해 보임. 아주 멍청한데, 뭔가 놓치고 있는 건가? 이건 세기가 아니라 그냥 표본 추출이고, 실제로 모든 서로 다른 단어를 세고 싶다면 단순히 세는 것과 비교해 메모리 사용량이 달라지지 않는 것 같음
  • 혹시 알고 있을 것 같은데, 왜 더 큰 카운트를 우선하도록 정렬한 뒤 가득 차면 하위 절반을 버리는 방식을 택하지 않는지 궁금함. 다른 사람에게는 obvious할 수 있지만 이유가 알고 싶음
  • 이 알고리즘의 주요 활용처가 뭔지 궁금함
  • 이제 Knuth의 다음 책 출간이 늦어진 책임을 물을 사람이 생겼군 :)

• 이 알고리즘은 논문에서도 인용한 HyperLogLog와 닮아 보임. 앞면/뒷면이 연속으로 나오는지를 추적해 추정값을 얻는 같은 통찰을 쓰되, 아이디어를 뒤집어서 기억한 값을 동전 결과의 연속성에 따라 버리는 더 단순한 알고리즘으로 만든 느낌임
  스트리밍 상황에서 특히 효율적으로 작동해서, 오류율은 있지만 서로 다른 원소 수를 세는 “카운터” 비슷한 것을 유지할 수 있음
  HyperLogLog의 장점은 어떤 면에서 해시 집합처럼 동작한다는 것임. 항목을 추가하고, 서로 다른 항목 수를 세고, 중요하게는 두 HLL을 병합해 합집합을 만들 수 있으면서도, 수십억 항목 집합에서도 메모리는 몇 KB로 고정됨. 분산 데이터 저장소에서 Elasticsearch/OpenSearch의 cardinality agg, Redis/Redict의 PFADD/PFMERGE/PFCOUNT가 이 요령을 씀
  CVM 알고리즘이 HLL과 정확히 어떻게 비교되는지는 잘 모르겠지만, Knuth에게 검토를 받았고 학부생도 쉽게 구현할 수 있다고 하니 꽤 괜찮은 알고리즘일 것 같음

  • HLL은 두 HLL의 합집합과 교집합을 모두 추정할 수 있어서, 조인의 카디널리티 추정에도 사용할 수 있음
    http://oertl.github.io/hyperloglog-sketch-estimation-paper/
  • 이 자료구조들도 병합할 수 있음. 병합할 두 인스턴스의 “라운드”가 다르면, 더 이른 라운드에 있는 쪽을 라운드 차이만큼 진행시키면 됨. 즉 무작위로 절반을 버림. 그다음 한 목록의 값을 다른 목록에 넣고 중복은 무시함. 결과가 너무 크면 무작위로 절반을 버리고 라운드 번호를 올리면 됨
    이전 직장에서 정확히 이 알고리즘을 구현했는데, 각 값 옆에 그 값이 등장한 횟수의 추정치도 함께 저장했음. 덕분에 가장 흔한 값들의 근사 목록과 각 값의 추정 카운트를 만들 수 있었음
  • 오래전 학교 기억을 더듬어 보면 궁금한데, 여기서 말하는 HLL과 CVM은 예전에 배웠던 저수지 표본 추출과 어떤 관계가 있나?
    예전에 병원에서 일할 때, DAT 테이프에 저장된 레코드의 작은 부분집합을 만들려고 저수지 표본 추출을 쓴 적이 있음

• 논문을 읽는 데 블로그 글을 읽는 시간과 거의 비슷하게 걸렸고, 논문이 더 유익했음
  https://arxiv.org/pdf/2301.10191
  스트림에서 나온 원소 집합의 카디널리티를 추정하는 내용임. 알고리즘이 너무 단순해서 논문을 읽는 동안 직접 코딩해 보며 가지고 놀 수 있음
  저자들은 이 알고리즘의 대상 독자와 목적이 학부생과 교과서라고 명확히 밝힘

  • 논문 부제인 “An Algorithm for the (Text) Book”은, 단순함과 아름다움이 너무 우아해서 “The Book에서 나온” 증명 같다는 Paul Erdős의 유명한 표현을 가리키는 것 같음
    Knuth가 직접 검토했으니, 이 알고리즘이 그런 종류라고 평했을지도 모름. 그렇다면 저자들이 제목에 넣은 건 겸손하지 않은 자랑처럼 보이지만, 충분히 자랑할 만함
    원래는 이 표현을 Knuth가 한 것으로 기억했는데, 내 기억이 틀렸음
  • 블로그 글은 절반 이상이 padding이었음. 알고리즘이 너무 단순해서 긴 블로그 글로 쓰기 어렵다는 건 좋은 일이긴 함
  • 논문이 블로그 글보다 낫다는 데 동의하지만, CVM 논문에 대한 한 가지 비판은 종료 조건을 두고 있다는 점임. 다른 스레드에 나온 Knuth의 CVM 노트는 저수지 절반 줄이기 단계에서 공간이 더 생기도록 그냥 반복문을 둠
    https://en.wikipedia.org/wiki/Up_tack을 설명하는 것보다 그냥 반복문을 쓰는 편이 덜 번거로워 보임. [1]
    [1] https://news.ycombinator.com/item?id=40388878
  • 예전에 컴퓨터과학을 했지만 머리가 매끈해진 건지, 이건 필요 이상으로 헷갈려 보임
    먼저 contradiction 처리가 그냥 오류나 패닉 같은데 왜 그렇게 표현했는지 모르겠음. 또 1..m이라는 전제가 헷갈림. 크기를 미리 알아야 하는지 아닌지 확실하지 않았는데, 더 보면 아닌 것 같음. 임계값을 고르고 스트림 크기에 따라 확률이 바뀌지만, 알고리즘 설명은 단일 출력을 가진 것처럼 되어 있어 혼란스러움
    Chernoff 경계와 delta/epsilon도 논문에서 전혀 설명하지 않아서 더 헷갈렸음. Go로 구현해 본 코드는 여기: https://github.com/betamos/distinct
    임계값 관련 부분을 helper로 빼는 편이, 실수로 너무 많은 메모리를 할당하는 것보다 훨씬 말이 됨. 신뢰도나 오류율을 추정하는 메서드도 있어야 할 것 같음. 스트림 크기를 미리 아는 사람은 없으니 진행하면서 이 값을 갱신하는 편이 더 자연스러움
  • “학부생과 교과서용”이라는 말이, 그들이 쓰기에 충분히 단순하다는 뜻이 아니라 정말로 거기에만 유용하다는 뜻이라면, 왜 전문가에게는 유용하지 않고 학부생에게만 유용한지 설명해 주면 좋겠음

• 논문 주제를 생각하면 각주가 특히 매력적임
  저자들은 오래된 저자명 알파벳순 관례 대신 무작위 순서를 택했고, r⃝로 표시했다고 함. 무작위화의 공개 검증 가능한 기록은 여기 있음: https://www.aeaweb.org/journals/policies/random-author-order...
  [0]: https://arxiv.org/pdf/2301.10191

• 알고리즘 설명이 틀린 것 같지 않나?
  “목록에 이미 있는 단어를 만나면 다시 동전을 던지고, 뒷면이면 단어를 지운다”라는 설명대로 “목록에 있는지 확인한 뒤 삭제”를 구현하면 약 20회 반복되고 추정값이 772800512처럼 엉뚱하게 나옴
  반대로 단어를 먼저 저장한 다음 같은 단어를 삭제하면 실제 고유 단어 수 7233에 가까운 7240이 나옴. 즉 설명상 순서가 중요한데 잘못 전달된 것 같음

  • 같은 문제를 겪었음. Quanta Magazine 설명만 보고 arxiv 논문을 보지 않고 구현하면 항상 461746372167462146216468796214962164 같은 추정값이 나왔음
    논문을 읽은 뒤에는 올바른 추정값이 나왔고, 문제는 작은 else 하나였음. Quanta 설명은 “목록에 없으면 추가, 그렇지 않으면 확률에 따라 제거”처럼 읽히는데, 올바른 구현은 추가 여부와 무관하게 그 뒤 확률 조건을 적용해야 함
  • 방금 풀어보다가 다른 사람도 같은 문제를 겪었는지 보러 왔는데, 맞음. 설명대로 하면 틀리고, 라운드마다 새 값을 추가한 뒤 확률적으로 가지치기하고, 메모리가 한계에 닿으면 전체 집합에서 무작위 절반을 제거하는 식으로 구현해야 함

• 집합의 고유 원소 수를 추정하는 것과 집합의 고유 원소 수를 세는 것은 아주 다른 일임. 멋진 방법이지만 제목은 별로임

  • 둘은 그렇게까지 다르지 않음. 현실 세계의 모든 세기 방법에는 0이 아닌 오류율이 있어서, 대부분의 맥락에서는 두 용어가 서로 바꿔 쓰임
    예를 들어 선거에서 “표를 센다”고 하지만, 접전이면 “재검표”를 하고 원래 카운트와 약간 다른 숫자가 나올 수 있다고 충분히 예상함. 그러면 표 세기도 사실은 표 추정이고, 재검표는 더 좁은 오류 경계를 가진 추정일 뿐임
    “countless stones” 신화(https://en.wikipedia.org/wiki/Countless_stones)도 아무리 크고 단단하고 정적인 선돌 같은 것조차 제대로 셌다고 너무 확신할 수 없다는 민간적 상기처럼 느껴짐
    세기가 추정이 아닌 경우는 수학적 상황 정도로 제한됨. 모든 항목을 빠짐없이 다뤘고, 어떤 항목의 정체성을 다른 것과 혼동하지 않았다고 보장할 수 있을 때임
  • 상대적으로 작은 숫자에서는 맞음. 하지만 매우 큰 숫자에서는 보통 추정이 세기와 동등하게 취급되고, 결과도 정수가 아니라 과학적 표기법, 즉 부동소수점처럼 표현되기도 함
    예를 들어 몰은 정수지만 그 값은 근사적으로만 알려져 있고, 정확한 값에 신경 쓰는 사람도 없음
  • 이건 estimation이 아니라 approximation임

• 이런 식의 틀 밖에서 생각하기 예시를 정말 좋아함. 직업적으로도 잘 못하는 부분이라 더 그렇다. 문제를 푸는 올바른 방법만 배우는 게 아니라, 가진 문제를 더 쉽게, 때로는 가능하게 만들어 주는 질문을 찾아내는 과정이 중요함
  여기서는 “정확한 숫자가 필요하지 않고, 정의된 매개변수 안에서 확률적 범위를 정하면 된다”는 질문이 핵심임. 다른 문제에는 다른 질문이 있을 것임. 이런 예시를 충분히 보면 사고 과정을 내면화해서 제대로 적용할 수 있기를 바람

  • 공정하게 말하면, 이건 대학 연구팀이 한 일임. 말 그대로 하루 종일 한 주제를 과학적 방법으로 반복 검토할 수 있는 사람들의 팀임
    큰 회사에서 똑같이 똑똑한 엔지니어들과 하루 종일 화이트보드 앞에 앉아 있으라고 돈을 받는다면, 세상 사람들에게는 “틀 밖의 해법”처럼 보일 뭔가를 분명 만들어낼 수 있을 것임
    하지만 우리 대부분은 JIRA 공장 라인에서 일하라고 돈을 받기 때문에, 하나의 문제만 붙잡고 실험할 시간이 제한됨
  • 보통 수평적 사고라고 부르는 것 같음. Edward de Bono가 관련 책을 몇 권 썼는데 흥미로울 수 있음

• “Facebook에서 매일 로그인하는 서로 다른 사용자 수를 세고 싶고, 일부 사용자는 여러 기기와 여러 시점에서 로그인한다면?”이라는 예시는 이 알고리즘이 실제로 유용한 상황으로는 별로인 것 같음
  로그인 프로세스를 설계할 때 이 정보가 필요하다는 걸 이미 안다면 간단함. 각 계정의 마지막 로그인 날짜를 저장하고, 저장된 값이 현재 날짜와 다를 때만 고유 사용자 카운터를 증가시키면 됨
  설령 그렇지 않더라도, 나중에 데이터베이스에서 로그인 이벤트 스트림을 “재생”해서 분석할 수 있을 것임. 이미 수년치 데이터가 쌓여 있는 경우라면 다를 수 있음

  • 그 방식은 “각 계정의 마지막 로그인 날짜”를 추적해야 하므로 사용자 수만큼의 메모리가 필요함. 이 알고리즘의 핵심은 훨씬 작고 고정된 메모리로 수행하는 것임

• 세기 관련해서, 스트림에서 상위 k개 항목을 찾는 효율적이고 구현도 쉬운 알고리즘을 언급하고 싶음. 생각보다 덜 알려진 것 같음
  A Simple Algorithm for Finding Frequent Elements in Streams and Bags
  Karp, Shenker & Papadimitriou
  https://www.cs.umd.edu/~samir/498/karp.pdf

  • “스트림에서 상위 k개 항목”이라는 표현은 초록의 설명과는 다르게 들림. 초록은 큰 알파벳에서 오는 아주 긴 기호열에서 빈도가 주어진 임계값보다 높은 기호를 찾는다고 말함
    당신 설명은 고정된 k개 항목을 찾고 그것들이 반드시 최상위라는 보장을 주는 것처럼 들림. 초록은 특정 값 k보다 큰 조건을 만족하는, 사전에 개수를 알 수 없는 항목들을 찾는 것처럼 들림
    “가장 나이 많은 사용자 100명 찾기”와 “30세 넘는 모든 사용자 찾기”의 차이처럼 보이는데, 내가 당신 말이나 초록을 잘못 이해한 건가? 영어가 모국어가 아니라서 헷갈림

• 컴퓨터과학자들이 부분집합 크기를 메모리 효율적으로 추정하는 방법을 발명했군

  • 더 적은 라운드의 동전 던지기만으로 추정값을 얻을 수 있다면 빠르기도 해 보임. 서로 다른 단어 수를 추정하기 위해 “책” 전체를 끝까지 훑지 않아도 될 수 있음
  • 여기서 부분집합이 중요함. 바로 고유 원소들의 부분집합임