SIEVE: A Space-Efficient Algorithm for Viterbi Decoding
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
10
Series
SIGMOD 2022 - Proceedings of the 2022 International Conference on Management of Data, pp. 1136-1145, Proceedings of the ACM SIGMOD International Conference on Management of Data
Abstract
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 (Space 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 naïve space-efficient solution.Description
Publisher Copyright: © 2022 ACM.
Other note
Citation
Ciaperoni, M, Gionis, A, Katsamanis, A & Karras, P 2022, SIEVE: A Space-Efficient Algorithm for Viterbi Decoding. in SIGMOD 2022 - Proceedings of the 2022 International Conference on Management of Data. Proceedings of the ACM SIGMOD International Conference on Management of Data, ACM, pp. 1136-1145, ACM SIGMOD International Conference on Management of Data, Virtual, Online, United States, 12/06/2022. https://doi.org/10.1145/3514221.3526170