본 문서에서는 ICDE 2026 학회에 발표된 "Fast and Accurate Element-Level Streaming CP Decomposition for Higher-Order Tensors" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: Fast and Accurate Element-Level Streaming CP Decomposition for Higher-Order Tensors
- Authors: Jeongyoung Lee, SeungJoo Lee, and U Kang
- Conference: IEEE International Conference on Data Engineering (ICDE) 2026
Element-Level Streaming Tensor Decomposition
교통량, 전력 사용량, 센서 측정값과 같은 많은 실제 데이터는 시간이 지남에 따라 지속적으로 새로운 값이 추가되는 스트리밍 시계열 데이터의 형태로 관측됩니다. 이러한 데이터에서는 매번 전체 데이터를 처음부터 다시 분석하는 대신, 새로운 데이터가 도착할 때마다 기존 모델을 효율적으로 갱신하는 것이 중요합니다.
텐서 분해(tensor decomposition)는 이러한 다차원 시계열 데이터를 압축적으로 표현하는 대표적인 방법입니다. 이에 따라 기존에도 새로운 데이터가 지속적으로 추가되는 상황에서 CP decomposition 등의 factor를 효율적으로 갱신하는 streaming tensor decomposition 기법들이 활발히 연구되어 왔습니다.
기존의 streaming tensor decomposition에서는 일반적으로 시간이 한 단계 진행될 때마다 텐서의 새로운 slice 전체가 한꺼번에 도착한다고 가정합니다. 예를 들어 (location)×(day) 텐서라면 새로운 하루가 시작될 때 모든 위치의 하루 데이터가 하나의 새로운 column 또는 slice로 주어지는 식입니다.
실제 streaming data에서는 이보다 훨씬 세밀한 단위로 데이터가 들어오는 경우가 많습니다. 하나의 slice가 한 번에 완성되는 것이 아니라, 현재 slice 내부의 일부 element 또는 element group이 시간에 따라 점진적으로 관측될 수 있습니다.
그림 1. Conventional streaming과 element-level streaming의 차이
위 그림의 conventional streaming에서는 매 update마다 완전한 slice가 새롭게 추가됩니다. 반면 본 논문에서 다루는 element-level streaming에서는 현재 활성화된 slice가 한 번에 완성되는 것이 아니라, 작은 element 또는 element group 단위로 점진적으로 채워집니다.
이러한 element-level stream은 특히 시계열을 higher-order tensor로 folding할 때 자연스럽게 발생합니다.
예를 들어 여러 위치에서 시간에 따라 측정되는 교통 데이터를 생각해 보겠습니다. 단순한 (location)×(timestamp) 행렬로 표현할 수도 있지만, 시간축을 접어 (location)×(hour)×(day) 형태의 3차원 텐서로 표현하면 하루 안에서 반복되는 패턴을 별도의 축으로 명시적으로 나타낼 수 있습니다. 더 나아가 (location)×(hour)×(day-of-week)×(week)와 같이 표현하면 일간 및 주간 주기성을 동시에 모델링할 수도 있습니다.
그림 2. Time-series folding을 통한 저랭크 구조 표현
원래의 1차원 시간축을 여러 temporal mode로 folding하면 반복되는 시간 패턴들이 서로 정렬되면서 보다 명확한 저랭크 구조를 얻을 수 있습니다. 따라서 CP decomposition과 같은 텐서 분해를 이용하여 긴 시계열을 적은 수의 latent factor로 효율적으로 표현할 수 있습니다.
하지만 이러한 표현에서는 새로운 문제가 발생합니다. (location)×(hour)×(day) 텐서를 예로 들어, 오전 9시의 데이터가 도착했다고 해서 그날의 10시, 11시, 오후 데이터까지 함께 관측되는 것은 아닙니다. 즉 하루 치 데이터를 담는 새로운 slice 전체가 한 번에 추가되는 것이 아니라, 현재 slice 내부가 시간에 따라 점진적으로 채워집니다.
따라서 이러한 higher-order folding을 적용한 시계열 데이터는 기존 streaming tensor decomposition이 가정하는 slice-level arrival보다 element-level streaming으로 보는 것이 더 자연스럽습니다.
이러한 차이는 단순히 데이터가 조금 더 자주 들어온다는 의미가 아닙니다. 기존 streaming decomposition은 한 번 처리한 slice를 다시 방문할 필요가 없다는 가정에 기반합니다. 그러나 element-level streaming에서는 동일한 slice에 새로운 값이 계속 추가되므로 이 가정이 깨집니다.
기존 slice-level 방법을 그대로 적용하면 크게 두 가지 문제가 발생합니다.
첫째, 아직 도착하지 않은 값들을 임의로 imputation하여 완전한 slice를 만든 뒤 업데이트할 수 있습니다. 하지만 실제로 관측되지 않은 값을 목적 함수에 포함하기 때문에 정확도가 떨어질 수 있습니다.
둘째, 새로운 element가 도착할 때마다 현재 slice에서 이전에 관측한 데이터까지 다시 읽고 factor를 갱신할 수 있습니다. 정확도는 유지할 수 있지만, 이미 처리한 데이터를 계속 반복해서 계산해야 하므로 고빈도 stream에서는 매우 비효율적입니다.
따라서 본 논문은 다음과 같은 질문을 다룹니다.
“Element-level streaming 텐서 분해에서, 과거 데이터를 반복해 처리하지 않으면서도 factor를 빠르고 정확하게 갱신할 수 있을까?”
이를 위해 본 논문에서는 ENTP (ElemENT-level Streaming CP Decomposition)를 제안합니다.
Proposed Method
ENTP의 핵심 아이디어는 새롭게 도착한 element를 기존의 불완전한 slice에 단순히 추가하는 대신, 현재까지 관측된 데이터를 구조적인 subtensor들로 나누어 CP decomposition의 목적 함수를 다시 구성하는 것입니다.
이를 통해 이미 처리한 데이터의 영향을 compact한 중간 통계량(intermediate statistics)으로 유지하고, 새로운 데이터가 들어올 때에는 실제로 영향을 받는 부분만 갱신할 수 있습니다.
그림 3. ENTP의 subtensor partition
그림 3과 같이 ENTP는 현재까지 관측된 영역을 크게 세 부분으로 나눕니다.
- Old tensor ($\mathcal{X}_{old}$): 이전 시점에서 이미 완전히 관측된 과거 slice들
- Previous tensor ($\mathcal{X}_{prev}$): 현재 slice에서 이전 update까지 관측된 부분
- Current tensor ($\mathcal{X}_{curr}$): 이번 update에서 새롭게 도착한 element들
이러한 분할은 element-level stream에서 자연스럽게 나타나는 L자-형태의 관측 패턴을 서로 겹치지 않는 regular subtensor로 재구성합니다. 그 결과 전체 관측 영역에 대한 reconstruction objective를 각 subtensor에 대한 목적 함수의 합으로 표현할 수 있습니다.
본 연구의 핵심 아이디어는 다음 세 가지 측면으로 요약할 수 있습니다.
- Element-level observation의 구조적 분할: 불규칙하게 증가하는 현재 observation 영역을 regular subtensor로 분리함으로써 element-level streaming에 적합한 목적 함수를 구성합니다.
- 새로운 관측값에 국한된 효율적인 factor update: 과거 데이터에서 계산된 정보를 supplementary statistics로 유지하고 재사용하여, 새로운 element가 도착할 때 전체 tensor나 현재 slice를 다시 처리하지 않고 필요한 factor만 갱신합니다.
- Sparse stream 및 higher-order tensor에 대한 확장: 지나치게 적은 데이터만 도착한 update를 선택적으로 생략하는 sparsity-aware mechanism을 사용하며, 여러 periodic mode를 갖는 higher-order tensor에서도 동일한 원리를 적용할 수 있도록 일반화합니다.
Structured Subtensor Partition
ENTP에서 가장 중요한 출발점은 관측된 데이터와 관측되지 않은 데이터를 명확하게 분리하는 것입니다.
기존 방법에서 현재 slice 전체를 하나의 tensor block으로 처리하면, 아직 관측되지 않은 부분을 masking하거나 imputation해야 합니다. 반면 ENTP에서는 이미 완전히 관측된 과거 데이터, 현재 slice에서 과거에 관측된 부분, 그리고 방금 도착한 데이터를 각각 별도의 reconstruction term으로 분리합니다.
따라서 최적화 과정에서 아직 도착하지 않은 값은 처음부터 목적 함수에 포함되지 않습니다. 이는 단순한 missing-value 처리와도 차이가 있습니다. 일반적인 tensor completion에서는 하나의 불완전한 slice를 반복적으로 최적화하는 반면, ENTP에서는 시간에 따라 관측 영역 자체가 증가한다는 streaming 구조를 이용하여 목적 함수를 명시적으로 분해합니다.
이 분할이 이후의 효율적인 update rule을 가능하게 하는 핵심입니다.
Localized Factor Updates
새로운 데이터가 들어올 때마다 전체 CP decomposition을 다시 계산하면 정확한 결과를 얻을 수 있지만 streaming 환경에서는 지나치게 비쌉니다. ENTP는 subtensor별로 분리한 목적 함수에서 각 factor에 대한 closed-form update rule을 유도하여 이 문제를 해결합니다.
예를 들어 (location)×(hour)×(day) tensor에서 새로운 시간대의 데이터가 들어왔다고 생각해 보겠습니다. 새 데이터는 현재 day factor와 현재 hour에 대응되는 factor에 직접적으로 영향을 주며, 과거의 모든 hour와 day factor를 다시 계산할 필요는 없습니다.
ENTP는 과거 observation의 영향을 supplementary matrices에 누적합니다. 새로운 데이터가 도착하면 과거 tensor를 다시 읽는 대신, 이전에 저장해 둔 통계량에 새로운 데이터에서 계산한 항만 추가하여 새로운 factor를 얻습니다.
즉, ENTP의 핵심은 단순히 “작은 데이터만 사용한다”는 것이 아니라, 과거 데이터가 optimization에 미치는 영향은 유지하면서, 과거 데이터 자체를 다시 처리하지 않는다는 데 있습니다.
이러한 방식은 계산을 새로운 관측값에 국한시키면서도, 전체 과거 데이터와 일관된 decomposition을 유지할 수 있도록 합니다.
Sparse Updates and Higher-Order Streams
Element-level streaming에서는 하나의 update가 매우 작을 수 있기 때문에 missing value나 극단적으로 sparse한 observation이 들어오는 경우 factor가 불안정하게 변할 수 있습니다. ENTP는 현재 update의 observation density가 지나치게 낮으면 해당 update를 생략하는 sparsity-aware thresholding을 사용합니다.
충분한 observation이 확보된 경우에만 factor를 갱신함으로써 작은 update에 overfitting되는 것을 방지하며, 동시에 불필요한 계산도 줄일 수 있습니다.
또한 ENTP는 3차원 tensor에만 한정되지 않습니다. 시간축에 여러 주기성이 존재한다면
(entity)×(hour)×(day-of-week)×(week)
와 같이 여러 periodic mode를 갖는 higher-order tensor로 확장할 수 있습니다. 각 periodic axis에서도 현재 위치 이전에 관측된 영역과 현재 새롭게 도착한 영역을 동일한 원리에 따라 분리함으로써 element-level update를 수행합니다.
이는 중요한 특징입니다. Higher-order folding은 일간, 주간 등 여러 temporal pattern을 명시적으로 표현하는 데 유용하지만 tensor의 차수가 높아질수록 하나의 새 observation이 전체 tensor에서 차지하는 비율은 더욱 작아집니다. 따라서 conventional slice-level streaming보다 element-level update를 효율적으로 처리하는 것이 더욱 중요해집니다.
이론적으로 ENTP의 한 번의 update에 대한 주요 계산 비용은 update size, tensor mode의 수, target rank에 대해 선형적으로 증가합니다. 따라서 tensor 전체의 크기가 계속 증가하더라도 매번 전체 history를 다시 처리할 필요가 없습니다.
Experiments
본 논문에서는 VicRoads, PEMS, Electricity의 세 가지 실제 multivariate time-series dataset을 사용하여 ENTP를 평가합니다. 각 데이터는 daily periodicity를 표현하는 3차원 tensor와 daily 및 weekly periodicity를 함께 표현하는 4차원 tensor로 구성됩니다.
비교 대상으로는 static CP-ALS와 함께 OnlineCP, SOAP, ROLCP, TeCPSGD, SOFIA 등 기존 streaming CP decomposition 방법을 사용합니다. 실험에서는 running time뿐만 아니라 전체 누적 데이터의 reconstruction accuracy, 새롭게 들어온 데이터에 대한 real-time accuracy, 그리고 다음 update에 대한 예측 성능을 함께 평가합니다.
Running Time
먼저 element-level stream에서 매 update를 처리하는 데 필요한 시간을 비교합니다.
그림 4. ENTP와 기존 방법의 running time 비교
ENTP는 모든 데이터셋에서 가장 빠른 update를 수행하며, 기존 방법 대비 최대 28배의 speed-up을 보입니다.
특히 higher-order setting에서 차이가 더욱 명확해집니다. CP-ALS는 매 update마다 누적된 전체 텐서를 다시 분해하기 때문에 텐서가 커질수록 실행 시간이 지속적으로 증가합니다. 일부 streaming baseline 역시 현재 slice에서 관측된 entry가 증가할수록 처리해야 하는 데이터가 많아집니다.
반면 ENTP는 계산을 새롭게 도착한 observation에 국한하기 때문에 stream이 진행되어도 update 시간이 안정적으로 유지됩니다. 이는 단순한 구현 상의 차이가 아니라, 과거 observation을 다시 계산하지 않도록 목적 함수와 update rule 자체를 설계한 결과입니다.
Reconstruction Accuracy
속도를 높이는 것만으로는 충분하지 않습니다. 빠른 update를 위해 과거 정보를 지나치게 생략한다면 분해 정확도가 크게 떨어질 수 있기 때문입니다.
이를 확인하기 위해 논문에서는 현재까지 누적된 모든 관측값에 대한 reconstruction quality를 overall fitness로 측정합니다.
표 1. 3차원 및 4차원 데이터에서의 overall fitness
전체 텐서를 매 update마다 처음부터 다시 분해하는 static CP-ALS가 예상대로 가장 높은 정확도를 보입니다. 그러나 ENTP는 이전 observation을 다시 읽지 않는 완전한 online setting에서도 이에 매우 가까운 정확도를 유지합니다.
VicRoads와 PEMS에서는 static CP-ALS 대비 99% 이상의 relative fitness를 달성하며, Electricity에서도 3차원과 4차원 setting 모두 90% 이상의 높은 relative fitness를 보입니다. 동시에 비교한 online streaming 방법 중에서는 모든 setting에서 가장 높은 overall fitness를 기록합니다.
이 결과는 ENTP의 localized update가 단순한 근사적 shortcut이 아니라는 점을 보여줍니다. 과거 데이터 자체를 다시 계산하지 않더라도 supplementary statistics를 통해 그 영향을 보존하기 때문에, 빠른 update와 전체 tensor에 대한 일관된 reconstruction을 동시에 달성할 수 있습니다.
논문에서는 새롭게 들어온 observation만을 대상으로 측정하는 real-time fitness도 함께 평가합니다. ENTP는 이 지표에서도 모든 데이터셋에 걸쳐 안정적으로 높은 정확도를 보이며, 특히 4차원 setting에서는 비교한 방법 중 가장 높은 성능을 기록합니다.
Prediction Performance
Streaming tensor decomposition은 단순한 compression뿐 아니라 forecasting과 같은 downstream task에도 활용될 수 있습니다. 이에 본 논문에서는 현재 factor를 이용해 다음 update에서 새롭게 관측될 entry를 예측하는 성능을 평가합니다.
표 2. 다음 update에 대한 predictive fitness 비교
ENTP는 VicRoads, PEMS, Electricity의 세 데이터셋 모두에서 가장 높은 predictive fitness를 달성합니다. 이는 ENTP가 현재까지 관측된 데이터의 reconstruction뿐 아니라, 이후의 temporal evolution에 필요한 latent structure도 안정적으로 학습하고 있음을 보여줍니다.
Higher-order tensor representation의 장점도 확인할 수 있습니다. Electricity 데이터에서는 daily pattern만 사용하는 3차원 tensor보다 daily와 weekly periodicity를 함께 표현하는 4차원 tensor에서 ENTP의 prediction 성능이 크게 향상됩니다. 즉, 데이터에 여러 시간 주기성이 존재한다면 higher-order folding을 통해 이를 명시적으로 표현하는 것이 downstream prediction에도 도움이 될 수 있으며, ENTP는 이러한 higher-order representation을 streaming 환경에서도 효율적으로 유지할 수 있습니다.
Effect of Update Granularity
마지막으로 element-level streaming이라는 문제 설정 자체의 의미를 확인하기 위해, 하나의 update에서 몇 개의 column이 동시에 도착하는지를 변화시키는 실험을 수행합니다.
그림 5. Update granularity에 따른 running time과 real-time fitness
한 번에 하나의 column만 들어오는 fine-grained stream에서 ENTP의 장점이 가장 크게 나타납니다. Update에 포함되는 column의 수가 증가하여 기존의 slice-level streaming에 가까워질수록 OnlineCP와의 차이는 점차 줄어듭니다.
이는 ENTP의 성능 향상이 단순히 특정 implementation이 빠르기 때문에 나타나는 것이 아니라, 기존 방법이 해결하도록 설계되지 않았던 fine-grained element-level streaming 문제를 직접적으로 다루기 때문임을 보여줍니다.
또한 ENTP는 update granularity가 변하더라도 real-time fitness가 비교적 안정적으로 유지됩니다. 따라서 매우 빈번하고 작은 update가 발생하는 실제 streaming 환경에서 특히 큰 장점을 가집니다.
Conclusion
본 문서에서는 ICDE 2026에 발표된 “Fast and Accurate Element-Level Streaming CP Decomposition for Higher-Order Tensors” 논문을 소개하였습니다.
본 논문은 기존 streaming tensor decomposition에서 일반적으로 가정하던 slice-level arrival에서 벗어나, 현재 slice 내부의 일부 observation이 시간에 따라 점진적으로 도착하는 element-level streaming tensor decomposition 문제를 새롭게 정의합니다. 이러한 상황은 multivariate time-series를 여러 periodic mode로 folding하여 고차원 텐서(higher-order tensor)로 표현할 때 자연스럽게 발생합니다.
제안 방법인 ENTP는 현재까지 관측된 영역을 구조적인 subtensor로 분리하고, 이에 맞게 decomposition objective를 재구성합니다. 이를 바탕으로 과거 observation의 영향을 supplementary statistics에 유지하면서 새롭게 도착한 데이터와 관련된 factor만 효율적으로 갱신합니다. 따라서 아직 관측되지 않은 데이터를 과도하게 imputation하거나, 새로운 element가 도착할 때마다 이전 observation을 반복해서 처리할 필요가 없습니다.
또한 ENTP는 여러 periodic mode를 갖는 higher-order tensor로 자연스럽게 확장되며, update size와 target rank 등에 대해 효율적으로 scale합니다. 실제 교통 및 전력 데이터에 대한 실험에서는 기존 streaming decomposition 방법보다 최대 28배 빠른 update를 수행하면서도 static offline decomposition에 가까운 reconstruction accuracy를 유지하였으며, real-time reconstruction과 future prediction에서도 안정적으로 높은 성능을 보였습니다.
결국 ENTP의 핵심 메시지는 streaming tensor에서 데이터가 반드시 slice 단위로 도착할 필요는 없다는 것입니다. 실제 데이터의 arrival granularity에 맞게 tensor decomposition 자체를 다시 설계함으로써, 더 높은 빈도로 들어오는 데이터를 불필요한 재계산 없이 즉시 반영할 수 있습니다. 이러한 특징은 실시간 forecasting, anomaly detection, continuous monitoring과 같이 최신 latent representation이 지속적으로 필요한 응용에서 특히 유용할 것으로 기대됩니다.
본 논문에 대한 자세한 정보는 [링크]에서 확인할 수 있습니다.