획기적인 CVM 알고리즘으로 40년 이상의 계산 문제를 해결합니다! 컴퓨터 과학자가 동전을 던져 '햄릿'이라는 고유한 단어를 알아냈습니다.

세는 것은 간단해 보이지만 실제로 구현하기는 매우 어렵습니다.

당신이 야생 동물 인구 조사를 실시하기 위해 깨끗한 열대 우림으로 보내졌다고 상상해 보세요. 동물을 볼 때마다 사진을 찍어보세요.

디지털 카메라는 추적된 동물의 총 수만 기록하는데, 고유한 동물의 수에 관심이 있지만 통계가 없습니다.

그럼, 이 독특한 동물을 손에 넣을 수 있는 가장 좋은 방법은 무엇일까요?

이쯤 되면, 이제부터 세기 시작하고, 마지막으로 사진에 나온 새로운 종들을 목록까지 비교해 보도록 하겠습니다.

그러나 이 일반적인 계산 방법은 최대 수십억 항목에 달하는 정보 양에 적합하지 않은 경우가 있습니다.

인도 통계 연구소, UNL 및 싱가포르 국립 대학교의 컴퓨터 과학자들이 새로운 알고리즘인 CVM을 제안했습니다.

긴 목록에 있는 다양한 항목의 수를 대략적으로 계산할 수 있으며 소수의 항목만 기억하면 됩니다.

문서 주소: https://arxiv.org/pdf/2301.10191

이 알고리즘은 연설문, 상품 등 한 번에 하나의 항목이 나타나는 모든 목록에 적합합니다. 컨베이어 벨트, 또는 주간 고속도로의 자동차.

CVM 알고리즘은 세 저자의 첫 글자를 따서 명명되었으며 "다른 요소 문제"를 해결하는 데 상당한 진전을 이루었습니다.

이 문제는 40년 넘게 컴퓨터 과학자들을 괴롭혀 왔습니다.

요소 스트림(총 개수가 사용 가능한 메모리를 초과할 수 있음)을 모니터링하고 그 안에 있는 고유 요소 수를 추정하는 효율적인 방법이 필요합니다.

그렇다면 CVM 알고리즘은 어떻게 문제를 해결할까요?

선도적인 CVM 알고리즘, 그 비결은 '무작위화'에 있습니다

당신이 "햄릿" 오디오북을 듣고 있다고 가정해 보세요.

이 드라마는 총 30557개의 단어로 구성되어 있는데, 몇 개나 다른가요?

답을 찾으려면 듣는 동안 잠시 멈추고 각 단어를 알파벳 순서로 쓴 다음 이미 목록에 있는 단어를 건너뛰고 마지막으로 목록에 있는 각 단어의 수를 세어보세요.

이 방법은 가능하지만 "기억"을 너무 많이 테스트합니다.

연구원 Vinodchandran Variyam은 "일반적인 데이터 흐름 상황에서는 추적해야 할 항목이 수백만 개일 수 있습니다. 모든 정보를 저장하고 싶지 않을 수도 있습니다.

이것이 바로 클라우드 서버이며, 알고리즘이 더 간단한 정보를 제공할 수 있습니다. 행동 양식".

비결은 "무작위화"입니다.

Vinodchandran Variyam은 데이터 스트림의 개별 요소 수를 추정하기 위한 CVM 알고리즘을 발명하는 데 도움을 주었습니다.

"Hamlet"에는 몇 개의 고유 단어가 있습니까? 동전 뒤집기 챌린지

당신의 "유효 기억력"이 100단어만 담을 수 있다고 가정하고, "햄릿"으로 돌아가세요.

오디오 재생이 시작되면 처음 듣는 100개의 단어를 적고 반복되는 단어는 건너뜁니다.

100단어 녹음이 끝나면 남은 것은 각 단어에 대해 동전을 던지는 것뿐입니다.

머리여, 단어를 지키세요. 반대면이면 삭제하세요.

예선 라운드가 끝나면 약 50개의 단어가 남게 됩니다.

이제 팀에서 1라운드라고 부르는 작업으로 넘어가서 계속해서 Hamlet을 읽고 새로운 단어를 추가합니다.

이미 목록에 있는 단어를 다시 만나면 메모리 화이트보드에 100단어가 될 때까지 동전을 다시 뒤집어보세요.

그런 다음 100번의 동전 던지기 결과를 바탕으로 대략 절반의 단어가 다시 무작위로 삭제됩니다. 1라운드는 여기서 끝납니다.

다음으로 2라운드 2차에 돌입합니다.

첫 번째 라운드와 마찬가지로 단어의 난이도를 높일 예정입니다. 반복되는 단어가 나타나면 동전을 다시 뒤집으세요.

조건은 꼬리라면 예전처럼 삭제. 하지만 앞면이면 동전을 다시 뒤집어보세요. 단어는 두 번째로 앞면이 나타날 경우에만 유지됩니다.

메모리 화이트보드가 가득 차면 라운드를 종료하고 100번 던진 결과에 따라 다시 절반 정도의 단어를 삭제합니다.

3라운드에서는 단어를 유지하려면 동전 앞면을 세 번 연속 뒤집어야 합니다.

4라운드에서는 단어를 앞면에 4번 연속으로 유지하는 식입니다.

드디어 k회차에서는 '햄릿' 전곡을 듣게 됩니다.

이 연습의 요점은 각 단어의 발생 확률이 1/2(k)로 동일하도록 하는 것입니다.

햄릿 오디오가 끝날 때 목록에 61개의 단어가 있고 완료하는 데 6라운드가 걸렸다고 가정해 보세요.

61을 확률 1/2(6)로 나누어 다양한 단어 수를 추정할 수 있습니다. 이 게임의 최종 결과는 3904입니다.

알고리즘의 정확도는 메모리 양에 비례합니다

연구원 Chakraborty, Variyam 및 Meel은 CVM 알고리즘의 정확도가 메모리 양에 비례한다는 것을 수학적으로 증명했습니다.

그리고 햄릿에는 우연히 3967개의 고유한 단어가 있습니다. (일반적인 계산 방법)

100 단어 기억을 사용한 실험에서 5회 실험 결과의 평균 추정치는 3955 단어입니다.

메모리에 1000단어로 평균 메모리 용량이 3964로 늘어났습니다.

Variyam은 "(메모리)가 모든 단어를 수용할 만큼 크다면 100% 정확도를 달성할 수 있습니다"라고 말했습니다.

하버드 대학교의 William Kuszmau는 "이것은 매우 기본적이고 널리 연구된 문제에서도 때로는 간단하지만 명확하지 않은 해결책이 여전히 발견될 수 있음을 보여주는 훌륭한 예입니다."라고 말했습니다.