Efficient Wavelet Tree Construction and Querying for Multicore Architectures

详细信息    查看全文

• 作者：José Fuentes-Sepúlveda (17)
  Erick Elejalde (17)
  Leo Ferres (17)
  Diego Seco (17)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8504
• 期：1
• 页码：150-161
• 参考文献：1. Arroyuelo, D., Costa, V.G., González, S., Marín, M., Oyarzún, M.: Distributed search based on self-indexed compressed text. Inf. Process. Manag.?48(5), 819-27 (2012) CrossRef
  2. Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. J. ACM?46(5), 720-48 (1999) CrossRef
  3. Brisaboa, N.R., Luaces, M.R., Navarro, G., Seco, D.: Space-efficient representations of rectangle datasets supporting orthogonal range querying. Inf. Syst.?38(5), 635-55 (2013) CrossRef
  4. Claude, F., Navarro, G.: Practical rank/select queries over arbitrary sequences. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol.?5280, pp. 176-87. Springer, Heidelberg (2008) CrossRef
  5. Claude, F., Navarro, G.: The wavelet matrix. In: Calderón-Benavides, L., González-Caro, C., Chávez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.?7608, pp. 167-79. Springer, Heidelberg (2012) CrossRef
  6. Claude, F., Nicholson, P.K., Seco, D.: Space efficient wavelet tree construction. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.?7024, pp. 185-96. Springer, Heidelberg (2011) CrossRef
  7. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Multithreaded Algorithms. In: Introduction to Algorithms, 3rd edn., chap. pp. 772-12. The MIT Press (2009)
  8. Faro, S., Külekci, M.O.: Fast multiple string matching using streaming SIMD extensions technology. In: Calderón-Benavides, L., González-Caro, C., Chávez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.?7608, pp. 217-28. Springer, Heidelberg (2012) CrossRef
  9. Ferragina, P., Manzini, G., M?kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms?3(2) (2007)
  10. Gagie, T., Navarro, G., Puglisi, S.J.: New algorithms on wavelet trees and applications to information retrieval. Theoret. Comput. Sci.?427, 25-1 (2012) CrossRef
  11. González, R., Grabowski, S., M?kinen, V., Navarro, G.: Practical implementation of rank and select queries. In: WEA, pp. 27-8. CTI Press, Greece (2005)
  12. Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 841-50. Soc. Ind. Appl. Math, Philadelphia (2003)
  13. Konow, R., Navarro, G.: Dual-sorted inverted lists in practice. In: Calderón-Benavides, L., González-Caro, C., Chávez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.?7608, pp. 295-06. Springer, Heidelberg (2012) CrossRef
  14. Ladra, S., Pedreira, O., Duato, J., Brisaboa, N.R.: Exploiting SIMD Instructions in Current Processors to Improve Classical String Algorithms. In: Morzy, T., H?rder, T., Wrembel, R. (eds.) ADBIS 2012. LNCS, vol.?7503, pp. 254-67. Springer, Heidelberg (2012) CrossRef
  15. M?kinen, V., Navarro, G.: Rank and select revisited and extended. Theoret. Comput. Sci.?387(3), 332-47 (2007) CrossRef
  16. Makris, C.: Wavelet trees: A survey. Comput. Sci. Inf. Syst.?9(2), 585-25 (2012) CrossRef
  17. Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul.?8(1), 3-0 (1998) CrossRef
  18. Navarro, G.: Wavelet trees for all. In: K?rkk?inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.?7354, pp. 2-6. Springer, Heidelberg (2012) CrossRef
  19. Navarro, G., Nekrich, Y., Russo, L.M.S.: Space-efficient data-analysis queries on grids. Theoret. Comput. Sci.?482, 60-2 (2013) CrossRef
  20. Otellini, P.: Keynote Speech at Intel Developer Forum (2003), http://www.intel.com/pressroom/archive/speeches/otellini20030916.htm
  21. Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms?3(4) (2007)
  22. Sutter, H.: The free lunch is over: A fundamental turn toward concurrency in software (2005), http://www.gotw.ca/publications/concurrency-ddj.htm
  23. Tischler, G.: On wavelet tree construction. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.?6661, pp. 208-18. Springer, Heidelberg (2011) CrossRef
  24. V?lim?ki, N., M?kinen, V.: Space-efficient algorithms for document retrieval. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.?4580, pp. 205-15. Springer, Heidelberg (2007) CrossRef
  
• 作者单位：José Fuentes-Sepúlveda (17)
  Erick Elejalde (17)
  Leo Ferres (17)
  Diego Seco (17)
  
  17. Universidad de Concepción, Edmundo Larenas 219, Concepción, Chile
  
• ISSN：1611-3349

文摘

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.