hftrie

Hftrie

Динамическая структура данных для индексации 64-битных двоичных кодов для эффективного поиска ближайшего соседа. Индекс предлагает возможность добавлять, удалять и диапазон поиска для всех точек в данном радиусе целевой точки.

Описание

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

 Блок -схема TD
		  root [r] -> l [0xxx]
		  root [r] -> r [1xxx]
		  L -> ll [00xx]
		  L --- RR [01xx]
		  R -> ll_ [10xx]
		  R -> rr_ [11xx]

Это основная идея, но для эффективности биты объединены вместе. Таким образом, вместо того, чтобы рассмотреть только один бит на уровень, несколько битов (например, 4) используются из битовой последовательности на каждом уровне для сортировки в детские узлы. Это естественным образом увеличивает фанату каждого узла. Для двух битов на слой каждый узел будет сортироваться на четыре возможных дочерних узла. Для 4 бит на слой есть 16 возможных детских узлов. И так далее.

Производительность

Вот показатели производительности для HFTRIE для различных размеров индексов. Время вставки и запроса - это среднее время, которое необходимо для вставки или запроса индекса. Операции запроса предназначены для среднего количества расчетов расстояния, выполняемых для поиска диапазона, нормализованного до размера индекса и выраженного в процентах. Последний столбец предназначен для процента отзыва или средней доли кластера, которая должна быть возвращена с каждым запросом. Поиск быстрого диапазона немного точности для значительного повышения эффективности скорости.

Быстрый поиск в диапазоне

Не	Мем	Вставьте время	Запрос Opers.	Время запроса	Отзывать
100 тыс	4,0 МБ	135 нс	0,97%	37,1 мкс	87,2%
200k	6,5 МБ	146 нс	0,96%	72,9 мкс	89,4%
400K	12 МБ	172 нс	0,89%	124 мкс	88,2%
800K	35 МБ	241 нс	0,43%	206 мкс	86,2%
1 м	45 МБ	263 нс	0,34%	250 мкс	86,0%
2м	75 МБ	297 нс	0,30%	387 мкс	86,2%
4 м	127 МБ	330 нс	0,30%	618 мкс	85,6%
8 м	268 МБ	373 нс	0,25%	953 мкс	85,0%
16M	727 МБ	461 нс	0,11%	1,75 мс	85,2%
32 м	1,2 ГБ	538 нс	0,09%	3,27 мс	86,4%
64 м	1,9 ГБ	613 нс	0,09%	5,21 мс	86,4%
128M	4,3 ГБ	674 нс	0,08%	7,39 мс	92,4%

Для постоянного размера индекса, n = 4M, производительность запроса варьируется для различных значений радиуса. Лучшая точность гарантируется для поиска более низкого радиуса со скромным снижением точности для поиска большего диапазона.

Радиус	Запрос Opers.	Время запроса	Отзывать
0	0,0003%	1,46 мкс	100%
2	0,02%	49,0 мкс	99,8%
4	0,02%	434 мкс	96,6%
6	0,30%	613 мкс	93,4%
8	0,30%	617 мкс	88,6%
10	0,30%	616 мкс	83,2%
12	0,30%	619 мкс	88,8%

Стандартный поиск диапазона

Стандартный диапазон гарантии поиска запроса со значительными дополнительными затратами на скорость.

Не	Мем	Вставьте время	Запрос Opers.	Время запроса	Отзывать
100 тыс	4,0 МБ	134 нс	89,5%	3,40 мс	100%
200k	6,5 МБ	142 нс	89,5%	6,54 мс	100%
400K	12 МБ	169 нс	86,7%	11,7 мс	100%
800K	35 МБ	238 нс	65,7%	30,4 мс	100%
1 м	45 МБ	257 нс	60,7%	39,7 мс	100%
2м	75 МБ	295 нс	58,8%	68,5 мс	100%
4 м	127 МБ	327 нс	58,6%	111 мс	100%
8 м	268 МБ	363 нс	51,2%	191 мс	100%
16M	727 МБ	457 нс	29,0%	454 мс	100%
32 м	1,2 ГБ	533 нс	27,1%	783 мс	100%
64 м	1,9 ГБ	604 нс	27,0%	1,29 с	100%
128M	4,3 ГБ	665 нс	22,8%	1,95 с	100%

Сравнение

Вот сравнение различных методов индексации единого набора распределенных данных в 4 миллиона человек. Операции запросов отмечают количество расстояний, выполняемых на запрос, нормализованный до размера набора данных. Все поисковые запросы образуются для радиуса = 10. Обратите внимание, что все методы снижают простой последовательный поиск при таком большом радиусе. Только быстрый поиск в диапазоне HFTRIE превосходит последовательный поиск с недостатком, что он способен достичь только 85% отзыва всех кластерных объектов для расширенного радиуса. Это, однако, гарантированно вернет все точные совпадения для поиска меньшего диапазона.

Для размера набора данных n = 4m и Query Radius = 10:

Метод	Мем	Вставьте время	Запрос Opers.	Время запроса	Отзывать
SequentialSearch	64 МБ	n/a	100%	9,08 мс	100%
MVPtree	2,67 ГБ	43,9 мкс	25,0%	276 мс	100%
Mtree	113 МБ	631ns	69,5%	68,2 мс	100%
Hwtree	312 МБ	1,69 мкс	17,6%	222 мс	100%
Hftrie-Std	124 МБ	327 нс	58,6%	111 мс	100%
Hftrie-fast	124 МБ	330 нс	0,30%	618 мкс	85,6%

Вы можете запустить эти тесты с помощью скомпилированной программы runhftrie . Просмотреть источник в тестах/run_hftrie.cpp.

Установить

 cmake .
make
make test
make install

Простой API

 HFTrie trie;

long long id;
uint64_t code;

// insert an element
trie.Insert({ id, code });

// delete an element
trie.Delete({ id, code });


uint64_t target;
int radius = 10;
vector<hf_t> results trie.RangeSearch(target, radius);

size_t sz = trie.Size();

size_t nbytes = trie.MemoryUsage();

// for debugging
trie.Print(cout);