MacBook Pro M3 128GB에서 두 시간 안에 원 논문의 전체 실험을 그대로 재현하겠다는 목표는 대개 무리다. 그러나 그 제약은 최근 temporal/dynamic graph 연구의 방향과 잘 맞는다.
첨부 자료가 검토한 2025년 1월–2026년 8월 19일 SIGMOD, PVLDB/VLDB, ICDE, TKDE 문헌에서 반복되는 변화는 global recomputation → affected-region computation, full scan → output-sensitive query, pointer-heavy representation → cache/bit-parallel representation, exact enumeration → bounded approximation이다.
M3 128GB·2시간 조건에서 가장 유망한 축
작은 문제를 고르는 것이 아니라 불필요한 계산을 없애는 것이 contribution인 문제를 고른다.
| 우선순위 | 주제 | 연결 논문 | 적합도 | 예산 |
|---|---|---|---|---|
| S | Historical/interval temporal indexing | Historical k-Core · Interval Index · IIT-Tree | 매우 높음 | 60–110분 |
| S | Partial-order temporal motif estimation | TIMEST · Temporal Triangle · TKDE motif | 매우 높음 | 45–100분 |
| S | Streaming temporal edge/core maintenance | TECM · ((k,p))-core · dynamic bi-core | 매우 높음 | 50–110분 |
| S/A | Workload-adaptive dynamic connectivity | SIGMOD 2025 connectivity comparison | 매우 높음 | 30–70분 |
| A | Bit-parallel exact graph primitives | GraphTwin | 높음 | 40–90분 |
| A | Temporal graph stream sketch | GeminiSketch | 높음 | 40–80분 |
| B | Compact dynamic graph storage | Aster · RadixGraph · Grace | 중간 | 80–120분+ |
논문 가능성, 구현 난이도, 2시간 실험 가능성을 함께 놓으면 1순위는 Temporal Interval/History Index, 2순위는 Partial-Order Temporal Motif Estimation, 3순위는 Adaptive Temporal-Core Maintenance다.
Temporal graph의 기본 정의
edge마다 timestamp 또는 validity interval이 붙고, 질의는 “연결되어 있는가?”를 넘어 “어느 기간에, 얼마 동안, 어떤 순서로, 어떤 구조가 존재했는가?”를 묻는다. Historical k-core는 \([t_s,t_e]\) 구간의 graph에서 k-core를 찾고, core time과 core-time shell로 재계산을 줄인다. TIMEST는 \(M=(H,\pi,\delta)\)로 motif topology, temporal order, 최대 시간폭을 함께 표현한다. Streaming temporal edge-core는 \(\omega\)-incident neighborhood의 support 변화만 추적한다.
여섯 문제와 다섯 원리
문제군
Historical / Interval Query
\(Q(G,[t_s,t_e],\theta)\to R\). 전체 graph보다 결과와 index navigation에 비용이 비례하도록 한다. 이상적 형태는 \(T_Q\approx O(|R|+\log n)\)이다.
Temporal Pattern Counting
\(C(M,G)=|\{\text{occurrences}\}|\). candidate explosion을 online index, sampling tree, weighted estimator로 억제한다.
Dynamic Maintenance
\(S_{t+1}=\operatorname{Update}(S_t,\Delta E_t)\). 한 edge 변화 때문에 전체를 다시 계산하지 않고 affected region만 갱신한다.
Exact Bit-Parallel Query
cheap bit test로 확정 가능한 경우를 먼저 제거하고 불확실한 경우만 exact adjacency fallback으로 보낸다.
Streaming Sketch
전체 state를 유지하지 않고 제한된 memory로 temporal stream의 query/statistics를 답한다.
Compact Dynamic Storage
append/update가 많은 graph에서 snapshot, log, compressed adjacency의 time–space–update trade-off를 최적화한다.
공통 원리
Temporal locality는 변화가 graph 전체에 균일하게 전파되지 않는다는 사실이다. Output sensitivity는 graph 크기보다 answer/affected-region 크기에 비례하는 계산을 지향한다. Shared computation은 여러 motif·interval query의 common intermediate result를 재사용한다. Bit parallelism은 많은 Boolean predicate를 CPU word에 담아 branch와 pointer chase를 줄인다. 마지막은 아래의 삼각관계다.
작은 머신이 아니라 작은 낭비를 겨냥한다
금융거래, communication, social interaction, knowledge evolution, network telemetry에서는 graph가 계속 변하고 “특정 기간” 자체가 query semantics가 된다. SIGMOD 2025에는 temporal triangle, dynamic core, fully-dynamic connectivity, graph-oriented LSM storage가 함께 등장했고 2026년에도 dynamic storage, bit-level exact query, dense-subgraph maintenance가 이어진다.
Historical k-core 연구는 약 120GB RAM CPU server에서 CollegeMsg, Email, MathOverflow, AskUbuntu, SuperUser부터 Flickr/Wikipedia까지 사용했다. M3에서 대형 실험 전체를 복제하는 것과, 중소형 data로 query sweep을 수행하는 것은 다른 문제다. TIMEST는 sampling budget으로 runtime을 직접 조절할 수 있고, dynamic connectivity 연구는 어떤 자료구조도 모든 workload에서 항상 우세하지 않음을 보여 workload-adaptive design의 동기를 만든다.
다섯 병목
- Combinatorial explosion: motif가 커지고 temporal ordering이 붙으면 candidate가 급증한다.
- Update boundary: affected region을 너무 넓게 잡으면 incremental advantage가 사라지고 너무 좁으면 correctness가 깨진다.
- Index duplication: 유사 interval 결과를 따로 materialize하면 storage가 폭발한다.
- Hardware portability: cache 효과를 M3에 그대로 전이하지 말고 bytes touched, random accesses, bit ops, RSS, wall-clock을 함께 측정해야 한다.
- Benchmark budget: 빠른 알고리즘도 parameter matrix가 커지면 2시간을 넘는다.
논문화하기 좋은 여섯 개 RQ
RQ1 · Output-sensitive query
Historical/interval query를 \(|V|+|E|\)가 아니라 result와 changed region에 비례하게 만들 수 있는가?
RQ2 · Constraint expressiveness
Total order를 partial order, duration, existence/durability까지 확장하면서 index와 query 비용을 억제할 수 있는가?
RQ3 · Adaptive locality
모든 vertex에 같은 \(\omega,\delta\), window를 쓰지 않고 density와 event rate에 따라 local temporal radius를 선택할 수 있는가?
RQ4 · Cross-query sharing
서로 다른 interval, motif, continuous query의 common partial computation을 compact representation으로 공유할 수 있는가?
RQ5 · Exact bit-parallelism
GraphTwin식 bit test + exact fallback을 temporal index/core에 적용해 correctness를 유지하면서 pointer-heavy computation을 줄일 수 있는가?
RQ6 · Budget-aware approximation
목표 confidence에 도달하면 sampling을 중단해 fixed sample budget보다 계산량을 줄일 수 있는가?
특히 RQ2+RQ6, RQ1+RQ5, RQ3+RQ5 조합이 강하다.
BOLT, PO-TIMEST, A-TECM 그리고 세 가지 확장
이 Part는 첨부 자료가 최근 논문을 연결해 제안한 후속 연구 설계이며 기존 논문의 직접 결과와 구분한다.
A · BOLT — Bitset-Optimized Local Temporal Index
MCTS의 core-time shell, IIT-Tree/interval decomposition, GraphTwin의 bit-parallel negative filtering을 결합한다. Interval마다 전체 vertex set을 저장하지 않고 temporal equivalence class를 bit-block으로 압축한다. \(Q([t_s,t_e],k)\)가 오면 candidate shell을 찾고 bitwise filtering 후 애매한 후보만 exact validation한다.
M3 실험은 CollegeMsg, Email, MathOverflow, AskUbuntu, SuperUser, interval length 5개, \(k\) 4개, 3회 반복 정도로 설계할 수 있다.
B · PO-TIMEST — Partial-Order Motif Estimation
Total order 대신 DAG precedence constraint를 사용한다. Partial order의 linear extension을 독립적으로 전부 세지 않고 shared temporal spanning tree로 sampling을 공유하며, confidence interval이 목표 수준에 도달하면 sequential stopping으로 종료한다. TIMEST가 partial-order constraint를 future work로 명시했다는 점에서 연구 lineage가 분명하다.
C · A-TECM — Adaptive Temporal Edge-Core Maintenance
지역 event rate와 density에 따라 temporal window를 바꾸되 lower/upper support를 함께 유지해 확실히 unaffected인 edge를 제거하고 boundary만 exact recomputation한다.
D · Workload-Adaptive Dynamic Connectivity
update-heavy region은 cheap-update representation, query-heavy component는 faster-query representation을 쓴다.
E · M3-oriented GraphTwin
64/128/256/512-bit multiword representation에서 filter strength와 bitset traffic의 sweet spot을 찾는다.
F · Expiration-Aware Temporal Sketch
GeminiSketch를 출발점으로 update-rate changepoint에 따라 \(B_1,\ldots,B_m\) bucket 폭을 달리하고 query window boundary bucket만 correction한다.
응용은 넓게, 실험은 좁고 완결되게
Temporal motif는 fraud-ring detection, communication burst, transaction flow, cyber-event correlation과 연결된다. Historical k-core/k-dense query는 “어느 시기에 어떤 집단이 cohesion을 가졌는가”를 묻고 collaboration·market interaction·evolving community에 적용된다. Dynamic connectivity는 dependency graph와 interactive graph DB의 기본 primitive이고, bit-parallel exact query는 adjacency test, set intersection, triangle counting, subgraph filter 같은 낮은 계층에 재사용될 수 있다.
Open problems
Unified time semantics. timestamp order, window, durability, existence interval을 섞은 query를 하나의 index에서 다루면서 explosion을 막아야 한다.
Query/update 공동 최적화.
Adaptive representation. sparse/high-degree, stable/bursty, query-heavy/update-heavy region을 같은 representation으로 처리할 필요가 없다. Partial-order temporal motif는 TIMEST가 명시적으로 남긴 open direction이다.
120분 실험 규약
| 단계 | 시간 | 내용 |
|---|---|---|
| Loading/index | 15분 | 3–5 datasets |
| Baseline 1 | 15분 | same query set |
| Baseline 2 | 15분 | same query set |
| Proposed | 20분 | main experiment |
| Sensitivity | 20분 | 4–5 settings |
| Ablation | 15분 | 2–3 components |
| Repeats/statistics | 10분 | deterministic 3 repeats |
| Slack | 10분 | OS noise/cleanup |
| Total | 120분 | hard wall-clock |
바로 시작한다면 PO-TIMEST, 다음은 BOLT
BOLT
temporal equivalence class를 bit-parallel representation으로 표현할 때 query/update complexity를 이론적으로 정리하는 방향이다.
PO-TIMEST
선행 논문의 explicit future work에 답하고 shared sampling, DAG linear-extension sharing, confidence-bounded stopping을 결합한다. sample budget으로 runtime을 제어할 수 있어 M3·2시간 조건과 가장 잘 맞는다.
A-TECM
local event rate와 topology를 반영하면서 lower/upper support bound로 exact core membership을 보장한다.