Поиск диапазона - Range searching

Односторонний поиск диапазона.

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

Проблема поиска диапазона и структуры данных которые решают эту проблему, являются фундаментальной темой вычислительная геометрия. Приложения проблемы возникают в таких областях, как географические информационные системы (ГИС) и системы автоматизированного проектирования (CAD) и базы данных.

Вариации

Существует несколько вариантов проблемы, и для разных вариантов могут потребоваться разные структуры данных.^[1] Чтобы получить эффективное решение, необходимо указать несколько аспектов проблемы:

Типы объектов: алгоритмы зависят от того, S состоит из точки, линии, отрезки линии, коробки, полигоны.... Самыми простыми и изученными объектами поиска являются точки.
Типы диапазонов. Диапазоны запросов также необходимо брать из заранее определенного набора. Некоторые хорошо изученные наборы диапазонов, и названия соответствующих задач выровненные по осям прямоугольники (поиск по ортогональному диапазону), симплексы, полупространства, и сферы /круги.
Типы запросов: если необходимо сообщить список всех объектов, которые пересекают диапазон запроса, проблема называется отчет о диапазоне, и запрос называется отчетный запрос. Иногда требуется только количество объектов, пересекающих диапазон. В этом случае проблема называется подсчет дальности, и запрос называется счетный запрос. В запрос пустоты сообщает, есть ли хотя бы один объект, пересекающий диапазон. в полугрупповая версия, а коммутативный полугруппа (S, +), каждой точке присваивается вес из S, и требуется сообщить полугрупповую сумму весов точек, пересекающих диапазон.
Динамический поиск по диапазону и поиск по статическому диапазону: в статической настройке набор S известно заранее. В динамической настройке объекты могут быть вставлены или удалены между запросами.
Автономный поиск по диапазону: заранее известен как набор объектов, так и весь набор запросов.

Структуры данных

Поиск ортогонального диапазона

Запрос двумерного ортогонального диапазона. В этом случае запрос отчета о диапазоне вернет две обведенные точки, запрос подсчета диапазона вернет 2, а запрос о пустоте вернет false.

При поиске по ортогональному диапазону множество S состоит из ${displaystyle n}$ указывает в ${displaystyle d}$ измерения, а запрос состоит из интервалов в каждом из этих измерений. Таким образом, запрос состоит из многомерного выровненный по оси прямоугольник. При размере вывода ${displaystyle k}$ , Джон Бентли использовал k-d дерево для достижения (в Обозначение Big O ) ${displaystyle O (n)}$ пространство и ${displaystyle O {ig (} n ^ {1- {frac {1} {d}}} + k {ig)}}$ время запроса.^[2] Bentley также предложил использовать деревья диапазона, что уменьшило время запроса до ${displaystyle O (log ^ {d} n + k)}$ но увеличил пространство до ${displaystyle O (nlog ^ {d-1} n)}$ .^[3] Дэн Уиллард использованные указатели поворота, частный случай дробное каскадирование чтобы сократить время запроса до ${displaystyle O (log ^ {d-1} n + k)}$ . ^[4]

Хотя указанные выше результаты были достигнуты в указатель машины модели, дальнейшие улучшения были внесены в слово RAM модель вычисления в малых размерах (2D, 3D, 4D). Бернар Шазель использовали деревья диапазона сжатия для достижения ${displaystyle O (log n)}$ время запроса и ${displaystyle O (n)}$ место для подсчета дальности.^[5] Joseph JaJa и другие позже улучшили это время запроса до ${displaystyle Oleft ({dfrac {log n} {log log n}} ight)}$ для подсчета диапазона, который соответствует нижней границе и, следовательно, асимптотически оптимальный.^[6]

По состоянию на 2015 год наилучшие результаты (в малых размерах (2D, 3D, 4D)) для отчетов о диапазоне Тимоти М. Чан, Каспер Ларсен и Михай Пэтрацу, также использующие сжатые деревья диапазонов в модели вычислений Word RAM, являются одним из следующих:^[7]

${displaystyle O (n)}$ Космос, ${displaystyle O (log ^ {epsilon} n + klog ^ {epsilon} n)}$ время запроса
${displaystyle O (nlog log n)}$ Космос, ${displaystyle O (log log n + klog log n)}$ время запроса
${displaystyle O (nlog ^ {epsilon} n)}$ Космос, ${displaystyle O (log log n + k)}$ время запроса

В ортогональном случае, если одна из оценок имеет вид бесконечность, запрос называется трехсторонним. Если две границы равны бесконечности, запрос двусторонний, а если ни одна из границ не бесконечна, то запрос является четырехсторонним.

