Индексация на основе кривой Пеано-Гильберта? - PullRequest
Новая
       40

Индексация на основе кривой Пеано-Гильберта?

4 голосов
/ 22 сентября 2010

У меня есть топор, у, z Трехмерные точки, хранящиеся в MySQL, я хотел бы спросить регионы, срезы или точки соседей.Есть ли способ индексировать точки, используя кривые Пеано-Гильберта для ускорения запросов?Или есть более эффективный способ хранения 3D-данных в MySQL?

спасибо Arman.

Ответы [ 2 ]

1 голос
/ 22 сентября 2010

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

XXXXa < the_hash < XXXXz
1 голос
/ 22 сентября 2010

Лично я никогда не заходил так далеко, но я использовал Z-кривую для хранения 2D точек. Это работало довольно хорошо, и не было необходимости пытаться реализовать кривую Гильберта для лучших результатов.

Это должно позволить вам быстро отфильтровать точки, которые, конечно, не находятся рядом. В худшем случае вам все равно нужно отсканировать более 25% таблицы, чтобы найти точки внутри области.

Способ сделать это состоит в том, чтобы разделить x y z в двоичном виде и объединить их в одно значение с помощью кривой. Хотелось бы, чтобы у меня был готов сценарий SQL, но у меня есть только один для 2-й z-кривой, который намного проще сделать.

Редактировать

Извините, вы, возможно, уже знаете все это и действительно просто ищете примеры SQL, но у меня есть некоторые дополнения:

  • Я не уверен, что сканирование в худшем случае на 25% верно и для трехмерных плоскостей. Это может быть выше, не хватит ума, чтобы сказать тебе;).
  • Этот тип кривой поможет вам найти диапазоны, где вам нужно искать. Если у вас есть 2 координаты, вы можете преобразовать их в число кривой Гильберта, чтобы узнать, в каком разделе вашей таблицы вам нужно искать элементы, которые точно соответствуют вашему запросу.
  • Возможно, вы сможете расширить эту концепцию, чтобы найти соседей, но для того, чтобы использовать кривую, вы все еще «застряли», чтобы посмотреть в диапазонах.
...