Building a guide star catalog which has the characteristics of completeness, simplicity and query rapidity is an important prerequisite and guarantee to realize the SINS/CNS(strapdown inertial navigation system/celestial navigation system). The Tycho-2 catalog in astronomy was selected as the initial catalog of the guide star catalog. The ball rectangle partition method was improved on the basis of the Tycho-2 catalog. It included how to divide the partition and the sub partition. The selection strategy of the alternative guide star was also creatively proposed. The experimental results show that the number of the alternative guide stars using the improved ball rectangle partition method most accounts for 19.37% of the guide stars used for the declination zone method and only accounts for 3.12% of the guide stars used for the traverse method. Therefore, the improved ball rectangle partition method is more accurate and rapid, and is more suitable for the strapdown inertial navigation system/celestial navigation system.