Análises Experimentais de uma Implementação Eficiente de um Algoritmo Paralelo para a Geração de Arranjos de Sufixos
Resumo
Este artigo apresenta experimentos feitos com uma implementação de um algoritmo paralelo para a geração de Arranjos de Sufixos. O algoritmo analisado é uma variação de um algoritmo baseado no hyperquicksort. Os experimentos mostram que pequenas modificações na idéia originalmente apresentada conduzem a uma versão bastante eficiente que permite, por exemplo, com 24 processadores, a geração de arranjos para textos de 400 MB em menos de dez minutos, ou seja, trinta e seis vezes mais rápido que a versão seqüencial.
Palavras-chave:
Processamento Paralelo, Geração de Índices, Arranjos de Sufixos, Passagem de Mensagens
Referências
T. Anderson. D. Culler, and D. Paterson. A case for NOW (Network of Worstations). IEEE Micro, 15(1):54-64, February 199.5.
M. D. Araúo, G. Navarro, and N, Ziviani. Large text searching allowing errors. In R. Baeza-Yates, editor, Proceedings Fourth South American Workshop on String Processing. Carleton University Press International Informatics Series. Valparaiso. Chile, 1997.
G. H. Gonnet, R. Baeza-Yates, and T. Snider. New indices for text: PAT trees and PAT arrays. In W. B. Frakes and R. Baeza-Yates (Eds.), Information Retrieval: Data Structures and Algorithms, 66-82, Prentice-Hall, Englewoods Cliff, N.J., 1992.
G. Gonnet. PAT 3.1: An Efficient Text Search System - User’s Manual. Centre of the New Oxford English Dictionary, University of Waterloo, Canada, 1987.
D. K. Harman. Overview of the Third Text REtrieval Conference. Proc. Third Text REtrieval Conference (TREC-3), pages 1-19, National Institute of Standards and Technology Special Publication 500-207, Gaithersburg, Maryland, 1995.
J. P. Kitajima, M. D. Resende, B. Ribeiro-Neto, and N. Ziviani. Distributed parallel generation of indices for very large text databases. Proceedings of the 1997 3rd International Conference on Algorithms and Architectures for Parallel Processing - ICA3PP. World Scientific. A. Goscinski and M. Hobbs and W. Zhou. Melbourne, Australia. dec, 1997.
J. P. W. Kitajima, B. A. N. Ribeiro, G. Navarro, and N. Ziviani. Parallel generation of inverted lists on a network of workstations Universidade Federal de Minas Gerais - Departamento de Ciência da Computação. RT 009-97. Belo Horizonte, Brasil. 1997.
A. Macedo et alli. Experimental Analysis of a Parallel Quicksort-Based Algoritm for Suffix Array Generation. 3rd International Meeting on Vector and Parallel Processing, Porto, Portugal, 1998.
U. Manber and G. Myers. Suffix arrays: a new method for on-line string searchs. 1st ACM-SIAM Symposium on Discrete Algorithms, 319-327, San Francisco, 1990.
G. A. Miller, E. B. Newman, and E. A. Friedman. Length-frequency statistics for written English. In Information and Control, 1:370-380, 1958.
IBM. IBM Parallel Environment for AIX: MPI Programming and Subroutine. Version 2, Release 3, Doc Number GC23-3894-02. 1997.
G. Navarro, J. P. W. Kitajima. B. A. N. Ribeiro, and N. Ziviani. Distributed parallel generation of suffix arrays. A. Apostolico and J. Hein, editors, Lecture notes in Computer Science, volume 1264, pages 102-115, Aarthus, Denmark, June 1997. Springer-Verlag. Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM).
M. D. Araúo, G. Navarro, and N, Ziviani. Large text searching allowing errors. In R. Baeza-Yates, editor, Proceedings Fourth South American Workshop on String Processing. Carleton University Press International Informatics Series. Valparaiso. Chile, 1997.
G. H. Gonnet, R. Baeza-Yates, and T. Snider. New indices for text: PAT trees and PAT arrays. In W. B. Frakes and R. Baeza-Yates (Eds.), Information Retrieval: Data Structures and Algorithms, 66-82, Prentice-Hall, Englewoods Cliff, N.J., 1992.
G. Gonnet. PAT 3.1: An Efficient Text Search System - User’s Manual. Centre of the New Oxford English Dictionary, University of Waterloo, Canada, 1987.
D. K. Harman. Overview of the Third Text REtrieval Conference. Proc. Third Text REtrieval Conference (TREC-3), pages 1-19, National Institute of Standards and Technology Special Publication 500-207, Gaithersburg, Maryland, 1995.
J. P. Kitajima, M. D. Resende, B. Ribeiro-Neto, and N. Ziviani. Distributed parallel generation of indices for very large text databases. Proceedings of the 1997 3rd International Conference on Algorithms and Architectures for Parallel Processing - ICA3PP. World Scientific. A. Goscinski and M. Hobbs and W. Zhou. Melbourne, Australia. dec, 1997.
J. P. W. Kitajima, B. A. N. Ribeiro, G. Navarro, and N. Ziviani. Parallel generation of inverted lists on a network of workstations Universidade Federal de Minas Gerais - Departamento de Ciência da Computação. RT 009-97. Belo Horizonte, Brasil. 1997.
A. Macedo et alli. Experimental Analysis of a Parallel Quicksort-Based Algoritm for Suffix Array Generation. 3rd International Meeting on Vector and Parallel Processing, Porto, Portugal, 1998.
U. Manber and G. Myers. Suffix arrays: a new method for on-line string searchs. 1st ACM-SIAM Symposium on Discrete Algorithms, 319-327, San Francisco, 1990.
G. A. Miller, E. B. Newman, and E. A. Friedman. Length-frequency statistics for written English. In Information and Control, 1:370-380, 1958.
IBM. IBM Parallel Environment for AIX: MPI Programming and Subroutine. Version 2, Release 3, Doc Number GC23-3894-02. 1997.
G. Navarro, J. P. W. Kitajima. B. A. N. Ribeiro, and N. Ziviani. Distributed parallel generation of suffix arrays. A. Apostolico and J. Hein, editors, Lecture notes in Computer Science, volume 1264, pages 102-115, Aarthus, Denmark, June 1997. Springer-Verlag. Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM).
Publicado
28/09/1998
Como Citar
CRISTO, M. A. P.; KITAJIMA, J. P..
Análises Experimentais de uma Implementação Eficiente de um Algoritmo Paralelo para a Geração de Arranjos de Sufixos. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 10. , 1998, Búzios/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1998
.
p. 213-217.
DOI: https://doi.org/10.5753/sbac-pad.1998.22690.
