Разделительный запрос по геопространственному индексу

Question

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

В этой статье , например, показано, как можно разделить запрос области на несколько запросов, чтобы избежать запроса диапазона с плохой локализацией (см. это изображение). Если вы хотите выполнить поиск по круглой области с помощью одного запроса, используя кривую Z, как обычный геохэш, вам придется запросить весь нижний левый квадрант, который имеет лишь крошечную долю интересующей нас области.

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

Answer 1

Как только вы определили префикс хеша, который покрывает границы вашего запроса, вы можете начать разбивать этот префикс на составные префиксы и проверять, пересекает ли каждый из них ваш запрос, прежде чем сохранять его. Например, скажем, вы определили префикс 0100 как охватывающий вашу область запроса. Префикс 0100 содержит префиксы 01000 и 01001, в то время как префикс 01000 содержит префиксы 010000 и 010001, а префикс 01001 содержит префиксы 010010 и 010011 и т. Д. Пока вы переписываете свой префикс в виде набора более крупных префиксов (соответствующих меньшие области), вы можете отфильтровать те префиксы, которые не пересекают границы вашего запроса. Вам придется остановить процесс разделения в какой-то момент; каждая итерация разделения потенциально удваивает размер вашей коллекции префиксов. Например, вы можете создать максимальный размер коллекции префиксов, после чего вы объявите удовлетворение своей фильтрацией; Конечно, есть и другие метрики, которые вы можете использовать, чтобы найти точку остановки. В качестве последнего шага вы можете повторно объединить «смежные» префиксы, чтобы уменьшить количество выполняемых поисков. Если, например, у вас остались префиксы 01000 и 01001, вы можете объединить их в 0100, чтобы избежать поиска 01000 с последующим поиском 01001 (преимущество в предположении, что у процесса поиска накладные расходы превышают последовательные чтения) , Вам понадобится подпрограмма для вычисления ограничивающей рамки префикса хеша, чтобы проверить пересечение границ вашего запроса. Это будет зависеть от используемой вами схемы хеширования.