параметр ДОЛГОТА, но сложно найти город, отвечающий обоим условиям одновременно. Один из подходов к подобным ортогональным запросам диапазонов состоит в разбиении множества всех возможных значений ШИРОТА и ДОЛГОТА таким образом, чтобы на каждый атрибут приходилось небольшое число классов (например, усечением значений до ближайшего меньшего значения, кратного 5°), и построении инвертированного списка по всем комбинированным классам (ШИРОТА, ДОЛГОТА). Это чем-то напоминает карты, состоящие из страниц для каждого локального региона. Используя 5-градусные интервалы, рассматриваемый здесь запрос будет обращаться к восьми страницам, а именно - (20°,70°), (25°,70°), (35°,75°). Запрос диапазона в данном случае должен обработать каждую страницу, либо переходя к более мелким частям страницы, либо обращаясь непосредственно к записям - в зависимости от количества записей, соответствующих этой странице. По сути, получается структура дерева с двумерным ветвлением в каждом внутреннем узле.

Существенное усовершенствование этого подхода, называемое сеточным файлом, было разработано Ю. Нивергельтом (J. Nievergelt), Г. Гинтербергером (И. Hin-terberger) и К. К. Севчик (К. С. Sevcik) [АСМ Trans. Database Systems 9 (1984), 38-71]. Если каждая точка х имеет к координат {xi,...,Xk), они разделяют значения г-й координаты на диапазоны

-00 = дю < 9п < < gin = +00 (1)

и положение х определяется индексами (ji,... ,jk), такими, что

0<ji<ri, 9iji < Xi < gi(j,ji) для1<г<А;. (2)

Совокупности точек, имеющих данное значение [jx,... ,jk), называются ячейками. Записи для точек в одной и той же ячейке хранятся в одном блоке внешней памяти. Блоки могут также содержать точки из нескольких смежных ячеек, обеспечивая тем самым соответствие каждого блока fc-мерному прямоугольному региону, или "суперячейке" Возможно использование различных стратегий для обновления значений границ сетки и для разделения и комбинирования блоков (см., например, К. Hinrichs, BIT 25 (1985), 569-592). Характеристики сеточных файлов со случайными данными проанализированы в работах М. Regnier, BIT 25 (1985), 335-357; P. Flajolet and С. Puech, JACM 33 (1986), 371-407, §4.2.

При простом способе работы с ортогональными запросами диапазонов, предложенном Дж. Л. Бентли (J. L. Bentley) и Р. А. Финкелем (R. А. Finkel), используются структуры, которые назьшаются четревьями* (quadtrees) [Acta Informatica 4 (1974), 1-9]. В двумерном случае каждый узел такого дерева представляет прямоугольник и содержит одну из точек в этом прямоугольнике. Имеется четыре поддерева, соответствующих четырем квадрантам исходного прямоугольника относительно координат данной точки. Аналогично для трех измерений существует восьмипутевое ветвление, и деревья соответственно назьшаются восьмиревьями (octrees). А;-мерные четревья, естественно, порождаются ветвлением по 2* путям.

Математический анализ случайных четревьев является весьма сложным, однако в 1988 году независимо двумя группами исследователей (L. Devroye and L. Laforest,

* Переводя такие термины, поневоле чувствуешь себя Алисой в Зазеркалье, слушающей объяснение Шалтая-Болтая о словах, похожих на бумажник: открываешь его, а там два отделения. Надеюсь, читатель простит не слишком научно звучащие, зато оживляющие сухой текст термины. - Прим. перев.

SICOMP 19 (1990), 821-832; P. Flajolet, G. Gonnet, C. Puech, and J. M. Robson, Algo-rithmica, 10 (1993), 473-500) была определена асимптотическая форма ожидаемого времени вставки ЛГ-го узла в случайное /г-мерное четрево:

\пМ + 0{1). (3)

Обратите внимание, что при к = 1 этот результат согласуется с хорошо известной формулой для вставки в бинарное дерево поиска б.2.2-(5). Дальнейшие разработки Ф. Флажоле (Р. Flajolet), Ж. Лабелля (G. Labelle), Л. Лафоре (L. Laforest) и Б. Салви (В. Salvy) показали, что в действительности средняя внутренняя длина пути может быть выражена в удивительно элегантной форме:

Таким образом, дальнейший анализ случайных четревьев возможен при помощи гипергеометрических функций [см. Random Structures and Algorithms 7 (1995), 117-144].

