Parameterized and Promised Streaming: Making Big Data More Accessible
Mohammad Hajiaghayi · 37:12 · Watch on YouTube
이 연구 발표는 엣지가 하나씩 도착하고 메모리가 작은 스트리밍 모델 하에서 작은 해결책 크기 K와 같은 실제 약속에 의존한다면 대규모 그래프를 처리할 수 있다고 주장합니다. 그러한 약속이 있으면 정점 커버와 같은 문제는 약 K² · polylog(n) 공간만 필요하며, 이 경계는 최적입니다. 핵심 트릭은 *스트림 내 커널화*입니다: 정점 커버가 전체 그래프 G의 것과 일치하는 작은 스케...