Задачи интервального поиска

Интервальный поиск имеет очевидное приложение к системам баз данных. В базе данных, содержащей записи о служащих некоторой компании, каждая запись имеет несколько атрибутов, таких, как возраст, жалование и т. д., и может рассматриваться как точка в n-мерном пространстве, в котором каждый атрибут соответствует измерению, а число измерений пространства п равно числу атрибутов. Типичная задача интервального поиска для двух измерений заключается в выявлении всех служащих, чьи возраст и жалованье находятся в заданных интервалах. Это пример взят из [64]. Другой пример можно найти у Д. Кнута [56]. Он рассматривал базу данных городов США с координатами в виде широты и долготы. К такой базе естественен вопрос о перечислении всех городов, попадающих в некоторый прямоугольник-запрос. Это типичная двумерная задача интервального поиска. Подобные задачи возникают также в статистике [181] и автоматизации проектирования [177].

Исследованию задачи интервального поиска (в другом переводе с английского — регионального поиска) посвящено большое количество работ [64, 86, 113, 115, 116, 118−120, 126, 149, 152, 178, 179, 182, 183, 196, 212]. Приведем результаты некоторых из них. Алгоритм решения двумерной задачи интервального поиска путем сведения к решению четырех двумерных задач о доминировании можно найти в [64, 86]. Бентли в [113] предложил метод многомерного двоичного дерева (к-D-дерева), исходя из того, что бинарное дерево для одномерной задачи дает хороший результат. Этот метод имеет линейные затраты по памяти, но Ли и Вонг [178] показали, что в худшем случае этот алгоритм дает плохие результаты, так двумерная задача решается за время Q (/k). Здесь и далее, к равно мощности библиотеки, а оценки приводятся без времени перечисления ответа. В работе [114] Бентли предложил метод прямого доступа, который решает задачу за время 0(log₂A:), но требует затрат по памяти порядка к³ для двумерной задачи. Чтобы уменьшить требуемую память, в работе [116] Бентли и Маурером был предложен многоэтапный метод прямого доступа. Он позволяет снижать порядок требуемой памяти, но при этом возрастает константа при логарифме в оценке времени. С помощью метода дерева интервалов (или дерева регионов) Бентли и Шеймос [118] получили оценку времени поиска 0(log₂ к) при затратах памяти Q (klog₂^_1 А:), где п — размерность задачи интервального поиска. Уиллард [212] и Люкер [182] независимо предложили модификацию дерева интервалов, которая позволила снизить время поиска до.

0(log2^_1 к) при тех же затратах памяти. Чазелле в [126] для двумерной задачи смог снизить затраты памяти до О (к log₂ к/ log₂ log₂ А:), но при этом возросла константа при логарифме в оценке времени. Во всех этих работах оценивается время поиска в худшем случае. И только Болоур описал метод хеширования [120], который он использовал вместо поиска по древовидным структурам в задаче интервального поиска. Применение этого метода позволило получить довольно быстрые в среднем решения задачи интервального поиска при условии, что область запросов находится в заранее определенных границах.