A Multidimensional Binary Search Tree for Star Catalog Correlations

A multi-dimensional binary search tree, k-d tree, is proposed to support range queries in multi-key data sets. The algorithm can been used to solve a near neighbors problem for objects in a 19 million entries star catalog, and can be used to locate radio sources in cluster candidates for the X-ray/SZ Hubble constant measurement technique. Objects are correlated by proximity in a RA-Dec range and by magnitude. Both RA and Dec have errors that must be taken into account. This paper will present the k-d tree design and its application to the star catalog problem.