Поиск диапазона

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

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

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

Варианты [ править ]

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

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

Структуры данных [ править ]

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

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

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

В то время как вышеуказанные результаты были достигнуты в модели указательной машины , дальнейшие улучшения были внесены в словесную модель RAM вычислений в малых измерениях (2D, 3D, 4D). Бернар Шазель использовал деревья диапазонов сжатия, чтобы добиться времени и пространства запроса для подсчета диапазонов. ^[5] Джозеф Яджа и другие позже улучшили это время запроса до подсчета диапазонов, которое соответствует нижней границе и, таким образом, является асимптотически оптимальным . ^[6] ${\ Displaystyle О (\ журнал п)}$ ${\ Displaystyle О (п)}$ ${\ displaystyle O \ left ({\ dfrac {\ log n} {\ log \ log n}} \ right)}$

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

${\ Displaystyle О (п)}$ пространство, время запроса ${\ Displaystyle О (\ журнал ^ {\ эпсилон} п + к \ лог ^ {\ эпсилон} п)}$
${\ Displaystyle О (п \ журнал \ журнал п)}$ пространство, время запроса ${\ Displaystyle О (\ журнал \ журнал п + к \ журнал \ журнал п)}$
${\ Displaystyle О (п \ журнал ^ {\ эпсилон} п)}$ пространство, время запроса ${\ Displaystyle О (\ журнал \ журнал п + к)}$

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

Поиск по динамическому диапазону [ править ]

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

Поиск по цветному диапазону [ править ]

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

Приложения [ править ]

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

См. Также [ править ]

Дерево диапазонов
Запрос диапазона

Ссылки [ править ]

^ Agarwal, PK ; Эриксон, Дж. (1999), «Поиск геометрического диапазона и его родственники» (PDF) , в Chazelle, Bernard ; Гудман, Джейкоб ; Ричард Поллак (ред.), Достижения в дискретной и вычислительной геометрии: материалы совместной летней исследовательской конференции AMS-IMS-SIAM 1996 г., Дискретная и вычислительная геометрия - десять лет спустя, 14-18 июля 1996 г., Колледж Маунт-Холиок , Contemporary Mathematics, 223 , American Mathematical Society Press, стр. 1–56.
^ Бентли, Джон (1975). «Многомерные бинарные деревья поиска, используемые для ассоциативного поиска». Коммуникации ACM . 18 (9): 509–517. DOI : 10.1145 / 361002.361007 .
^ Бентли, Джон (1980). «Многомерный разделяй и властвуй». Коммуникации ACM . 23 (4): 214–229. DOI : 10.1145 / 358841.358850 .
^ Уиллард, Дэн (1985). «Новые структуры данных для запросов с ортогональным диапазоном». SIAM Journal on Computing . 14 (1): 232–253. DOI : 10.1137 / 0214019 .
^ Chazelle, Bernard (1988). «Функциональный подход к структурам данных и его использование в многомерном поиске». SIAM Journal on Computing . 17 (3): 427–462. DOI : 10.1137 / 0217026 .
^ JaJa, Джозеф; Мортенсен, Кристиан; Ши, Цинминь (2005). «Компактные и быстрые алгоритмы для многомерного отчета и подсчета доминирования». Международный симпозиум по алгоритмам и вычислениям : 558–568.
^ Чан, Тимоти ; Ларсен, Каспер; Пэтраску, Михай (2011). "Повторный поиск ортогонального диапазона в ОЗУ". Симпозиум по вычислительной геометрии : 1–10.
^ Мельхорн, Курт ; Нахер, Стефан (1990). «Динамическое дробное каскадирование». Алгоритмика . 5 (2): 215–241.
^ Гупта, Просенджит; Джанардан, Рави; Смид, Майкл (1995). «Дальнейшие результаты по обобщенным задачам поиска пересечений: подсчет, отчетность и динамизация». Журнал алгоритмов . 19 (2): 282–317. DOI : 10.1006 / jagm.1995.1038 .

Дальнейшее чтение [ править ]

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

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

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

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

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

[Chazelle88-5] Chazelle, Bernard (1988). «Функциональный подход к структурам данных и его использование в многомерном поиске». SIAM Journal on Computing . 17 (3): 427–462. DOI : 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. DOI : 10.1006 / jagm.1995.1038 .

[1]