Алгоритм паралельного пошуку для документів, описаних формальною граматикою
In this paper, we developed a concurrent generic heuristic algorithm for parallel parsing and searching in structured text datasets. The main objective of the algorithm was to increase an efficiency of central processing unit dependent operations when parsing large-scale datasets by using a parallel...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Теми: | |
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/139915 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| id |
journaliasakpiua-article-139915 |
|---|---|
| record_format |
ojs |
| institution |
System research and information technologies |
| collection |
OJS |
| language |
English |
| topic |
grammar search parallelism concurrency heuristics грамматика поиск параллелизм параллельность эвристика граматика пошук паралелізм паралельність евристика |
| spellingShingle |
grammar search parallelism concurrency heuristics грамматика поиск параллелизм параллельность эвристика граматика пошук паралелізм паралельність евристика Prodan, Anastasiia O. Алгоритм паралельного пошуку для документів, описаних формальною граматикою |
| topic_facet |
grammar search parallelism concurrency heuristics грамматика поиск параллелизм параллельность эвристика граматика пошук паралелізм паралельність евристика |
| format |
Article |
| author |
Prodan, Anastasiia O. |
| author_facet |
Prodan, Anastasiia O. |
| author_sort |
Prodan, Anastasiia O. |
| title |
Алгоритм паралельного пошуку для документів, описаних формальною граматикою |
| title_short |
Алгоритм паралельного пошуку для документів, описаних формальною граматикою |
| title_full |
Алгоритм паралельного пошуку для документів, описаних формальною граматикою |
| title_fullStr |
Алгоритм паралельного пошуку для документів, описаних формальною граматикою |
| title_full_unstemmed |
Алгоритм паралельного пошуку для документів, описаних формальною граматикою |
| title_sort |
алгоритм паралельного пошуку для документів, описаних формальною граматикою |
| title_alt |
A parallel search algorithm for formal grammar data types Алгоритм параллельного поиска для документов, описанных формальной грамматикой |
| description |
In this paper, we developed a concurrent generic heuristic algorithm for parallel parsing and searching in structured text datasets. The main objective of the algorithm was to increase an efficiency of central processing unit dependent operations when parsing large-scale datasets by using a parallel approach. The developed algorithm uses heuristics to find requested data without needing to process the whole file and without syntax tree building. It can be applied to any data formats. An increase in efficiency was discovered when input-output operations take significantly less time than the process of searching, the file is loaded into random access memory or when an efficient non-sequential access to file is possible. We also developed a prototype implementation of the algorithm for use in performance comparisons. The prototype supports searching in large-scale XML datasets using a subset of XPath expressions to specify search request. Our experimental results show that the developed algorithm is faster than classical algorithms, when all the requirements are met and the desired data is located closer to the beginning of the dataset. In worst cases, our algorithm gives nearly the same results as the others, but consumes more memory. |
| publisher |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| publishDate |
2018 |
| url |
http://journal.iasa.kpi.ua/article/view/139915 |
| work_keys_str_mv |
AT prodananastasiiao aparallelsearchalgorithmforformalgrammardatatypes AT prodananastasiiao algoritmparallelʹnogopoiskadlâdokumentovopisannyhformalʹnojgrammatikoj AT prodananastasiiao algoritmparalelʹnogopošukudlâdokumentívopisanihformalʹnoûgramatikoû AT prodananastasiiao parallelsearchalgorithmforformalgrammardatatypes |
| first_indexed |
2024-04-08T15:06:18Z |
| last_indexed |
2024-04-08T15:06:18Z |
| _version_ |
1795779491529752576 |
| spelling |
journaliasakpiua-article-1399152019-04-26T15:57:21Z A parallel search algorithm for formal grammar data types Алгоритм параллельного поиска для документов, описанных формальной грамматикой Алгоритм паралельного пошуку для документів, описаних формальною граматикою Prodan, Anastasiia O. grammar search parallelism concurrency heuristics грамматика поиск параллелизм параллельность эвристика граматика пошук паралелізм паралельність евристика In this paper, we developed a concurrent generic heuristic algorithm for parallel parsing and searching in structured text datasets. The main objective of the algorithm was to increase an efficiency of central processing unit dependent operations when parsing large-scale datasets by using a parallel approach. The developed algorithm uses heuristics to find requested data without needing to process the whole file and without syntax tree building. It can be applied to any data formats. An increase in efficiency was discovered when input-output operations take significantly less time than the process of searching, the file is loaded into random access memory or when an efficient non-sequential access to file is possible. We also developed a prototype implementation of the algorithm for use in performance comparisons. The prototype supports searching in large-scale XML datasets using a subset of XPath expressions to specify search request. Our experimental results show that the developed algorithm is faster than classical algorithms, when all the requirements are met and the desired data is located closer to the beginning of the dataset. In worst cases, our algorithm gives nearly the same results as the others, but consumes more memory. Разработан параллельный общий эвристический алгоритм для параллельного анализа и поиска в наборах структурированных текстовых данных. Основная цель алгоритма — повышение эффективности зависимых от центрального процессора операций для анализа крупномасштабных наборов данных с использованием параллельного подхода. Разработанный алгоритм использует эвристику для поиска запрашиваемых данных без необходимости обрабатывать весь файл и без создания синтаксиса. Его можно применять к любым форматам данных. Повышение эффективности обнаруживается, когда операции ввода–вывода занимают значительно меньше времени, чем процесс поиска, а файл загружается в оперативное запоминающее устройство, или когда возможен эффективный непоследовательный доступ к файлу. Разработан также прототип реализации алгоритма для использования при сравнении производительности. Прототип поддерживает поиск в крупномасштабных наборах данных XML с использованием подмножества выражений XPath для указания запроса на поиск. Экспериментальные результаты показывают, что разработанный алгоритм быстрее, чем классические при условии выполнения соответственных требований и расположения данных ближе к началу набора. В худшем случае разработанный алгоритм покажет почти такие результаты, что и другие, но требует больше памяти. Розроблено паралельний загальний евристичний алгоритм для паралельного аналізу і пошуку в наборах структурованих текстових даних. Основна мета алгоритму — підвищення ефективності залежних від центрального процесора операцій для аналізу великомасштабних наборів даних з використанням паралельного підходу. Розроблений алгоритм використовує евристику для пошуку даних за запитом без необхідності обробляти весь файл і без створення синтаксису. Його можна застосовувати до будь-яких форматів даних. Підвищення ефективності виявляється, коли операції введення-виведення займають значно менше часу, ніж процес пошуку, а файл завантажується в оперативний запам’ятовувальний пристрій, або коли можливий ефективний непослідовний доступ до файлу. Розроблено також прототип реалізації алгоритму для застосування у разі порівняння продуктивності. Прототип підтримує пошук у великомасштабних наборах даних XML з використанням підмножини виразів XPath для указання запиту на пошук. Експериментальні результати показують, що розроблений алгоритм швидший за класичні за умови виконання відповідних вимог розташування даних ближче до початку набору. У гіршому випадку алгоритм покаже майже такі результати, що й інші, але потребує більше пам'яті. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-12-18 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/139915 10.20535/SRIT.2308-8893.2018.4.05 System research and information technologies; No. 4 (2018); 58-66 Системные исследования и информационные технологии; № 4 (2018); 58-66 Системні дослідження та інформаційні технології; № 4 (2018); 58-66 2308-8893 1681-6048 en http://journal.iasa.kpi.ua/article/view/139915/151392 Copyright (c) 2021 System research and information technologies |