## 3 Search Process Acceleration
### Search Time Reduced Much Further  
Later in 1997, [PERSON] [17; 18] proposed an even faster database search technique, the \"Search-Less Algorithm,\" (SLA). [PERSON] retained the approach of selecting any pair of stars in the field of view, \(O(b)\)-time, but he proposed using a \"\(k\)-vector\" to search the database in an amount of time independent of the size of the database [19]. Figure 7 shows the \(k\)-vector construction for a 10-element database. The small horizontal lines are equally spaced and they give the \(k\)-vector values: \(0,2,2,3,3,5,6,8,9,10\). The search time for a single star-pair would be \(O(k)\), where \(k\) is the number of possible star pairs with  
Figure 6: Illustration of [PERSON]’s Grid Algorithm (reprinted from [16]). inter-star angles within the measurement tolerance. Unfortunately, the dominant time of the algorithm came when comparing multiple lists of stars returned for each inter-star angle. Since multiple stars had to have all their inter-star angles confirmed to be a match, the running time of the comparison would be \(O(bk^{2})\), and \(b\) is the number of stars in the pattern required to guarantee uniqueness. Even though the resulting value of \(k\) would be a number based on the uncertainty associated with the inter-star angle measurement and the number of observable star pairs, [PERSON] had made the first important step in breaking the dependence of the database search time on the size of the database. [PERSON]'s method could also reject a single non-star from a set of selected stars, without loosing the progress made in identifying the others. The resulting _Search-Less Algorithm_ (SLA) was then successfully tested on orbit on an Indian satellite [20]. A few years later, realizing that the robustness to non-star \"spikes\" was essential towards reducing the number of iterations of his algorithm, [PERSON] developed the \"_Pyramid_\" algorithm [21] which uses an optimal permutation algorithm to exploit the ability of his algorithm to select which stars to match. This permutation is written to minimize the time spent considering stars that don't match, fearing them to be non-star spikes. The code has been tested to reject non-stars in an image containing only five real star but with 63 non-stars thrown in. The Pyramid algorithm has been successfully tested on [PERSON]'s \"Inertial Stellar Compass\" star tracker [22] and on MIT's satellites HETE and HETE-2 [23]. This algorithm is presently under exclusive contract to StarVision Technologies. Neural networks, have been proposed for use in Star ID as early as 1989, [24]. In 2000, [PERSON] [25], proposed using a neural network and fuzzy logic to identify the stars, as illustrated in Figure 8. [PERSON] used the popular ordered triple, based on star brightness, and fed the resulting angular separations into a neural network. While his feature extraction process runs very fast, \(O(1)\), he is forced to use a massively parallel architecture to implement the neural network. Though such techniques may be used with much success on ground-based systems, it is uncertain if this technique is the best for use in a  
Figure 7: Example of \(k\)-vector construction (reprinted from [19]). system with limited electrical power, or that requires expensive radiation-tolerant hardware. [PERSON] notes quite accurately that his algorithm performs much faster than some other of the mentioned algorithms, referencing [PERSON], [PERSON] and [PERSON], but failed to make a comparison with [PERSON]'s method. [PERSON] readily admits that his technique requires more than a quarter-million multiplications. Then in 2007, [PERSON] [26] proposed a feature extraction technique, similar to [PERSON] [11], using the inter-star angles and the angle made by two stars relative to a central star. Though his feature extraction time is \(O(f\lg b)\), he uses a linear database search, performing bit-by-bit comparisons, running in \(O(n)\) time.