Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
') Выбранная так область поиска часто называется ортогональным запросом, возможно, потому, что гиперплоскости, ограничивающие гиперпрямоугольник, ортогональны координатным осям. Иногда гиперпрямоугольник называют прямоугольным (rectilinear); употребляя слово, вероятно, подсказанное формой путей в плоской Li-метрике (см. гл. 8). Однако нам кажется неудачным такое использование термина «прямоугольный> (дискуссия на эту тему будет продолжена в разд. 8.2). (Терминологические вопросы, которые здесь возникли, специфичны для английского языка и не имеют прямых аналогий в русском. — Ред.).
90
Гл. 2. Геометрический поиск
они будут представлены в гл. 5 и 6. Эти рассуждения, строго говоря, приложимы только к такому режиму работы, когда поисковые операции не получают доступа ни к каким другим элементам файла, кроме содержащихся внутри области запроса. Если такое ограничение снять, то сферическую область можно адекватно аппроксимировать семейством гиперпрямоугольных областей; хотя подобный подход может оказаться неудачным при оценке поведения в худшем случае, однако в «реальных», практических ситуациях он может работать весьма хорошо (например, метод fe-D-дерева из разд. 2.3.2).
Общая черта всех методов, которые будут рассмотрены в настоящей главе, состоит в том, что используемые структуры данных будут статическими, т. е. они не будут модифицироваться после их построения. Очевидно, отсюда следует, что все составляющие их элементы — в нашем случае это множество точек в d-мерном пространстве — должны быть заданы заранее. Соответствующие динамические структуры данных, т. е. такие структуры, которые допускают вставку и удаление своих элементов, по-видимому, будут значительно более сложными; их изучение находится до сих пор в весьма активной стадии и не будет детально обсуждаться в данной книге, за исключением нескольких коротких замечаний и библиографических ссылок в разд. 2.4.
Теперь стоит поискать критерий для сравнения разных методов. Естественно в качестве критерия выбрать нижнюю оценку для некоторых мер эффективности этих методов. Однако, перед тем как двинуться дальше, стоит неформально проанализировать взаимосвязь разных способов оценки.
Как обычно, предположим, что файл является фиксированным набором 5 из N записей. Ответом на запрос будет S'-под-множество 5. Один из возможных подходов состоит в предварительном вычислении ответов на все допустимые запросы. Поскольку допустимые ответы составляют конечное множество (как множество всех подмножеств конечного множества S), то бесконечное множество запросов разбивается на конечное число классов эквивалентности (два запроса эквивалентны, если на них поступает одинаковый ответ). Тогда обработка запроса свелась бы к его сравнению со стандартным представителем соответствующего класса эквивалентности, что в свою очередь немедленно дало бы ответ. Этот метод прямого доступа (он будет обсуждаться в разд. 2.3.3) продемонстрировал бы весьма простую обработку запроса, достигнутую за счет огромных затрат памяти и времени предобработки. Однако из двух последних ресурсов память важнее времени предобработки; в самом деле, время предобработки это вполне допустимая однократная затрата, но память является долгосрочной затратой, поскольку непригодна для других целей на протяжении всей жизни запросно-
2.3. Задачи регионального поиска
ответной системы. Поэтому стало традицией, если и не пренебрегать вовсе, то по крайней мере не переоценивать затраты на предобработку, а вместо этого концентрировать внимание на времени обработки запроса и объеме памяти для файла. (Впрочем, во многих приложениях время предобработки и память оцениваются функциями одного порядка, поэтому бывает достаточно оценить лишь последнюю.) Вышеописанный метод характеризуется малым временем запроса и большой памятью; понятно, что уменьшение требований к памяти достигается ценой увеличения времени запроса; итак, мы столкнулись с взаимозависимостью между двумя мерами эффективности. В соответствии с современной практикой будем характеризовать метод регионального поиска парой: (память файла, время запроса).
Понятие «время запроса», в свою очередь, заслуживает некоторого обсуждения. Работа, затрачиваемая на обработку запроса, естественно, зависит не только от размера файла N и от подмножества S'czS, содержащегося внутри запрашиваемого региона, но и от типа запроса (т. е. от природы ранее упомянутой операции «*» на полугруппе). В самом деле, ответом на запрос в режиме подсчета всегда будет единственное целое число (k — мощность 5'), в то время как ответом на запрос в режиме отчета будут имена всех k элементов S'. В принципе можно различать два вида действий при обработке запроса:
1. Поиск, т.е. действия, приводящие к элементам искомого подмножества (обычно последовательность сравнений).
2. Выборка, т. е. действия по составлению ответа на запрос (для запросов в режиме отчета —это фактическое извлечение искомого подмножества).
Анализ запросов в режиме подсчета удобен тем, что всю вычислительную работу вбирает в себя «поиск»; при этом следует ожидать, что время запроса для худшего случая будет функцией f(N, d), зависящей от размера файла и числа измерений. Намного сложнее случай запросов в режиме отчета, поскольку вычислительная работа теперь является комбинацией поиска и выборки, и та ее часть, которая связана с выборкой, ограничена снизу числом k — мощностью Если потребовать, чтобы при обработке запроса обеспечивался доступ только к элементам S', то ясно, что время на поиск этих элементов будет одинаковым для запросов обоих типов. Если же разрешить доступ к супермножеству, немного превосходящему искомое множество S', то появится возможность сократить затраты памяти, а часть стоимости поисковой работы «отнести на счет» задачи выборки; в этом и состоит основная суть метода фильтрующего поиска [Chazelle (1983с)], который будет обсуждаться в конце данной
