🏠︎ | #️⃣ 💾 📃 🔗 | ✏️ 🗑

(번역) 거의 완벽에 가까운 새로운 도서 분류 알고리즘 

컴퓨터 과학자들은 종종 이해하기 어려운 추상적인 문제를 다루지만, 책과 서가를 하나 이상 소유하고 있는 사람이라면 흥미로운 새 알고리즘이 중요합니다. 이 알고리즘은 라이브러리 정렬 문제(보다 공식적으로는 '목록 라벨링' 문제)를 해결합니다. 이 문제는 새 책을 서가에 배치하는 데 걸리는 시간을 최소화하는 일종의 정렬된 순서(예: 알파벳순)로 책을 정리하는 전략을 고안하는 것입니다.

예를 들어, 서가의 맨 오른쪽에 빈 공간을 남겨두고 책을 한데 모아 보관한다고 상상해 보세요. 그런 다음 이사벨 아옌데의 책을 컬렉션에 추가하면 그 책을 위한 공간을 만들기 위해 선반의 모든 책을 옮겨야 할 수도 있습니다. 이는 시간이 많이 걸리는 작업입니다. 더글러스 애덤스의 책을 추가하려면 이 모든 작업을 다시 해야 합니다. 더 나은 배열은 비어 있는 공간을 서가 전체에 분산 배치하는 것인데, 정확히 어떻게 분산 배치해야 할까요?

이 문제는 1981년 논문에서 소개된 것으로, 단순히 사서에게 정리 지침을 제공하는 것 이상의 의미를 지닙니다. 정리해야 할 항목이 수십억 개에 달할 수 있는 하드 드라이브와 데이터베이스의 파일 정리에도 이 문제가 적용되기 때문입니다. 비효율적인 시스템은 상당한 대기 시간과 막대한 전산 비용을 의미합니다. 연구자들은 몇 가지 효율적인 물품 보관 방법을 고안해냈지만, 오랫동안 최적의 방법을 찾고자 노력해왔습니다.

작년에 시카고에서 열린 컴퓨터 과학의 기초 컨퍼런스에서 발표된 연구에서 7명의 연구원으로 구성된 연구팀은 이론적 이상에 매우 근접한 항목 정리 방법을 설명했습니다. 이 새로운 접근 방식은 책장의 과거 내용에 대한 약간의 지식과 무작위성의 놀라운 힘을 결합한 것입니다.

미시간 대학교의 컴퓨터 과학자인 세스 페티는"오늘날 우리가 사용하는 많은 데이터 구조는 정보를 순차적으로 저장하기 때문에 이는 매우 중요한 문제"라고 말합니다. 그는 이 새로운 연구가 "매우 영감을 주었으며, 올해 제가 가장 좋아하는 논문 세 편 중 하나"라고 말했습니다.

범위 좁히기

그렇다면 잘 분류된 책장은 어떻게 측정할 수 있을까요? 일반적인 방법은 개별 항목을 삽입하는 데 걸리는 시간을 확인하는 것입니다. 물론 이는 애초에 얼마나 많은 항목이 있는지에 따라 달라지며, 일반적으로 n으로 표시되는 값입니다. 이사벨 아옌데의 예에서 새 책을 넣기 위해 모든 책을 옮겨야 할 때 걸리는 시간은 n에 비례하며, n이 클수록 시간이 더 오래 걸립니다. 따라서 서가에 책 한 권을 추가하는 데 n에 비례하는 시간보다 더 오래 걸리는 일은 절대 없습니다.

이 문제를 제기한 1981년 논문의 저자들은 평균 삽입 시간이 n보다 훨씬 짧은 알고리즘을 설계할 수 있는지 알고 싶었고, 실제로 더 나은 알고리즘을 설계할 수 있다는 것을 증명했습니다. 그들은 (로그 n)2에 비례하는 평균 삽입 시간을 보장하는 알고리즘을 만들었습니다. 이 알고리즘은 두 가지 특성을 가졌습니다: '결정론적'이어서 결정이 임의성에 의존하지 않는다는 점과 '매끄럽다'는 점. 즉, 삽입(또는 삭제)이 이루어지는 서가의 하위 섹션 내에 책이 고르게 분포되어 있어야 한다는 점입니다. 저자들은 이 상한선을 더 개선할 수 있는지에 대한 의문을 열어두었습니다. 40년 넘게 아무도 그렇게 하지 못했습니다.

