Как использовать порядок Мортона (кривая z порядка) при поиске по диапазону?

Как использовать Morton Order в диапазоне поиска? Из вики, в параграфе "Использование с одномерными структурами данных для поиска по диапазону",

это говорит

"Запрашиваемый диапазон (x = 2, ..., 3, y = 2, ..., 6) указан пунктирным прямоугольником. Его наибольшее значение Z (MAX) равно 45. В этом примере значение F = 19 встречается при поиске структуры данных в направлении увеличения значения Z. ......BIGMIN (в нашем примере 36)..... поиск только в промежутке между BIGMIN и MAX...."

Мои вопросы:

1) почему F 19? Почему F не должно быть 16?

2) Как получить БОЛЬШОЙ?

3) Существуют ли какие-либо веб-блоги, демонстрирующие, как выполнять поиск по диапазону?

Источник

2 ответа

Решение

РЕДАКТИРОВАТЬ: блог базы данных AWS теперь содержит подробное введение в эту тему.

Этот пост в блоге хорошо иллюстрирует процесс.

При поиске прямоугольного пространства x=[2,3], y=[2,6]:

  1. Минимальное значение Z (12) определяется путем чередования битов младшего x а также y значения: 2 и 2 соответственно.
  2. Максимальное значение Z (45) определяется путем чередования битов старшего x а также y значения: 3 и 6 соответственно.
  3. Найдя минимальное и максимальное значения Z (12 и 45), теперь у нас есть линейный диапазон, который мы можем перебирать, который гарантированно содержит все записи внутри нашего прямоугольного пространства. Данные в линейном диапазоне будут расширенным набором данных, которые нам действительно нужны: данные в прямоугольном пространстве. Если мы просто проведем итерацию по всему диапазону, мы найдем все данные, которые нас интересуют, а затем и некоторые. Вы можете проверить каждое значение, которое вы посещаете, чтобы увидеть, является ли оно актуальным или нет.

Очевидная оптимизация - попытаться минимизировать количество лишних данных, которые вы должны пройти. Это в значительной степени зависит от количества "швов", которые вы пересекаете в данных - местах, где кривая "Z" должна делать большие скачки, чтобы продолжить свой путь (например, от значения Z от 31 до 32 ниже).

Обход диапазона Z-кривой

Это может быть смягчено путем использования BIGMIN а также LITMAX функции, чтобы идентифицировать эти швы и перейти обратно к прямоугольнику. Чтобы минимизировать количество ненужных данных, которые мы оцениваем, мы можем:

  1. Ведите подсчет количества последовательных фрагментов ненужных данных, которые мы посетили.
  2. Определите максимально допустимое значение (maxConsecutiveJunkData) для этого рассчитывать. Сообщение в блоге, связанное в верхней части, использует 3 за это значение.
  3. Если мы столкнемся maxConsecutiveJunkData кусочки нерелевантных данных подряд мы инициируем BIGMIN а также LITMAX, Важно отметить, что в тот момент, когда мы решили их использовать, мы сейчас находимся где-то в пределах нашего линейного пространства поиска (значения Z от 12 до 45), но за пределами прямоугольного пространства поиска. В статье в Википедии они, похоже, выбрали maxConsecutiveJunkData ценность 4; они начинали с Z=12 и шли до тех пор, пока не достигли 4 значений за пределами прямоугольника (за 15), прежде чем решили, что пришло время использовать BIGMIN, Так как maxConsecutiveJunkData остается на ваш вкус, BIGMIN может использоваться для любого значения в линейном диапазоне (значения Z от 12 до 45). В некоторой степени сбивает с толку, статья только показывает область от 19 до как перекрестно, потому что это поддиапазон поиска, который будет оптимизирован, когда мы используем BIGMIN с maxConsecutiveJunkData из 4

Когда мы понимаем, что мы вышли за пределы прямоугольника слишком далеко, мы можем заключить, что прямоугольник не является смежным. BIGMIN а также LITMAX используются для определения характера раскола. BIGMIN предназначен для того, чтобы при любом значении в пространстве линейного поиска (например, 19) найти следующее наименьшее значение, которое вернется обратно в половину разделенного прямоугольника с большими значениями Z (т. е. прыгнет с 19 до 36). LITMAX аналогично, помогая нам найти наибольшее значение, которое будет внутри половины разделенного прямоугольника с меньшими значениями Z. Реализации BIGMIN а также LITMAX подробно объясняются в zdivide объяснение функции в связанном сообщении в блоге.

Источник

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

С этим ограничением ваша стратегия начинается с полного диапазона, который является индексом мининовой доли (16) и максимальным индексом степени (45). Для оптимизации необходимо найти и устранить большие полосы поддиапазонов, которые находятся за пределами прямоугольника запроса. Заштрихованная область на диаграмме относится к тому, что было бы доступно (последовательно), если бы такая оптимизация (исключая поддиапазоны) не применялась.

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

Источник
Другие вопросы по тегам