당신이 거대한, 몇 시간 길이의 복잡한 도시 거리 녹음 파일에서 특정하고 반복되는 소리를 찾으려는 탐정이라고 상상해 보십시오. 당신은 그 소리가 반복해서 발생한다는 것은 알지만, 그것이 얼마나 오래 지속되는지는 전혀 모릅니다. 그것은 짧고 날카로운 "삐-" 소리일까요? 길게 끌리는 "웅-" 하는 소리일까요? 아니면 중간 길이의 "치르르" 하는 소리일까요? 만약 당신이 전체 녹음을 계속해서 다시 들으며, 한 번은 "삐-" 소리라고 가정하고, 다음에는 "웅-" 소리라고 가정하고, 또 다음에는 "치르르" 소리라고 가정하며 추측하는 방식으로 시도한다면, 당신은 영원히 그곳에 머물게 될 것입니다. 이것은 심장 박동, 주식 가격, 또는 지진의 진동과 같이 시간이 흐름에 따라 변하는 숫자들의 목록인 시계열(time series) 데이터를 다루는 데이터 과학자들의 일상적인 고충입니다. 그들은 숨겨진, 반복되는 패턴인 **모티프(motifs)**를 찾고자 합니다. 까다로운 점은, 그들이 종종 그 "지속 시간"(패턴이 몇 초 또는 몇 개의 데이터 포인트 동안 지속되는지)을 미리 알지 못한다는 것입니다. 이를 해결하기 위해, 그들은 보통 가능한 모든 길이를 확인해야 하는데, 이는 마치 건초더미에서 바늘을 찾기 위해 매번 모든 짚 하나하나를 하나씩 일일이 확인하는 것과 같습니다.

여기에, 초스마트한 '원패스(one-pass)' 탐정처럼 행동하는 새로운 방법인 Panache가 등장합니다. 테이프를 멈추고 되감아서 다양한 길이를 확인하는 대신, Panache는 녹음 파일을 단 한 번만 듣습니다. 소리가 흘러 들어옴에 따라, 이 알고리즘은 모든 가능한 길이에 대해 동시에 즉각적으로 반복되는 패턴을 파악합니다. 이는 소리를 단순히 부피(volume)가 아닌 파형의 형태에 기반한 고유한 서명인 "스펙트럼 지문(spectral fingerprint)"으로 변환함으로써 가능해집니다. 만약 두 소리의 모양이 비슷하다면 지문이 일치하게 되고, Panache는 이를 더 조사해야 함을 인지합니다. 일치하지 않는다면 즉시 무시합니다. 그 결과, Panache는 기존의 느린 방식과 동일한 패턴을 찾아내면서도 훨씬 적은 시간 안에 이를 수행합니다. 테스트 결과, 다른 방법들이 거대한 데이터셋을 분석하는 데 몇 시간이 걸린 반면, Panache는 단 몇 분 만에 작업을 마쳤으며, 이는 반복적인 작업 없이도 정답을 얻을 수 있음을 입증했습니다.

문제점: "골디락스" 윈도우

시계열 데이터의 세계에서 "모티프"란 반복되는 패턴을 의미합니다. 하지만 패턴은 단순한 모양이 아니라, 모양에 '지속 시간'이 더해진 것입니다. 비디오에서 특정 댄스 동작을 찾는다고 상상해 보십시오. 만약 너무 짧은 창(window)으로 본다면, 발을 까닥이는 동작만 보게 됩니다. 만약 너무 긴 창으로 본다면, 발 까닥임과 다음 동작, 그리고 무용수의 의상까지 섞여 보이게 됩니다. 당신에게는 전체 동작을 명확하게 볼 수 있는 딱 적당한 길이인 "골디락스" 윈도우가 필요합니다.

