# A Method for Synthesizing Ultra-Large-Scale Clock Trees
## 2 IB-KSR Algorithm  
### Imst  
Traditional MST generation methods include algorithms such as Kruskal and Prim. Regardless of the algorithm used, they all need to traverse all nodes and store a significant amount of edge weight information. Taking Kruskal as an example, for node information involving 100,000 nodes, merely using the int type in C for storage would require approximately 20 GB of memory (considering additional data structures and overhead, this estimate can vary, but it illustrates the scale of the requirement). Moreover, the running time of such an approach would be prohibitively long. Thus, we employed the IMST technique, which does not compute and store all edges but only stores the nearby edges with smaller weights. As shown in Figure 1, the specific content is to traverse all nodes, using each node as a starting point for scanning, scan the \(k\) nearest nodes to that point, and generate \(k\) sets of edge information. In essence, this part constitutes a \(k\)-nearest neighbor method. The complete description of the IMST algorithm is presented as Algorithm 1 below:  
For \(n\) nodes, this approach generates a total of \(kn\) sets of edge information, which are added to a set \(E\) to form an incomplete edge set \(E_{k}\). After sorting \(E_{k}\) in ascending order, [PERSON]'s edge addition method is applied to construct an incomplete minimum spanning tree. In the process of finding the nearest neighbor nodes, there are indeed many methods that can achieve logarithmic time complexity \(O(\log n)\) for the search. One such method is the use of R-trees found in C++'s Boost library. However, R-trees are based on Euclidean distance for nearest neighbor search, but in the context of clock tree synthesis, the Manhattan distance better aligns with the actual physical constraints in a circuit layout. Thus, we adopted a quadtree-based nearest neighbor search technique. Quadtrees, as a type of spatial partition data structure, efficiently support \(k\)-nearest neighbor searches  
Figure 1: With \(k=7\), the dashed lines represent the edges that [PERSON]’s algorithm would need to compute, while the red lines depict the \(k\) sets of edges scanned using the \(k\)-nearest neighbors method. Note that the selection of nearest neighbors is based on Manhattan distance rather than the intuitive Euclidean distance. The red circle serves as the reference point for the \(k\)-nearest neighbors search, where the algorithm identifies the \(k\) closest data points to this centroid. The black circle represent candidate points in the search space. based on Manhattan distance by recursively dividing the plane into subregions. When combined with a priority queue algorithm, the search efficiency can be further optimized while ensuring accuracy, resulting in an overall time complexity of \(O(k\log n)\), where \(k\) is the number of nearest neighbors and \(n\) is the number of nodes. ```
Input: A set of points \(P=\{r_{1},r_{2},\ldots,r_{n}\}\), with the location \((x_{r},y_{r_{i}})\) for point \(r_{i}\) Output: A minimum spanning tree (IMST) with edges \(\text{E}_{\text{IMSTE}}\)
1: Create a graph \(G(P,E)\), where \(E=\big{\{}e(r_{i},r_{j})\big{|}i,j\in\{1,2,\ldots,n\}\cap i\
eq j\big{\}}\)
2:For each point \(r_{i}\in P\):
3: Create an empty list neighbors to store the nearest neighbors of \(r_{i}\)
4:For each of the k nearest neighbors \(r_{j}\) of \(r_{j}\):
5: Calculate the Manhattan distance between \(r_{j}\) and \(r_{j}\): \(d(r_{i},r_{j})=\Big{|}x_{r_{i}}-x_{r_{j}}\Big{|}+\Big{|}y_{r_{i}}-y_{r_{j}} \Big{|}\)
6: Add the edge \(e(r_{i},r_{j},d(r_{i},r_{j}))\) to the list neighbors. 7:EndFor
8: Add these k edges to the edge set \(E_{k}\)
9:EndFor
10: Sort all edges in \(E_{k}\) in ascending order by weight.