Существует ли структура данных ближайшего соседа на диске?

У меня есть набор данных, для которого мне нужно найти K ближайших соседей или всех соседей на расстоянии d. В наборе данных определено произвольное расстояние, но это не евклидово расстояние.

Раньше я использовал деревья показателей, в основном дерево обложек. Однако в этом случае мой набор данных будет больше, чем доступная память. Итак, есть ли какая-либо структура данных, которая может использоваться для ближайших соседей в наборе данных, хранящемся на диске? Также будет полезен хороший индекс базы данных для этой операции.


data-structures nearest-neighbor
person Muhammad Alkarouri    schedule 17.11.2010    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

person Gilbert Le Blanc    schedule 17.11.2010
comment
Это было бы неэффективно, потому что дополнительная информация из записи - это вся запись (подумайте о расстояниях между документами или изображениями). Я надеялся минимизировать доступ к диску, и, насколько мне известно, дерево обложек специально не оптимизировано для этого. - person Muhammad Alkarouri; 17.11.2010
comment
Думаю, я не понимаю. Разве документы или изображения нельзя хранить на диске, а индекс содержать рассчитанное расстояние и указатель на место на диске документа или изображения? - person Gilbert Le Blanc; 17.11.2010
comment
Я надеялся на что-то, что минимизирует количество обращений к диску, потому что каждый расчет расстояния требует, по крайней мере, загрузки одного всего документа из базы данных. На практике дерево обложки с вашей подсказкой удовлетворяло моим потребностям. - person Muhammad Alkarouri; 22.11.2010
comment
почему не периодически записывать на диск и извлекать с него часть набора данных? - person iratzhash; 18.10.2015