期刊
PROCEEDINGS OF THE 2022 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA (SIGMOD '22)
卷 -, 期 -, 页码 1136-1145出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3514221.3526170
关键词
Viterbi decoding; space efficiency; divide-and-conquer
This paper presents an algorithm called SIEVE, which is an improvement on the Viterbi algorithm to address the issue of its space complexity growing with the number of observations. SIEVE improves space efficiency by discarding and recomputing parts of the DP solution, without incurring a time complexity overhead.
Can we get speech recognition tools to work on limited-memory devices? The Viterbi algorithm is a classic dynamic programming (DP) solution used to find the most likely sequence of hidden states in a Hidden Markov Model (HMM). While the algorithm finds universal application ranging from communication systems to speech recognition to bioinformatics, its scalability has been scarcely addressed, stranding it to a space complexity that grows with the number of observations. In this paper, we propose SIEVE (pace Efficient Viterbi), a reformulation of the Viterbi algorithm that eliminates its space-complexity dependence on the number of observations to be explained. SIEVE discards and recomputes parts of the DP solution for the sake of space efficiency, in divide-and-conquer fashion, without incurring a time-complexity overhead. Our thorough experimental evaluation shows that SIEVE is highly effective in reducing the memory usage compared to the classic Viterbi algorithm, while avoiding the runtime overhead of a naive space-efficient solution.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据