Я новичок в структурах данных rtree/btree. Создание дерева — это процесс снизу вверх, но поиск по узлу/диапазону/поиск knn — это процесс сверху вниз. Я использую поиск knn, но хочу сделать некоторые улучшения: мои данные представляют собой траекторию точек, которые пространственно близки друг к другу. Чтобы искать KNN для каждой точки на всей траектории, я хочу сначала искать одну точку, а затем другие точки, я не хочу снова начинать с корня, вместо этого я хочу начать с результатов первого точка, и идут выше к своим родителям. Это позволит мне избежать поиска большого количества ненужных страниц. Проблема здесь в том, как я могу перейти от дочернего элемента к его родителю в структуре rtree/btree? Должен ли я изменить процесс создания дерева и всякий раз, когда происходит разделение, заполнять свойство parent[] дочернего элемента? Есть ли другие более простые способы решения этой проблемы?
Структура данных rtree/btree идет вверх от дочернего к родительскому
Ответы (1)
Вы могли:
- Сохраните указатель на родительский узел в дочернем узле, чтобы знать, как двигаться вверх по структуре узлов. Таким образом, между запросами сохраните некоторый указатель на последний листовой узел, а оттуда, используя указатель на родительский узел, переместитесь вверх, проверьте родительский узел, затем снова переместитесь вверх и т. д., пока не будет выбран узел, в котором должно быть выбрано другое поддерево.
- Храните только указатели на дочерние узлы в каждом узле. Затем между запросами сохраните весь путь узлов, используемый для перехода от корня к листу в последнем запросе. Затем, имея последний путь, вы можете вернуться назад в этой коллекции, что будет представлять собой движение вверх от листа, использованного в последнем запросе, к узлу, где вы должны выбрать другое поддерево.
person
Adam Wulkiewicz
schedule
25.01.2016