그러나 그 사이 하한선은 개선되었습니다. 상한은 책을 삽입하는 데 필요한 최대 시간을 지정하는 반면, 하한은 가능한 가장 빠른 삽입 시간을 나타냅니다. 문제에 대한 확실한 해결책을 찾기 위해 연구자들은 상한과 하한 사이의 간격을 좁히기 위해 노력하며, 이상적으로는 둘이 일치할 때까지 노력합니다. 그렇게 되면 알고리즘은 최적의 알고리즘으로 간주되어 더 이상 개선할 여지를 남기지 않고 위와 아래에서 무한히 제한됩니다.

2004년에 한 연구팀은 라이브러리 정렬 문제에 대해 어떤 알고리즘이 할 수 있는 최선, 즉 궁극적인 하한이 로그 n이라는 것을 발견했습니다. 이 결과는 모든 유형의 알고리즘에 적용되는 가장 일반적인 버전의 문제와 관련이 있습니다. 같은 저자 중 두 명은 이미 1990년에 보다 구체적인 버전의 문제에 대한 결과를 확보하여 모든 평활 알고리즘의 경우 하한이(로그 n)2로 훨씬 더 높다는 것을 보여주었습니다. 그리고 2012년에 다른 팀은 무작위성을 전혀 사용하지 않는 결정론적 알고리즘에 대해서도 동일한 하한인(로그 n)2를 증명했습니다.

이 결과는 어떤 평활 또는 결정론적 알고리즘의 경우에도 1981년 논문에서 설정한 상한과 동일한 (로그 n)2보다 더 나은 평균 삽입 시간을 얻을 수 없음을 보여주었습니다. 즉, 이 상한선을 개선하려면 연구자들은 다른 종류의 알고리즘을 고안해야 했습니다. 스토니 브룩 대학교의 컴퓨터 과학자 마이클 벤더는"더 나은 결과를 얻으려면 무작위적이고 매끄럽지 않아야 합니다."라고 말합니다.

마이클 벤더는 직관적으로 이해되지 않는 접근 방식을 사용하여 도서관 분류 문제를 해결했습니다.

Michael Bender 제공

그러나 항목을 어느 정도 균등하게 분산시켜야 하는 매끄러움을 없애는 것은 실수처럼 보였습니다. (모든 책이 선반 왼쪽에 뭉쳐 있는 매끄럽지 않은 구성에서 발생한 문제를 기억하세요). 또한 동전 던지기와 같은 무작위적인 우연에 맡기는 것이 어떻게 도움이 될지도 분명하지 않았습니다. 벤더는 "직관적으로는 그것이 합당한 방향인지 명확하지 않았습니다."라고 말합니다.

그럼에도 불구하고 2022년, 벤더와 5명의 동료들은 무작위 알고리즘이 어떤 이점을 제공할 수 있는지 알아보기 위해 무작위 알고리즘을 시도해보기로 결정했습니다.

비밀스러운 역사

아이러니하게도 진전은 또 다른 제약에서 비롯되었습니다. 책장의 역사를 알 수 없는 알고리즘을 사용하는 데에는 개인정보 보호 또는 보안상의 이유가 있습니다. 카네기멜론 대학교의 윌리엄 쿠스몰은 "책장에 <그레이의 50가지 그림자>를 꽂아두었다가 꺼내도 아무도 알 수 없을 것"이라고 말했습니다.

2022년 논문에서 벤더, 쿠스마울, 그리고 4명의 공동 저자는 "역사 독립적이고" 비평활적이며 무작위화된 알고리즘을 개발하여 마침내 1981년의 상한선을 낮추고 평균 삽입 시간을 (로그 n)1.5로 줄였습니다.