문제는 탐색적 데이터 분석(exploratory data analysis)에서 우리는 종-종 그 "딱 적당한" 길이가 얼마인지 모른다는 것입니다. 우리는 10포인트에서 1,000포인트까지의 길이를 확인해야 할 수도 있습니다. 이 기존의 방식인 **Pan Matrix Profile (PMP)**는 매우 철저하지만 믿을 수 없을 정도로 느린 사서와 같았습니다. 모든 길이에 대한 최적의 매치를 찾기 위해, 사서는 길이 10에 대한 방대한 검색을 실행한 후, 다시 처음부터 시작하여 길이 11, 길이 12를 위한 검색을 수행해야 했습니다. 만약 확인해야 할 길이가 50개라면, 사서는 책 전체를 50번 읽어야 했던 것입니다. 이것을 "quadratic self-joins"라고 부르는데, 이는 "모든 데이터 조각을 다른 모든 데이터 조각과 반복해서 비교하는 것"을 뜻하는 멋진 표현입니다. 작동은 하지만, 데이터가 커질수록 고통스러울 정도로 느려집니다.

Panache 솔루션: 한 번의 통과(One Pass), 모든 길이

이 논문의 저자인 Tej Sanibh Ranade는 이 "Pan Matrix Profile" 작업을 단 한 번의 패스로 수행하는 최초의 알고리즘인 Panache를 소개했습니다. 테이프를 50번 되감는 대신, Panache는 데이터 스트림을 정확히 한 번만 읽습니다. 새로운 숫자가 도착할 때마다, 알고리즘은 관심 있는 모든 서로 다른 길이에 대한 내부 상태를 동시에 업데이트합니다.

어떻게 이런 마법 같은 일을 해낼 수 있을까요? 이는 수학에 관한 영리한 관찰에 기반합니다. 데이터 덩어리를 가져와서 "정규화(normalize)"하면(즉, 평균을 0으로, 표준 편차를 1로 조정하여 부피를 제거하고 오직 형태에만 집중하게 하면), 놀라운 일이 일어납니다. 데이터의 수학적 "스펙트럼"(푸리에 변환)에서 변하는 부분은 오직 DC 성분(평균)뿐입니다. 나머지 스펙트럼—실제 파형의 형태를 설명하는 부분들—은 평균이 무엇이든 상관없이 정확히 동일하게 유지됩니다.

Panache는 이 사실을 이용하여 **슬라이딩 스펙트럼 상태(sliding spectral state)**를 유지합니다. 데이터 윈도우가 앞으로 한 단계 미끄러질 때, 알고리즘은 전체 형태를 처음부터 다시 계산하지 않습니다. 대신, "슬라이딩 DFT(Discrete Fourier Transform)" 재귀를 사용합니다. 이것은 재료가 담긴 컨베이어 벨트를 생각하면 쉽습니다. 새로운 재료가 들어올 때, 전체 레시피를 버리고 새로 시작하는 것이 아니라, 뒤쪽의 오래된 재료를 빼고 앞쪽의 새 재료를 추가하면서 수학적으로 약간만 조정하는 것입니다. 이를 통해 Panache는 모든 윈도우 길이에 대해 최신의 "지문"을 실시간으로 유지할 수 있습니다.

탐정의 도구 상자: 해싱(Hashing)과 거절(Rejection)

이러한 스펙트럼 지문을 확보한 후, Panache는 어떤 것들이 서로 일치하는지 찾아내야 합니다. 모든 지문 하나하나를 서로 비교할 수는 없는데, 그러면 여전히 너무 느리기 때문입니다. 그래서 Panache는 **지역 민감 해시(Locality-Sensitive Hash, LSH)**를 사용합니다. 유사한 지문들이 자동으로 같은 서랍에 분류되는 거대한 서류함이라고 상상해 보십시오. 만약 두 윈도우가 유사한 형태를 가지고 있다면, 그들의 해시(디지털 서명)는 매우 가까울 것이며 같은 버킷(bucket)에 담기게 됩니다.

하지만 두 대상이 같은 버킷에 있다고 해서 반드시 완벽한 매치라는 뜻은 아닙니다. 버킷 내의 모든 쌍에 대해 비용이 많이 드는 정밀한 계산을 수행하는 것을 피하기 위해, Panache는 **Parseval 하한(lower bound)**을 사용합니다. 이것은 수학적 안전망입니다. 알고리즘은 오직 스펙트럼 지문만을 바탕으로 두 형태 사이의 "최소 가능한 거리"를 계산합니다. 만약 이 최소 거리가 이미 매치라고 보기에는 너무 크다면, Panache는 추가적인 작업 없이 해당 쌍을 바로 버립니다. 이는 마치 클럽의 문지기가 신분증을 검사하는 것과 같습니다. 신분증이 가짜처럼 보이면, 얼굴을 확인하기 위해 입장시키지도 않는 것과 같습니다. 이 단계는 "거의 일치하는" 대다수의 쌍을 거절함으로써 엄청난 시간을 절약해 줍니다.

