Модель ввода-вывода: различия между версиями

Традиционные графовые алгоритмы обычно используют хорошо организованные механизмы обхода графа, такие как поиск в глубину или в ширину, для получения информации о структуре графа и последующего использования ее для решения текущей задачи. Для модели ввода-вывода не существует эффективного с точки зрения операций ввода-вывода алгоритма поиска в глубину; что до поиска в ширину и нахождения кратчайших путей, то только в последние годы был достигнут некоторый прогресс на неориентированных графах. Для ориентированных графов даже такие простые задачи, как ответ на вопрос, существует ли ориентированный путь между двумя вершинами, остаются открытыми. Таким образом, основными направлениями исследований в этой сфере являются как разработка эффективных с точки зрения операций ввода-вывода алгоритмов обхода графа общего вида, так и продолжение реализации нынешней стратегии по разработке графовых алгоритмов на базе альтернативных подходов, не основанных на обходе графа.

Техники решения геометрических задач, эффективные с точки зрения операций ввода-вывода, разработаны намного лучше, чем для графовых алгоритмов – по крайней мере, для двумерных случаев. Тем не менее, остаются несколько важных фронтов работ. Возможно, наиболее важным из них является разработка эффективных с точки зрения операций ввода-вывода алгоритмов и структур данных для решения геометрических задач большей размерности. Одна из перспективных задач, которые могут исследоваться в этом контексте, касается применения многомерного поиска по диапазону в приложениях для управления базами данных. Не слишком активно велись исследования в области задач о близости, которые сегодня также вышли на передний план. Потребность в подобных структурах имеется в множестве областей применения, в частности, в географических информационных системах; в последнее время много внимания уделялось многофункциональным структурам данных – то есть структурам, способным эффективно отвечать на разные типы запросов. Большинство существующих структур настроены узкофункционально и способны эффективно поддерживать только определенный тип запросов.