Поиск динамического диапазона

При поиске в статическом диапазоне набор S известно заранее, динамичный поиск по диапазонам, вставка и удаление точек разрешены. В инкрементной версии задачи разрешены только вставки, тогда как в декрементной версии разрешены только удаления. Для ортогонального случая Курт Мельхорн и Стефан Нэхер создали структуру данных для поиска по динамическому диапазону, которая использует динамическое дробное каскадирование достигать ${displaystyle O (nlog n)}$ пространство и ${displaystyle O (log nlog log n + k)}$ время запроса.^[8] И инкрементная, и декрементная версии проблемы могут быть решены с помощью ${displaystyle O (log n + k)}$ время запроса, но неизвестно, можно ли выполнить поиск в общем динамическом диапазоне за это время запроса.

Цветной поиск диапазона

В задаче подсчета цветных дальностей рассматривается случай, когда точки имеют категоричный атрибуты. Если категории рассматриваются как цвета точек в геометрическом пространстве, тогда запрашивается, сколько цветов появляется в определенном диапазоне. Просенджит Гупта и другие описали структуру данных в 1995 году, которая решала двумерный ортогональный цветной подсчет диапазона в ${displaystyle O (n ^ {2} log ^ {2} n)}$ пространство и ${displaystyle O (журнал ^ {2} n)}$ время запроса.^[9]

Приложения

Помимо рассмотрения в вычислительная геометрия, поиск по дальности и, в частности, поиск по ортогональному диапазону, имеет приложения для диапазон запросов в базы данных. Цветной поиск диапазона также используется и мотивируется поиском по категориальным данным. Например, определение строк в базе данных банковских счетов, которые представляют людей в возрасте от 25 до 40 лет и имеющих от 10 000 до 20000 долларов, может быть проблемой отчетности ортогонального диапазона, когда возраст и деньги являются двумя измерениями.

Смотрите также

дальнейшее чтение

де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк; Шварцкопф, Отфрид (2000), Вычислительная геометрия (2-е изд.), Берлин: Springer-Verlag, ISBN 3-540-65620-0
Матушек, Иржи (1994), «Поиск геометрического диапазона», Опросы ACM Computing, 26 (4): 421–461.

[Agarwal99-1] Агарвал, П. К.; Эриксон, Дж. (1999), "Геометрический поиск и его аналоги" (PDF), в Шазель, Бернар; Гудман, Джейкоб; Поллак, Ричард (ред.), Достижения в дискретной и вычислительной геометрии: материалы совместной летней исследовательской конференции AMS-IMS-SIAM 1996 г., Дискретная и вычислительная геометрия - десять лет спустя, 14-18 июля 1996 г., Колледж Маунт-Холиок, Современная математика, 223, American Mathematical Society Press, стр. 1–56.

[Bentley75-2] Бентли, Джон (1975). «Многомерные бинарные деревья поиска, используемые для ассоциативного поиска». Коммуникации ACM. 18 (9): 509–517. Дои:10.1145/361002.361007.

[Bentley80-3] Бентли, Джон (1980). «Многомерный разделяй и властвуй». Коммуникации ACM. 23 (4): 214–229. Дои:10.1145/358841.358850.

[Willard85-4] Уиллард, Дэн (1985). «Новые структуры данных для запросов ортогонального диапазона». SIAM Журнал по вычислениям. 14 (1): 232–253. Дои:10.1137/0214019.

[Chazelle88-5] Шазель, Бернар (1988). «Функциональный подход к структурам данных и его использование в многомерном поиске». SIAM Журнал по вычислениям. 17 (3): 427–462. Дои:10.1137/0217026.

[JaJa05-6] JaJa, Джозеф; Мортенсен, Кристиан; Ши, Цинминь (2005). «Компактные и быстрые алгоритмы для многомерного отчета и подсчета доминирования». Международный симпозиум по алгоритмам и вычислениям: 558–568.

[Chan11-7] Чан, Тимоти; Ларсен, Каспер; Пэтраску, Михай (2011). "Повторный поиск ортогонального диапазона в ОЗУ". Симпозиум по вычислительной геометрии: 1–10.

[Mehlhorn90-8] Мельхорн, Курт; Нэхер, Стефан (1990). «Динамическое дробное каскадирование». Алгоритмика. 5 (2): 215–241.

[Gupta95-9] Гупта, Просенджит; Джанардан, Рави; Смид, Майкл (1995). «Дальнейшие результаты по обобщенным задачам поиска пересечений: подсчет, отчетность и динамизация». Журнал алгоритмов. 19 (2): 282–317. Дои:10.1006 / jagm.1995.1038.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]