Построение суффиксного дерева в иерархической памяти: различия между версиями

Суффиксное дерево – популярная структура данных для распознавания образцов в комбинаторике, поскольку ее элегантность позволяет использовать ее в множестве ситуаций – таких как поиск, сжатие и добыча данных, а также биоинформатика [ ]. В таких приложениях огромные современные наборы данных используют многоуровневые структуры памяти, составляющие среду хранения данных современных компьютеров: кэши L1 и L2, внутренняя память, несколько жестких дисков и удаленных устройств, доступных по сети. Преимущество подобной организации памяти заключается в том, что она может обеспечить гарантированное время доступа к самым быстрым уровням (т.к. кэшу) и при этом сохранить низкую стоимость хранения данных в пересчете на одну ячейку памяти на самом дешевом уровне (диске), при условии, что данные должным образом кэшируются и предоставляются запрашивающим их алгоритмам. Проблемы игнорирования, касающиеся стоимости ссылок на память, могут даже привести к отказу от использования больших наборов входных данных. Инженеры-исследователи в настоящее время пытаются улучшить систему ввода/вывода, чтобы снизить влияние подобных проблем, однако хорошо известно [ ], что улучшения, достижимые посредством должной организации данных и должным образом структурированных алгоритмических вычислений, заметно превышают самые значительные технологические достижения.