Бентли (Bentle}) еще больше упростил представления четревьев, введя "A;-d-деревья" (A;-d trees), которые имеют только двойное ветвление в каждом узле [САСМ 18 (1975), 509-517; IEEE Transactions SE-5 (1979), 333-340]. 1-d-дерево представляет собой обычное бинарное дерево поиска, рассмотренное в разделе 6.2.2. 2-d-дерево подобно ему, но при ветвлении на четных уровнях сравниваются координаты х, а на нечетных - у. В общем случае A;-d-дерево имеет узлы с к координатами и ветвление на каждом уровне базируется на сравнении одной из координат. Например, на уровне I происходит ветвление по координате {кmodi) + 1. Для гарантии того, что никакие две записи не будут иметь никаких совпадающих координат, можно использовать правило разрыва узлов (tie-breaking), основываясь на номерах записей или их положении в памяти компьютера. Случайно растущее A;-d-дерево будет иметь то же значение средней длины пути и то же распределение ветвей, что и обычное бинарное дерево поиска, потому что предположения, лежащие в основе их роста, те же, что и в одномерном случае (см. упр. 6.2.2-6).

Если файл "не изменяется динамически, можно сбалансировать любое A;-d-дepeвo с N узлами так, чтобы его высота составляла и IgA, выбрав среднее значение для ветвления в каждом узле. После этого можно быть уверенным в эффективности обработки запросов различных фундаментальных типов. Например, Бентли доказал, что можно найти все записи, имеющие t определенных координат, за 0(N~*) шагов. Кроме того, можно найти все записи, лежащие в заданной прямоугольной области, не более чем за 0(tiV~/* + q) шагов, если всего имеется q таких записей, а t координат лежат в некоторых подобластях [D. Т. Lee and С. К. Wong, Acta Informatica 23 (1977), 23-29]. В действительности, если данная область близка к кубической и q мало и если выбранные для ветвления координаты в каждом узле имеют наибольший разброс значений атрибутов, то, как показано в работе Friedman, Bentley, and Finkel, ACM Trans. Math. Software 3 (1977), 209-226, среднее время обработки запроса к такой области будет составлять всего лишь 0(logiV -f q). Эта же формула применима при поиске в таком A;-d-дepeвe ближайших соседей данной точки в /г-мерном пространстве.

При использовании случайных, а не идеально сбалансированных /г-ё-деревьев среднее время работы для частичных совпадений по t определенным координатам несколько увеличивается до 0(ЛГ~/*+/(*/*). Функция / неявно определяется уравнением

{f{x) + 3-xY{f{x) + 2-xY-= 2 (5)

и весьма мала: имеем

О < }{х) < 0.063293388123738857181401127797 33590 58170-. (6)

При этом максимум достигается при х, близком к 0.585371 [см. Р. Flajolet and С. Puech, JACM 33 (1986), 371-407, §3].

Рост популярности геометрических алгоритмов (и их эстетическая привлекательность) вызвали ускоренное развитие технологий решения многомерных задач и смежных вопросов разных видов. Фактически в 70-х годах появилось новое направление в математике и информатике, именуемое вычислительной геометрией. Отличным справочным пособием, в котором подробно излагается текущее состояние дел в этой отрасли знаний, является Handbook of Discrete and Computational Geometry под редакцией J. E. Goodman and J. ORourke (Boca Raton, Florida: CRC Press, 1997).

Всесторонний обзор структур данных и алгоритмов для важных случаев двух-и трехмерных объектов можно найти в двух взаимодополняющих Самета (Напап Samet) The Design and Analysis of Spatial Data Structures и Applications of Spatial Data Structures (Addison-Wesley, 1990). Самет обратил внимание на то, что исходные четревья Бентли и Финкеля более корректно было бы именовать "точечными четревьями" (point quadtrees). Название четревья теперь стало общим термином для любой иерархической декомпозиции геометрических данных.

Составные атрибуты. Два или более атрибутов могут быть скомбинированы в один суператрибут. Например, атрибут "(КУРС, СПЕЦИАЛИЗАЦИЯ)" может быть создан путем комбинирования полей КУРС и СПЕЦИАЛИЗАЦИЯ в университетском файле регистрации. Таким образом, запрос зачастую можно выполнить, объединяя короткие списки вместо пересечения длинных.

Идея комбинирования атрибутов была развита В. Ю. Лумом (V. Y. Lum) [САСМ 13 (1970), 660-665], который предложил упорядочение инвертированных списков комбинированных атрибутов в лексикографическом порядке слева направо и создание нескольких копий с перестановкой индивидуальных атрибутов надлежащим способом. Например, предположим, что имеется три атрибута - А, В и С. Можно сформировать составные атрибуты

(А, В, С), (В, С, А), (С, А, В) (7)

и построить упорядоченные инвертированные списки для каждого из них. (Так, в первом списке записи упорядочены по их значениям А; записи с одинаковыми значениями А упорядочены по значениям В, а затем - по С.) Такая организация позволяет выполнять запросы, основанные на комбинации этих трех атрибутов; например, все записи, имеющие определенные значения А и С, будут располагаться в третьем списке последовательно.