"앵커(Anchor)" 전략

이러한 기술들을 사용하더라도, 모든 가능한 길이(예: 10에서 1,000까지)를 메모리에 추적하는 것은 무리가 있습니다. 그래서 Panache는 앵커 길이(Anchor Lengths) 전략을 사용합니다. 모든 길이에 대해 활발한 검색을 계속 유지하는 대신, 징검다리처럼 간격을 두고 선택된 몇 개의 길이(앵커)에 대해서만 "활성" 검색을 실행합니다.

논문은 모티프가 "끈적하다(sticky)"고 주장합니다. 만약 어떤 패턴이 길이 20에서 좋은 매치라면, 길이 19나 21에서도 좋은 매치일 가능성이 매우 높습니다. 따라서 Panache는 앵커 길이에서 매치를 찾은 다음, 그 사이의 길이들에 대해 빠른 국소적 체크를 수행합니다. 이는 모든 길이에 대해 무거운 작업을 수행하지 않으면서도, "좋은" 길이들이 서로 군집을 이루고 있기 때문에 정답을 찾아낼 수 있게 해줍니다.

결과: 속도와 정확도

저자들은 심장 박동(ECG), 지진, 주식 시장 데이터 등 17가지의 다양한 실제 데이터 구성에 대해 Panache를 테스트했습니다. 그들은 강력한 GPU(고속 컴퓨팅에 사용되는 그래픽 카드)를 사용하는 최신 방법들을 포함하여 기존의 가장 우수한 방법들과 비교했습니다.

결과는 놀라웠습니다. 500만 개의 데이터 포인트와 51개의 길이를 확인해야 하는 Wafer 데이터셋에 대한 결과는 다음과 같습니다:

• 가장 빠른 기존 CPU 방식은 7.95시간이 걸렸습니다.
• 최고 수준의 GPU 방식(H100 기반 Scamp)은 38.3분이 걸렸습니다.
• Panache는 초기 스캔을 2.9분 만에 완료했으며, 최종적인 정확한 모티프를 추출하는 데 6.0분이 걸렸습니다.

Panache는 그들이 테스트한 모든 CPU 및 GPU 베이스라인보다 빨랐습니다. 더 중요한 것은, 정확도를 희생하지 않았다는 점입니다. Panache는 느린 정밀 방식이 찾아낸 상위 20개 모티프를 100% 복구했습니다. Panache가 보고한 모든 패턴은 추정치가 아니라 유효한 이웃에 대한 정확한 거리값이었습니다.

이것이 왜 중요한가

이 논문은 Panache가 어떻게 정확도를 희생하지 않으면서도 스트리밍 방식의 실시간 환경에서 알려지지 않은 길이의 반복 패턴을 찾는가라는, 데이터 마이닝의 오랜 문제를 해결했음을 결론짓습니다. 반복적인 "되감기 및 검색" 접근 방식을 스펙트럼 지문과 수학적 지름길을 사용하는 단 한 번의 스마트한 패스로 대체함으로써, Panache는 거대한 데이터 스트림을 몇 시간이 아닌 몇 분 만에 분석하는 것을 가능하게 했습니다. 이는 당신이 "케이크를 먹으면서 동시에 먹을 수도 있다(두 마리 토끼를 다 잡을 수 있다)"는 것을 증명합니다. 즉, 기존 방식의 정확하고 엄격한 결과를 얻으면서도 현대적인 스트리밍 알고리즘의 속도를 누릴 수 있다는 것입니다. 유일한 트레이드오프는 메모리입니다. 빠른 조회를 위해 많은 데이터를 RAM에 유지해야 하므로 일부 단순한 방법보다 더 많은 메모리를 요구하지만, Panache가 제공하는 속도를 고려할 때 저자들은 이것이 충분히 가치 있는 대가라고 제안합니다.