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