Portal de Periódicos da CAPES

Review of the k-Vector and Its Relation to Classical Data Structures

2022; American Institute of Aeronautics and Astronautics; Volume: 45; Issue: 11 Linguagem: Inglês

10.2514/1.g006688

1533-3884

John A. Christian, Joy Arulraj,

Inertial Sensor and Navigation

No AccessEngineering NotesReview of the k-Vector and Its Relation to Classical Data StructuresJohn A. Christian and Joy ArulrajJohn A. Christian https://orcid.org/0000-0002-9522-5784Georgia Institute of Technology, Atlanta, Georgia 30332*Associate Professor, Guggenheim School of Aerospace Engineering. Associate Fellow AIAA.Search for more papers by this author and Joy ArulrajGeorgia Institute of Technology, Atlanta, Georgia 30332†Barry Dickman Assistant Professor, School of Computer Science.Search for more papers by this authorPublished Online:1 Sep 2022https://doi.org/10.2514/1.G006688SectionsRead Now ToolsAdd to favoritesDownload citationTrack citations ShareShare onFacebookTwitterLinked InRedditEmail AboutAbstract References [1] Bentley J. L. and Friedman J. H., “Data Structures for Range Searching,” Computing Surveys, Vol. 11, No. 4, 1979, pp. 397–409. https://doi.org/10.1145/356789.356797 CrossrefGoogle Scholar[2] Saxe J. B., “On the Number of Range Queries in k-Space,” Discrete Applied Mathematics, Vol. 1, No. 3, 1979, pp. 217–225. https://doi.org/10.1016/0166-218X(79)90045-3 Google Scholar[3] Hjaltason G. R. and Samet H., “Index-Driven Similarity Search in Metric Spaces (Survey Article),” ACM Transactions on Database Systems, Vol. 28, No. 4, 2003, pp. 517–580. https://doi.org/10.1145/958942.958948 Google Scholar[4] Mortari D., “A Fast On-Board Autonomous Attitude Determination System Based on a New Star-ID Technique for a Wide FOV Star Tracker,” AAS/AIAA Spaceflight Mechanics Meeting, AAS Paper 96-158, 1996. Google Scholar[5] Mortari D., “Search-Less Algorithm for Star Pattern Recognition,” Journal of the Astronautical Sciences, Vol. 45, No. 2, 1997, pp. 179–194. https://doi.org/10.1007/BF03546375 CrossrefGoogle Scholar[6] Mortari D. and Neta B., “k-Vector Range Searching Techniques,” AAS/AIAA Spaceflight Mechanics Meeting, AAS Paper 00-128, 2000. Google Scholar[7] Mortari D. and Rogers J., “A k-Vector Approach to Sampling, Interpolation, and Approximation,” Journal of the Astronautical Sciences, Vol. 60, 2013, pp. 686–706. https://doi.org/10.1007/s40295-015-0065-x Google Scholar[8] Mortari D., “Memory Adaptive k-Vector,” AAS/AIAA Spaceflight Mechanics Meeting, AAS Paper 14-302, 2014. Google Scholar[9] Arnas D., Leake C. and Mortari D., “The n-Dimensional k-Vector and Its Application to Orthogonal Range Searching,” Applied Mathematics and Computation, Vol. 372, 2020, Paper 125010. https://doi.org/10.1016/j.amc.2019.125010 Google Scholar[10] Mortari D., Samaan M., Bruccoleri C. and Junkins J., “The Pyramid Star Identification Technique,” Navigation: Journal of the Institute of Navigation, Vol. 51, No. 3, 2004, pp. 171–183. https://doi.org/10.1002/j.2161-4296.2004.tb00349.x CrossrefGoogle Scholar[11] Samaan M. A., Mortari D. and Junkins J. L., “Nondimensional Star Identification for Uncalibrated Star Cameras,” Journal of the Astronautical Sciences, Vol. 54, No. 1, 2006, pp. 95–111. https://doi.org/10.1007/BF03256478 CrossrefGoogle Scholar[12] Ying D., Fei X. and Zheng Y., “Brightness Independent 4-Star Matching Algorithm for Lost-in-Space 3-Axis Attitude Acquisition,” Tsinghua Science and Technology, Vol. 11, No. 5, 2006, pp. 543–548. https://doi.org/10.1016/S1007-0214(06)70232-2 Google Scholar[13] Roshanian J., Yazdani S. and Ebrahimi M., “Star Identification Based on Euclidean Distance Transform, Voronoi Tessellation, and k-Nearest Neighbor Classification,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 52, No. 6, 2016, pp. 2940–2949. https://doi.org/10.1109/TAES.2016.150642 CrossrefGoogle Scholar[14] Somayehee F., Nikkhah A. A., Roshanian J. and Salahshoor S., “Blind Star Identification Algorithm,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 56, No. 1, 2020, pp. 547–557. https://doi.org/10.1109/TAES.2019.2917572 Google Scholar[15] Christian J. A. and Crassidis J. L., “Star Identification and Attitude Determination with Projective Cameras,” IEEE Access, Vol. 9, 2021, pp. 25,768–25,794. https://doi.org/10.1109/ACCESS.2021.3054836 Google Scholar[16] Hanak C., Crain T. and Bishop R., “Crater Identification Algorithm for the Lost in Low Lunar Orbit Scenario,” AAS Guidance & Control Conference, AAS Paper 10-052, 2010. Google Scholar[17] Maass B., Woicke S., Oliveria W. M., Razgus B. and Krüger H., “Crater Navigation System for Autonomous Precision Landing on the Moon,” Journal of Guidance, Control, and Dynamics, Vol. 43, No. 8, 2020, pp. 1414–1431. https://doi.org/10.2514/1.G004850 LinkGoogle Scholar[18] Christian J., Derksen H. and Watkins R., “Lunar Crater Identification in Digital Images,” Journal of the Astonautical Sciences, Vol. 68, 2021, pp. 1056–1144. https://doi.org/10.1007/s40295-021-00287-8 CrossrefGoogle Scholar[19] Arnas D. and Mortari D., “Nonlinear Function Inversion Using k-Vector,” Applied Mathematics and Computation, Vol. 320, 2018, pp. 754–768. https://doi.org/10.1016/j.amc.2017.10.009 CrossrefGoogle Scholar[20] Arnas D., Leake C. and Mortari D., “Random Sampling Using k-Vector,” Computing in Science and Engineering, Vol. 21, No. 1, 2018, pp. 94–107. https://doi.org/10.1109/MCSE.2018.2882727 Google Scholar[21] Zobel J. and Moffat A., “Inverted Files for Text Search Engines,” ACM Computing Surveys (CSUR), Vol. 38, No. 2, 2006. https://doi.org/10.1145/1132956.1132959 Google Scholar[22] Piatetsky-Shapiro G. and Connell C., “Accurate Estimation of the Number of Tuples Satisfying a Condition,” ACM SIGMOD Record, Vol. 14, No. 2, 1984, pp. 256–276. https://doi.org/10.1145/971697.602294 Google Scholar[23] Raab M. and Steger A., “ ‘Balls into Bins’—A Simple and Tight Analysis,” Lecture Notes in Computer Science, Vol. 1518, 1999, pp. 159–170. https://doi.org/10.1007/3-540-49543-6_13 Google Scholar[24] Jagadish H. V., Koudas N., Muthukrishnan S., Poosala V., Sevcik K. C. and Suel T., “Optimal Histograms with Quality Guarantees,” VLDB, Vol. 98, 1998, pp. 24–27. Google Scholar[25] Gibbons P. B., Matias Y. and Poosala V., “Fast Incremental Maintenance of Approximate Histograms,” ACM Transactions on Database Systems (TODS), Vol. 27, No. 3, 2002, pp. 261–298. https://doi.org/10.1145/581751.581753 Google Scholar[26] Asano T., Edahiro M., Imai H., Iri M. and Murota K., “Practical Use of Bucketing Techniques in Computational Geometry,” Machine Intelligence and Pattern Recognition, Vol. 2, 1989, pp. 153–195. https://doi.org/10.1016/B978-0-444-87806-9.50011-6 Google Scholar[27] Devroye L., Lecture Notes on Bucket Algorithms, Birkhäuser, Boston, 1986. Google Scholar[28] Stevens H., “Hans Peter Luhn and the Birth of the Hashing Algorithm,” IEEE Spectrum, Vol. 55, No. 2, 2018, pp. 44–49. https://doi.org/10.1109/MSPEC.2018.8278136 Google Scholar[29] Bentley J. L., Weide B. W. and Yao A. C., “Optimal Expected-Time Algorithms for Closest Point Problems,” ACM Transactions on Mathematical Software, Vol. 6, No. 4, 1980, pp. 563–580. https://doi.org/10.1145/355921.355927 Google Scholar[30] Knott G. D., “Hashing Functions,” Computer Journal, Vol. 18, No. 3, 1975, pp. 265–278. https://doi.org/10.1093/comjnl/18.3.265 Google Scholar[31] Yao A. C., “Uniform Hashing Is Optimal,” Journal of the Associate for Computing Machinery, Vol. 32, No. 3, 1985, pp. 687–693. https://doi.org/10.1145/3828.3836 Google Scholar[32] Isaac E. J. and Singleton R. C., “Sorting by Address Calculation,” Journal of the ACM, Vol. 3, No. 3, 1956, pp. 169–174. https://doi.org/10.1145/320831.320834 Google Scholar[33] Cormen T. H., Introduction to Algorithms, MIT Press, Boston, 2009, pp. 262–269. Google Scholar[34] Price C. E., “Table Lookup Techniques,” ACM Computing Surveys, Vol. 3, No. 2, 1971, pp. 49–64. https://doi.org/10.1145/356586.356587 Google Scholar[35] Perl Y., Itai A. and Avni H., “Interpolation Search–A Log Log N Search,” Communications of the ACM, Vol. 21, No. 7, 1978, pp. 550–553. https://doi.org/10.1145/359545.359557 Google Scholar[36] Kronmal R. and Tarter M., “Cumulative Polygon Address Calculation Sorting,” Proceedings of the 1965 ACM 20th National Conference, Assoc. for Computing Machinery, New York, 1965, pp. 376–385. https://doi.org/10.1145/800197.806060 Google Scholar[37] Carter J. L. and Wegman M. N., “Universal Classes of Hash Functions,” Journal of Computer and System Sciences, Vol. 18, No. 2, 1979, pp. 143–154. https://doi.org/10.1016/0022-0000(79)90044-8 Google Scholar[38] Bayer R. and McCreight E. M., “Organization and Maintenance of Large Ordered Indexes,” Acta Informatica, Vol. 1, No. 3, 1972, pp. 173–189. https://doi.org/10.1007/BF00288683 Google Scholar[39] Comer D., “Ubiquitous B-Tree,” ACM Computing Surveys (CSUR), Vol. 11, No. 2, 1979, pp. 121–137. https://doi.org/10.1145/356770.356776 CrossrefGoogle Scholar[40] Graefe G., “Modern B-Tree Techniques,” Foundations and Trends in Databases, Vol. 3, No. 4, 2010, pp. 203–402. https://doi.org/10.1561/1900000028 Google Scholar[41] Perryman M. A. C., Lindegren L., Kovalevsky J., Hoeg E., Bastian U., Bernacca P. L., Crézé M., Donati F., Grenon M. and Grewing M. et al., “The Hipparcos Catalogue,” Astronomy and Astrophysics, Vol. 323, 1997, pp. L49–L52. Google Scholar[42] van Leeuwen F., “Validation of the New Hipparcos Reduction,” Astronomy and Astrophysics, Vol. 474, No. 2, 2007, pp. 653–664. https://doi.org/10.1051/0004-6361:20078357 Google Scholar[43] Cai T., Fan J. and Jiang T., “Distributions of Angles in Random Packing on Spheres,” Journal of Machine Learning Research, Vol. 14, 2013, pp. 1837–1864, http://jmlr.org/papers/v14/cai13a.html. Google Scholar Previous article Next article FiguresReferencesRelatedDetails What's Popular Volume 45, Number 11November 2022 CrossmarkInformationCopyright © 2022 by John Christian and Joy Arulraj. Published by the American Institute of Aeronautics and Astronautics, Inc., with permission. All requests for copying and permission to reprint should be submitted to CCC at www.copyright.com; employ the eISSN 1533-3884 to initiate your request. See also AIAA Rights and Permissions www.aiaa.org/randp. TopicsAlgorithms and Data StructuresApplied MathematicsComputing and InformaticsComputing, Information, and CommunicationData Base Management SystemsData ManagementData ProcessingData ScienceDatabasesElementary AlgebraGeneral PhysicsSearch AlgorithmStatistical Analysis KeywordsData StructuresHistogramsDatabase Management SystemsInterpolation SearchLinear MappingData RetrievalOracle DatabaseSpace ExplorationPDF Received16 January 2022Accepted15 July 2022Published online1 September 2022