1. About multidimensional queries
1. One-dimensional query
Assuming that table T stores students' test scores, how to query students with scores above 49?
If the traversal method is used, the time complexity is
。
To improve efficiency, a balanced binary tree can be used.
Figure 1 Balanced binary tree
2. Two-dimensional query
- Assume that table T stores students' Chinese and mathematics test scores. What if we query students whose Chinese scores range from 30 to 93 and whose math scores range from 30 to 90?
Figure 2 Table
If you continue to use the balanced binary tree method, you need to first obtain the sets of Chinese scores and mathematics scores respectively, and then calculate the communication between the two sets. The time complexity is
。
In order to improve efficiency, you can follow the following methods to keep the time complexity at
level:
1) Divide everyone's scores into two halves according to their Chinese scores. Half of them have Chinese scores <= c1, and the other half have Chinese scores > c1. Sets S1 and S2 are obtained respectively;
2) For S1, it is divided into two halves according to the math score, half of which has a math score <= m1, and the other half has a math score > m1, and S3 and S4 are obtained respectively;
3) For S2, it is divided into two halves according to the math score, half of which has a math score <= m2, and the other half has a math score > m2, resulting in S5 and S6 respectively;
4) Continue to perform similar divisions on S3, S4, S5, and S6 based on the Chinese scores to get smaller sets, and then continue on the smaller sets based on the math scores.
Figure 3 Division
- Through the above operations, a kd tree is generated:
Figure 4 Generate KD tree
2. About KD tree
1. About KD tree
KD tree (K-dimensional tree, k-dimensional tree) is a high-index tree data structure.
Each node of the KD tree is a binary tree of k-dimensional points.
All non-leaf nodes can be viewed as using a hyperplane to partition the space into two half-spaces.
The left subtree of a node represents the point on the left side of the hyperplane, and the right subtree represents the point on the right side.
Figure 5 KD tree
2. Hyperplane selection method
Each node is related to the k-dimensional dimension perpendicular to the hyperplane.
Therefore, if you choose to divide according to the x-axis, all nodes with x values less than the specified value will appear in the left subtree, and those with x values greater than the specified value will appear in the right subtree.
In this way, the hyperplane can be delineated by x values, and its normal is the unit vector of the x-axis.
Figure 6 Hyperplane
1. Structure
- The loop sequentially takes each dimension of the data point as the segmentation dimension;
| Dimension selection | describe |
|---|---|
| Segmentation dimension selection optimization | - Before starting the construction, compare the distribution of data points in each dimension. The larger the variance of the coordinate value of the data points in a certain dimension, the more dispersed the distribution. The smaller the variance, the more concentrated the distribution. - Starting from the dimension with large variance can achieve good segmentation effect and balance. |
| Median selection optimization (a) | - Before the algorithm starts, the original data points are sorted in all dimensions and stored. - In subsequent median selections, there is no need to sort the subsets every time, which improves performance. |
| Median selection optimization (b) | - Randomly select a fixed number of points from the original data points and then sort them. - Each time, the median value is taken from these sample points as the dividing hyperplane. - This method has been proven in practice to achieve good performance and good balance. |
- Take the median value of the data points in this dimension as the dividing hyperplane;
- Hang the data points to the left of the median value in its left subtree, and hang the data points to the right of the median value in its right subtree;
- Its subtrees are processed recursively until all data points are mounted.
template<class T>
void KDTree<T>::BuildKDTree(vector<vector<T>> points, Node<T>* root)
{ int indexpart = 0, max = 0; vector<T> temp; for (st i = 0; i < _k; i++) { temp.clear(); for each (auto var in points) { temp.push_back(var[i]); } double ave = accumulate(temp.begin(), temp.end(), 0.0) / _point_num; // average double accum = 0.0; for each (auto var in temp) { accum += (var - ave) * (var - ave); //todo:variance } if (accum > max) { max = int(accum); indexpart = int(i); } } //At this time indexpart is the dimension of splitting to be carried out temp.clear(); for each (auto var in points) { temp.push_back(var[indexpart]); } //Find the median; sort(temp.begin(), temp.end()); double median = temp[(temp.size()) >> 1]; //Divide the point into left and right parts vector<vector<T>> leftpoints, rightpoints; for each(auto var in points) { if (var[indexpart] < median) { leftpoints.push_back(var); } if (var[indexpart] == median) { root->m_split = indexpart + 1; root->m_point = var; } if (var[indexpart] > median) { rightpoints.push_back(var); } } //recursion if (leftpoints.size() == 0 && rightpoints.size() == 0) { root->is_leaf = true; } if (leftpoints.size() != 0) { root->lc = new Node<T>(); root->lc->parent = root; BuildKDTree(leftpoints, root->lc); } if (rightpoints.size() != 0) { root->rc = new Node<T>(); root->rc->parent = root; BuildKDTree(rightpoints, root->rc); }
}
2. Range query
- For any rectangular query area R, the query process starts from the root node and is recursive as follows:
1) At any node v, if the subtree v contains only a single node, it means that the matrix region v only covers a single input point. At this time, it can be directly determined whether the point falls within R.
2) Otherwise, it is assumed that the rectangular area v contains multiple input points, which can be divided into three situations:
- a) If the rectangular area v is completely contained in R, then all the input points in it fall within R, and only need to traverse the subtree v to report this part of the input points.
- **b)** If the two intersect, it is necessary to input them into the left and right subtrees of v respectively, and continue the recursive query.
- **c)** If the two are separated from each other, the points in the subset v cannot fall within R, and the recursive branch terminates.
template<class T>
void KDTree<T>::SearchRecu(vector<T> from, vector<T> to, const Node<T>* temp, vector <vector<T>>& nodes)const
{ if (temp == nullptr)return; // If it is an empty tree int partindex = temp->m_split - 1; // current dimension int value = temp->m_point[partindex]; if (from[partindex] <= value && to[partindex] >= value) //The point is within the range { bool in_region = true; for (st i = 0; i < _k; i++) { if (from[i] > temp->m_point[i] || to[i] < temp->m_point[i]) { in_region = false; } } if (in_region) { nodes.push_back(temp->m_point); } SearchRecu(from, to, temp->lc, nodes); SearchRecu(from, to, temp->rc, nodes); } else if (value > to[partindex]) { SearchRecu(from, to, temp->lc, nodes); } else if (value < from[partindex]) { SearchRecu(from, to, temp->rc, nodes); }
}
3. Implement KD tree
1. Node structure
template <class T>
struct Node
{ bool is_leaf; vector<T> m_point; //k-dimensional points int m_split; //Dimensions to be separated Node* parent; Node* lc; Node* rc;
};
2. Tree structure
template<class T>
class KDTree
{
public: KDTree(int k,vector<vector<T>> allpoints); //Constructor ~KDTree() {}; //destructor void Insert(vector<T> newpoint); //Insert node vector<vector<T>> SearchByRegion(vector<T> from, vector<T> to)const; // Find area vector<T> SearchNearestNode(vector<T> goalpoint); //Find the node closest to the target
private: void BuildKDTree(vector<vector<T>> points, Node<T>* root); //create tree void SearchNearestByTree(vector<T> goalpoint, T& curdis, const Node<T>* treeroot, vector<T>& nearestpoint); //Find the point closest to the target point void SearchRecu(vector<T> from, vector<T> to, const Node<T>* temp, vector < vector<T>>& nodes)const; //Find points within the area T CalDistance(vector<T> point1, vector<double> point2); //Calculate distance
private: Node<T>* _root; //Root node int _k; //Dimensions int _point_num; //Number of points vector<vector<T>> points; //Collection of points
};
3. Method implementation
template<class T>
//Constructor
KDTree<T>::KDTree(int k, vector<vector<T>> allpoints) :_k(k)
{ _root = new Node<T>(); _root->is_leaf = false; _root->lc = nullptr; _root->rc = nullptr; _point_num = int(allpoints.size()); points = allpoints; BuildKDTree(allpoints, _root);
} template<class T>
//create tree
void KDTree<T>::BuildKDTree(vector<vector<T>> points, Node<T>* root)
{ int indexpart = 0, max = 0; vector<T> temp; for (st i = 0; i < _k; i++) { temp.clear(); for each (auto var in points) { temp.push_back(var[i]); } double ave = accumulate(temp.begin(), temp.end(), 0.0) / _point_num; // average double accum = 0.0; for each (auto var in temp) { accum += (var - ave) * (var - ave); //todo:variance } if (accum > max) { max = int(accum); indexpart = int(i); } } //At this time indexpart is the dimension of splitting to be carried out temp.clear(); for each (auto var in points) { temp.push_back(var[indexpart]); } //Find the median; sort(temp.begin(), temp.end()); double median = temp[(temp.size()) >> 1]; //Divide the point into left and right parts vector<vector<T>> leftpoints, rightpoints; for each(auto var in points) { if (var[indexpart] < median) { leftpoints.push_back(var); } if (var[indexpart] == median) { root->m_split = indexpart + 1; root->m_point = var; } if (var[indexpart] > median) { rightpoints.push_back(var); } } //recursion if (leftpoints.size() == 0 && rightpoints.size() == 0) { root->is_leaf = true; } if (leftpoints.size() != 0) { root->lc = new Node<T>(); root->lc->parent = root; BuildKDTree(leftpoints, root->lc); } if (rightpoints.size() != 0) { root->rc = new Node<T>(); root->rc->parent = root; BuildKDTree(rightpoints, root->rc); }
} template<class T>
//Find the point closest to the target point
void KDTree<T>::SearchNearestByTree(vector<T> goalpoint, T& curdis, const Node<T>* treeroot, vector<T>& nearestpoint)
{ if (treeroot == nullptr)return; // If it is an empty tree double newdis = CalDistance(goalpoint, treeroot->m_point); // Calculate distance if (newdis < curdis) { curdis = newdis; nearestpoint = treeroot->m_point; } SearchNearestByTree(goalpoint, curdis, treeroot->lc, nearestpoint); SearchNearestByTree(goalpoint, curdis, treeroot->rc, nearestpoint);
} template<class T>
//Find points within the area
void KDTree<T>::SearchRecu(vector<T> from, vector<T> to, const Node<T>* temp, vector <vector<T>>& nodes)const
{ if (temp == nullptr)return; // If it is an empty tree int partindex = temp->m_split - 1; // current dimension int value = temp->m_point[partindex]; if (from[partindex] <= value && to[partindex] >= value) //The point is within the range { bool in_region = true; for (st i = 0; i < _k; i++) { if (from[i] > temp->m_point[i] || to[i] < temp->m_point[i]) { in_region = false; } } if (in_region) { nodes.push_back(temp->m_point); } SearchRecu(from, to, temp->lc, nodes); SearchRecu(from, to, temp->rc, nodes); } else if (value > to[partindex]) { SearchRecu(from, to, temp->lc, nodes); } else if (value < from[partindex]) { SearchRecu(from, to, temp->rc, nodes); }
} template<class T>
//Calculate distance
T KDTree<T>::CalDistance(vector<T> point1, vector<double> point2)
{ if (point1.size() != point2.size()) { cerr << "Two points have different dimensions"; exit(1); } double distance = 0.0; for (st i = 0; i < point1.size(); i++) { distance += pow((point1[i] - point2[i]), 2); } return sqrt(distance);
} template<class T>
//Insert node
void KDTree<T>::Insert(vector<T> newpoint)
{ if (newpoint.size() != _k) { cerr << "The insertion point dimension does not match the KD tree" << endl; } Node<T>* temp = _root; if (temp == nullptr) //If it is an empty tree { temp = new Node<T>(); temp->is_leaf = true; temp->m_split = 1; temp->m_point = newpoint; return; } if (temp->is_leaf) //If the tree has only one node, prepare for insertion { temp->is_leaf = false; int max = 0, partindex = 0; for (st i = 0; i < _k; i++) { double delta = abs(newpoint[i] - temp->m_point[i]); if (delta > max) { max = delta; temp->m_split = i + 1; } } } while (true) { int partindex = temp->m_split - 1; Node<T>* nextnode; if (newpoint[partindex] > temp->m_point[partindex]) { if (temp->rc == nullptr) //Right subtree insertion point { temp->rc = new Node<T>(); temp->rc->parent = temp; temp->rc->is_leaf = true; temp->rc->m_split = 1; temp->rc->m_point = newpoint; break; } else nextnode = temp->rc; } else { if (temp->lc == nullptr) //Insert left subtree { temp->lc = new Node<T>(); temp->lc->parent = temp; temp->lc->is_leaf = true; temp->lc->m_split = 1; temp->lc->m_point = newpoint; break; } else nextnode = temp->lc; } if (nextnode->is_leaf) //If it is a leaf node, prepare for insertion { nextnode->is_leaf = false; int max = 0; partindex = 0; for (st i = 0; i < _k; i++) { double delta = abs(newpoint[i] - nextnode->m_point[i]); if (delta > max) { max = delta; nextnode->m_split = i + 1; } } } temp = nextnode; // Next step }
} template<class T>
// Find area
vector<vector<T>> KDTree<T>::SearchByRegion(vector<T> from, vector<T> to)const
{ vector<vector<T>> result; if (from.size() != _k || to.size() != _k) { cerr << "The search area dimensions do not match the KD tree" << endl; exit(1); } for (st i = 0; i < _k; i++) { if (from[i] > to[i]) { cerr << "The coordinates of the starting point of the region are greater than the end point of the region" << endl; exit(1); } } SearchRecu(from, to, _root, result); return result;
} template<class T>
// Find the node closest to the target
vector<T> KDTree<T>::SearchNearestNode(vector<T> goalpoint)
{ vector<T> nearest_point; Node* temp = _root; while (!temp->is_leaf) //Find the closest leaf node { int partindex = temp->m_split - 1; if (temp->lc != nullptr && goalpoint[partindex] < temp->m_point[partindex]) { temp = temp->lc; } else if (temp->rc) { temp = temp->rc; } } nearest_point = temp->m_point; double curdis = CalDistance(goalpoint, nearest_point); bool is_left = false; while (temp != _root) //backtrace { is_left = (temp == temp->parent->lc); //Determine whether it is a left node temp = temp->parent; //Move the pointer up if (CalDistance(goalpoint, temp->m_point) < curdis) { nearest_point = temp->m_point; curdis = CalDistance(goalpoint, nearest_point); } int partindex = temp->m_split - 1; // Determine whether there is a closer point in the subtree on the other side if (curdis > abs(temp->m_point[partindex] - goalpoint[partindex])) { if (is_left) { SearchNearestByTree(goalpoint, curdis, temp->rc, nearest_point); } else { SearchNearestByTree(goalpoint, curdis, temp->lc, nearest_point); } } } return nearest_point;
}