A parallel search algorithm for formal grammar data types

Скорочена інформація про документ
dc.contributor.authorProdan, Anastasiia
dc.date.accessioned2023-12-26T07:32:05Z
dc.date.available2023-12-26T07:32:05Z
dc.date.issued2018
dc.description.abstractIn 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.uk
dc.format.pagerangePp. 58-66uk
dc.identifier.citationProdan, A. A parallel search algorithm for formal grammar data types / Anastasiia Prodan // Системні дослідження та інформаційні технології : міжнародний науково-технічний журнал. – 2018. – № 4. – С. 58-66. – Бібліогр.: 7 назв.uk
dc.identifier.doihttps://doi.org/10.20535/SRIT.2308-8893.2018.4.05
dc.identifier.issn1681–6048
dc.identifier.orcid0000-0002-8829-3308uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/63346
dc.language.isoenuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.relation.ispartofСистемні дослідження та інформаційні технології: міжнародний науково-технічний журнал, № 4uk
dc.subjectgrammaruk
dc.subjectsearchuk
dc.subjectparallelismuk
dc.subjectconcurrencyuk
dc.subjectheuristicsuk
dc.subject.udc004.021uk
dc.titleA parallel search algorithm for formal grammar data typesuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
139915-329121-1-10-20181221.pdf
Розмір:
175.03 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.01 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Системні дослідження та інформаційні технології: міжнародний науково-технічний журнал, № 4