Stream Clipper: Scalable Submodular Maximization on Stream
원문 초록
We propose a streaming submodular maximization algorithm "stream clipper" that performs as well as the offline greedy algorithm on document/video summarization in practice. It adds elements from a stream either to a solution set $S$ or to an extra buffer $B$ based on two adaptive thresholds, and improves $S$ by a final greedy step that starts from $S$ adding elements from $B$. During this process, swapping elements out of $S$ can occur if doing so yields improvements. The thresholds adapt based on if current memory utilization exceeds a budget, e.g., it increases the lower threshold, and removes from the buffer $B$ elements below the new lower threshold. We show that, while our approximation factor in the worst case is $1/2$ (like in previous work, and corresponding to the tight bound), we show that there are data-dependent conditions where our bound falls within the range $[1/2, 1-1/e]$. In news and video summarization experiments, the algorithm consistently outperforms other streaming methods, and, while using significantly less computation and memory, performs similarly to the offline greedy algorithm.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
SD-VSum: A Method and Dataset for Script-Driven Video Summarization
An Egocentric Vision-Language Model based Portable Real-time Smart Assistant
What Is That Talk About? A Video-to-Text Summarization Dataset for Scientific Presentations
Do Language Models Understand Time?
Video Repurposing from User Generated Content: A Large-scale Dataset and Benchmark
Does SpatioTemporal information benefit Two video summarization benchmarks?
토론
이 논문과 연결된 포럼 글이 아직 없습니다.