쿠즈마을은 일반적으로 개인 정보 보호를 위해 사용되는 도구가 다른 이점을 제공할 수 있다는 사실에 놀랐다고 회상합니다. "마치 알고리즘을 더 빠르게 만들기 위해 암호화를 사용하는 것과 같습니다."라고 그는 말합니다. "좀 이상해 보이기도 하죠."

이 연구팀의 일원이 아니었던 조지아 공과대학교의헬렌 쉬도 깊은 인상을 받았습니다. 그녀는 보안 이외의 이유로 기록 독립성을 사용한다는 아이디어가 다른 많은 유형의 문제에 영향을 미칠 수 있다고 말했습니다.

격차 좁히기

벤더와 쿠스몰 등은 작년 논문을 통해 더 큰 발전을 이루었습니다. 이들은 다시 기록을 경신하여 상한을 (로그 n)배 (로그 n)3, 즉 (로그 n)1.000...1에 해당하는 값으로 낮췄습니다. 즉, 이들은 이론적 한계인 로그 n의 궁극적 하한에 매우 근접했습니다.

다시 한 번, 그들의 접근 방식은 매끄럽지 않고 무작위적이었지만 이번에는 알고리즘이 제한된 정도의 히스토리 의존성에 의존했습니다. 과거의 추세를 보고 미래의 이벤트를 계획하는 방식이었지만, 여기에는 한 지점까지만 해당됩니다. 예를 들어 나보코프, 네루다, 응 등 성이 N으로 시작하는 저자의 책이 많이 팔렸다고 가정해 보겠습니다. 알고리즘은 이를 바탕으로 더 많은 책이 들어올 것으로 추정하여 N 섹션에 약간의 여분의 공간을 남겨둡니다. 하지만 너무 많은 공간을 확보하면 유명 작가들이 한꺼번에 몰려들면 문제가 발생할 수 있습니다. 벤더는 "결정을 내릴 때 얼마나 많은 기록을 살펴볼지에 대해 전략적으로 무작위성을 부여하는 것이 좋은 방법이었습니다."라고 말합니다.

그 결과는 이전 작업을 기반으로 하여 변화했습니다. 페티는 "2022년 논문과는 완전히 다른 방식으로 무작위성을 사용했다"고 말했습니다.

시카고 대학교의 컴퓨터 과학자인 브라이언 휘트먼은 이 논문들이 이론적인 측면에서 "상당한 진전"을 이루었다고 말합니다. "그리고 응용 측면에서도 큰 개선의 잠재력을 가지고 있다고 생각합니다."

쉬도 동의합니다. "지난 몇 년 동안 동적 그래프를 저장하고 처리하기 위해 목록 라벨링에 기반한 데이터 구조를 사용하는 것에 대한 관심이 있었습니다. 이러한 발전은 거의 확실하게 일을 더 빠르게 만들 것입니다.

한편, 이론가들이 고려해야 할 것이 더 많습니다. 벤더는 "우리는 거의 로그 n을 할 수 있다는 것을 알고 있습니다."라고 말하며 "하지만 완전한 솔루션을 가로막는 아주 작은 틈새가 여전히 존재합니다."라고 말합니다. "상한선을 낮추는 것이 옳은지 하한선을 높이는 것이 옳은지 알 수 없습니다."

페티는 우선 하한이 변경될 것으로 예상하지 않습니다. "보통 이런 상황에서는 이렇게 가까운 간격이 있고 한쪽 경계는 매우 자연스럽고 다른 쪽 경계는 부자연스러워 보이면 자연스러운 쪽이 정답입니다."라고 그는 말합니다. "하지만 세상은 이상한 놀라움으로 가득 차 있습니다."라며 "향후 개선 사항이 상한값에 영향을 미쳐 로그 N까지 내려갈 가능성이 훨씬 더 높습니다."라고 덧붙였습니다.