Równoległa implementacja algorytmu winnowing dla operacji strumieniowej analizy tekstu

• Autorzy: Wielgosz M. , Żurek D. , Pietroń M. , Dąbrowska-Boruch A. , Wiatr K.

Warianty tytułu

EN

Parallel Winnowing Implementation for text stream analysis

• Języki publikacji: PL

Abstrakty

PL

W ramach praca przeprowadzona została analiza możliwości wykorzystania algorytmu winnowing do strumieniowego przetwarzania informacji tekstowej. W szczególności nacisk został położony na operacje generacji odcisku jako jej zredukowanej reprezentacji wiadomości tekstowej. Autorzy przeprowadzili szereg eksperymentów, w celu określenia efektywności działania algorytmu oraz możliwego do uzyskania przyspieszenia obliczeń, z wykorzy-staniem węzła procesorów Intel Xeon E5645 2.40GHz oraz karty GPU Nvidia Tesla m2090.

EN

There are several models available for information retrieval and text analysis but the two are considered to be the dominant ones, namely Boolean and the vector space model (VSM). A model maps the existing words or text into a new representation space. This paper presents a boolean n-gram-based algorithm - winnowing for fast text search and comparison of documents with main focus on its implementation and performance analysis. The algorithm is used to generate fingerprints (i.e. a set of hashes) of the analyzed documents. A dedicated test framework was designed and implemented to handle the task of the algorithm evaluation which utilizes PAN test corpus and programming environment. Several tests were conducted in order to determine the comparison quality of the obfuscated and not obfuscated text for the winnowing algorithm and different window and n-gram size. The tests revealed interesting properties of the algorithms with respect to comparison of documents as well as defied the limits of their applicability. The n-gram-based algorithms due to their simplicity are well suited for hardware implementation. Thus, the authors implemented compu-tationally demanding part of both fingerprint generation both on CPU and GPU. Performance measurements for Intel Xeon E5645, 2.40GHz and Nvidia Tesla m2090 implementation of Ngram-based algorithm show approximately 14x computational speedup.

Słowa kluczowe

PL

n-gramowy model; eksploracja danych; przetwarzanie strumieniowe; GPGPU

EN

n-gram-based model; document comparison; GPU; information retrieval

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 5
• Strony: 309--312
• Opis fizyczny: Bibliogr. 8 poz., tab., wykr.

Twórcy

autor

Wielgosz M.

• Akademia Górniczo-Hutnicza, Al. A. Mickiewicza 30, 30-059 Kraków

autor

Żurek D.

• ACK-CYFRONET AGH, Nawojki 11, 30-950 Kraków

autor

Pietroń M.

• ACK-CYFRONET AGH, Nawojki 11, 30-950 Kraków

autor

Dąbrowska-Boruch A.

• Akademia Górniczo-Hutnicza, Al. A. Mickiewicza 30, 30-059 Kraków

autor

Wiatr K.

• Akademia Górniczo-Hutnicza, Al. A. Mickiewicza 30, 30-059 Kraków

Bibliografia

• [1] IDC Predicts 2012 Will Be the Year of Mobile and Cloud Platform Warsas IT Vendors Vie for Leadership While the Industry RedefinesItself, http://www.businesswire.com/news/home/20111201005201/en/IDCPredicts- 2012-Year-Mobile-Cloud-Platform [access: 16.01.2014].
• [2] Hilbert M.,López, P. :The Worlds Technological Capacity to Store. Science, Vol. 332, no. 6025, s. 60-65, 2011.
• [3] Cisco Visual Networking Index: Forecast and Methodology, 2012 2017. Cisco Systems, White paper. [access: 16.01.2014].
• [4] Amine A, Elberrichi Z., Simonet M., Malki, M.: WordNet-Based and N-Grams-Based Document Clustering. Proceedings of Third International Conference on Broadband Communications, Information Technology and Biomedical Applications, s.394-401, 2008.
• [5] Cavnar W., B. Trenkle J.M.: N-Gram-based text categorization. Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, s. 161-175, 1994.
• [6] Heintze, N.: Scalable Document Fingerprinting. Proceedings usenix workshop on electronic commerce, s. 191-200, 1996.
• [7] Schleimer S., Wilkerson D.S., Aiken A.:Winnowing: local algorithms for document _ngerprinting. Proceeding of SIGMOD '03 Proceedings of the ACM SIG-MOD international conference on Management of data, s. 76-85, 2003.
• [8] Potthast M., Stein B., Eiselt A., Barron-cedeno A., Rosso P.: Overview of the 1st International Competition on Plagiarism Detection. Benno Stein, Paolo Rosso, Efstathios Stamatatos, Moshe Koppel, and Eneko Agirre, editors, SE-PLN 09 Workshop on Uncovering Plagiarism, Authorship, and Social Software Misuse (PAN 09), 2009.