Portal de Periódicos da CAPES

Efficient Wavelet Tree Construction and Querying for Multicore Architectures

2014; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-319-07959-2_13

1611-3349

José Fuentes‐Sepúlveda, Erick Elejalde, Leo Ferres, Diego Seco,

Image Retrieval and Classification Techniques

Wavelet trees have become very useful to handle large data sequences efficiently. By the same token, in the last decade, multicore architectures have become ubiquitous, and parallelism in general has become extremely important in order to gain performance. This paper introduces two practical multicore algorithms for wavelet tree construction that run in O(n) time using $\lg \sigma$ processors, where n is the size of the input and σ the alphabet size. Both algorithms have efficient memory consumption. We also present a querying technique based on batch processing that improves on simple domain-decomposition techniques.