Раніше (1, 2) ми обґрунтували і продемонстрували можливість існування
просторового індексу, що володіє всіма плюсами звичайного B-Tree — індексу та
не поступається по продуктивності індексу на основі R-Tree.
Під катом узагальнення алгоритму на тривимірний простір, оптимізації та бенчмарки.

Читати далі →

Просторовий індекс для PostgreSQL на основі Z-order (vs R-tree), продовження


минулий раз ми прийшли до висновку, що для ефективної роботи просторового індексу на основі Z-order необхідно зробити 2 речі:
  • ефективний алгоритм отримання подинтервалов
  • низькорівневу роботу з B-деревом
Ось саме цим ми і займемося під катом.
Читати далі →

Про Z-оrder і R-дерево

image
Індекс на основі Z-order кривої в порівнянні з R-деревом має масу переваг, він:
  • реалізований як звичайне B-дерево, а ми знаємо що
  • сторінки B-дерева мають кращу заповнюваність, крім того,
  • Z-ключі самі по собі більш компактні
  • B-дерево має природний порядок обходу, на відміну від R-дерева
  • B-дерево швидше будується
  • B-дерево краще збалансовано
  • B-дерево зрозуміліше, не залежить від евристики поділу/злиття сторінок
  • B-дерево не деградує при постійних змінах
  • ...
Втім, у індексів на основі Z-order є і недолік — порівняно низька продуктивність :). Під катом ми спробуємо розібратися з чим пов'язаний цей недолік і чи можна щось з цим зробити.

Читати далі →

Пошук майже-дублікатів і геометрія

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

Формулювання
Є велика база текстів (сотні тисяч текстів). Довжини текстів приблизно однакові, близько 250 символів, мова — англійська. Деякі з текстів відредаговані (виправлені помилки, розставлені коми тощо); таким чином в базі виявляється як оригінальний текст, так і його виправлена копія. Таких пар не дуже багато, скажімо не більше 1%. Завдання: знайти всі такі пари.

Читати далі →