Как сделать запрос с многомерным диапазоном с фиксированным диапазоном?

Question

У меня есть около 10^4 точек в 7-мерном пространстве. Для определенного приложения мне нужно сделать ~10^6 запросов диапазона на этом входе, чтобы найти все точки, которые лежат в данном диапазоне. В этом приложении все запросы используют одинаковый размер диапазона. Какая структура данных подходит для этой проблемы?

Кажется, что kd-дерево подходящее, но для 7 измерений и небольшого размера вывода оно почти линейно по временной сложности для запросов. Другое решение - деревья диапазона, но оно кажется слишком сложным для небольшого количества входных данных в этом приложении. Кроме того, я не вижу ни одной из этих структур, использующих тот факт, что диапазон имеет постоянный размер в их пользу. Например, если бы это была одномерная проблема, все запросы запрашивали бы точки, лежащие, например, в диапазоне размера 10, в разных местах вдоль числовой линии.

Answer 1

Ну, это поздний ответ, я не знаю, будет ли он полезным сейчас. Вы можете использовать FQT с фиксированной высотой (FHFQT или FHQT) [ http://users.dcc.uchile.cl/~rbaeza/ftp/fqtrees.ps.gz%5D или массивы с фиксированными запросами (FQA) [ http://www.dcc.uchile.cl/~gnavarro/ps/mtap01.pdf%5D. Эти структуры хорошо работают при поиске подобия. Кроме того, вам нужно использовать хороший метод выбора, например, инкрементальный, чтобы получить хорошие результаты. Я предполагаю, что вы используете евклидово расстояние, а гистограмма расстояний является гауссовым распределением. Извините за мой английский...