Skip to Main content Skip to Navigation
Journal articles

Composition of weighted finite transducers in MapReduce

Abstract : Abstract Weighted finite-state transducers have been shown to be a general and efficient representation in many applications such as text and speech processing, computational biology, and machine learning. The composition of weighted finite-state transducers constitutes a fundamental and common operation between these applications. The NP-hardness of the composition computation problem presents a challenge that leads us to devise efficient algorithms on a large scale when considering more than two transducers. This paper describes a parallel computation of weighted finite transducers composition in MapReduce framework. To the best of our knowledge, this paper is the first to tackle this task using MapReduce methods. First, we analyze the communication cost of this problem using Afrati et al. model. Then, we propose three MapReduce methods based respectively on input alphabet mapping, state mapping, and hybrid mapping. Finally, intensive experiments on a wide range of weighted finite-state transducers are conducted to compare the proposed methods and show their efficiency for large-scale data.
Document type :
Journal articles
Complete list of metadata
Contributor : Sébastien Verel Connect in order to contact the contributor
Submitted on : Monday, January 3, 2022 - 10:36:32 AM
Last modification on : Monday, May 2, 2022 - 11:36:06 AM

Links full text




Bilal Elghadyry, Faissal Ouardi, Sébastien Verel. Composition of weighted finite transducers in MapReduce. International Journal of Big Data Intelligence, Inderscience Publishers, 2021, 8 (1), ⟨10.1186/s40537-020-00397-4⟩. ⟨hal-03507182⟩



Record views