{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T04:02:32Z","timestamp":1781841752859,"version":"3.54.5"},"reference-count":63,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2011,12,20]],"date-time":"2011-12-20T00:00:00Z","timestamp":1324339200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>We present a novel data structure, the Bayes tree, that provides an algorithmic foundation enabling a better understanding of existing graphical model inference algorithms and their connection to sparse matrix factorization methods. Similar to a clique tree, a Bayes tree encodes a factored probability density, but unlike the clique tree it is directed and maps more naturally to the square root information matrix of the simultaneous localization and mapping (SLAM) problem. In this paper, we highlight three insights provided by our new data structure. First, the Bayes tree provides a better understanding of the matrix factorization in terms of probability densities. Second, we show how the fairly abstract updates to a matrix factorization translate to a simple editing of the Bayes tree and its conditional densities. Third, we apply the Bayes tree to obtain a completely novel algorithm for sparse nonlinear incremental optimization, named iSAM2, which achieves improvements in efficiency through incremental variable re-ordering and fluid relinearization, eliminating the need for periodic batch steps. We analyze various properties of iSAM2 in detail, and show on a range of real and simulated datasets that our algorithm compares favorably with other recent mapping algorithms in both quality and efficiency.<\/jats:p>","DOI":"10.1177\/0278364911430419","type":"journal-article","created":{"date-parts":[[2011,12,20]],"date-time":"2011-12-20T22:55:23Z","timestamp":1324421723000},"page":"216-235","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1084,"title":["iSAM2: Incremental smoothing and mapping using the Bayes tree"],"prefix":"10.1177","volume":"31","author":[{"given":"Michael","family":"Kaess","sequence":"first","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory (CSAIL), Massachusetts Institute of Technology (MIT), Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hordur","family":"Johannsson","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory (CSAIL), Massachusetts Institute of Technology (MIT), Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Roberts","sequence":"additional","affiliation":[{"name":"School of Interactive Computing, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viorela","family":"Ila","sequence":"additional","affiliation":[{"name":"School of Interactive Computing, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John J","family":"Leonard","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory (CSAIL), Massachusetts Institute of Technology (MIT), Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Dellaert","sequence":"additional","affiliation":[{"name":"School of Interactive Computing, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2011,12,20]]},"reference":[{"key":"bibr1-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"bibr2-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"bibr3-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904049393"},{"key":"bibr4-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1985.1087348"},{"key":"bibr5-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/70.795798"},{"key":"bibr6-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"bibr7-0278364911430419","volume-title":"Probabilistic Networks and Expert Systems","author":"Cowell R","year":"1999"},{"key":"bibr8-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024079"},{"key":"bibr9-0278364911430419","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2005.I.024"},{"key":"bibr10-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2010.5650422"},{"key":"bibr11-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906072768"},{"key":"bibr12-0278364911430419","volume-title":"Proceedings 22nd AAAI National Conference on AI","author":"Dellaert F","year":"2005"},{"key":"bibr13-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/70.938381"},{"key":"bibr14-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015269615729"},{"key":"bibr15-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2007.4409098"},{"key":"bibr16-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1307180"},{"key":"bibr17-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2007.900608"},{"key":"bibr18-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2007.4399201"},{"key":"bibr19-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-006-9043-2"},{"key":"bibr20-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2004.839220"},{"key":"bibr21-0278364911430419","unstructured":"Gauss C (1809) Theoria Motus Corporum Coelestium in Sectionibus Conicis Solem Mabientium [Theory of the Motion of the Heavenly Bodies Moving about the Sun in Conic Sections]. Hamburg: Perthes and Besser. English translation available at http:\/\/name.umdl.umich.edu\/AGG8895.0001.001."},{"key":"bibr22-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/12.3.329"},{"key":"bibr23-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0343558-6"},{"key":"bibr24-0278364911430419","volume-title":"Matrix Computations","author":"Golub G","year":"1996","edition":"3"},{"key":"bibr25-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1080\/10867651.1998.10487493"},{"key":"bibr26-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509407"},{"key":"bibr27-0278364911430419","doi-asserted-by":"crossref","unstructured":"Grisetti G, Stachniss C, Grzonka S, Burgard W (2007) A tree parameterization for efficiently computing maximum likelihood maps using gradient descent. In Robotics: Science and Systems (RSS).","DOI":"10.15607\/RSS.2007.III.009"},{"key":"bibr28-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60904-6_4"},{"key":"bibr29-0278364911430419","volume-title":"Lie Groups, Lie Algebras, and Representations: An Elementary Introduction","author":"Hall B","year":"2000"},{"key":"bibr30-0278364911430419","volume-title":"Multiple View Geometry in Computer Vision","author":"Hartley R","year":"2000"},{"key":"bibr31-0278364911430419","volume-title":"Second SIAM Conference on Sparse Matrices","author":"Heggernes P","year":"1996"},{"key":"bibr32-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.876922"},{"key":"bibr33-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.933280"},{"key":"bibr34-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2009.06.008"},{"key":"bibr35-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17452-0_10"},{"key":"bibr36-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5979641"},{"key":"bibr37-0278364911430419","first-page":"2129","volume-title":"International Joint Conference on AI (IJCAI)","author":"Kaess M","year":"2007"},{"key":"bibr38-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2008.2006706"},{"key":"bibr39-0278364911430419","first-page":"3185","volume-title":"IEEE International Conference on Robotics and Automation (ICRA)","author":"Kim B","year":"2010"},{"key":"bibr40-0278364911430419","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"Koller D","year":"2009"},{"key":"bibr41-0278364911430419","volume-title":"Proceedings 21st AAAI National Conference on AI","author":"Konolige K","year":"2004"},{"key":"bibr42-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2008.2004832"},{"key":"bibr43-0278364911430419","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Konolige K","year":"2010"},{"key":"bibr44-0278364911430419","doi-asserted-by":"crossref","unstructured":"Krauthausen P, Dellaert F, Kipp A (2006) Exploiting locality by nested dissection for square root smoothing and mapping. In Robotics: Science and Systems (RSS).","DOI":"10.15607\/RSS.2006.II.010"},{"key":"bibr45-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"key":"bibr46-0278364911430419","first-page":"346","volume":"16","author":"Lipton R","year":"1979","journal-title":"SIAM J Appl Maths"},{"key":"bibr47-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008854305733"},{"key":"bibr48-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2008.2004888"},{"key":"bibr49-0278364911430419","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Ni K","year":"2010"},{"key":"bibr50-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363564"},{"key":"bibr51-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2006.1642040"},{"key":"bibr52-0278364911430419","volume-title":"International Joint Conference on AI (IJCAI)","author":"Paskin M","year":"2003"},{"key":"bibr53-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2008.2004637"},{"key":"bibr54-0278364911430419","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl J","year":"1988"},{"key":"bibr55-0278364911430419","first-page":"34","volume-title":"Proceedings of the Fifth SIAM Conference on Parallel Processing for Scientific Computing","author":"Pothen A","year":"1992"},{"key":"bibr56-0278364911430419","first-page":"2191","volume-title":"International Joint Conference on AI (IJCAI)","author":"Ranganathan A","year":"2007"},{"key":"bibr57-0278364911430419","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2009.V.023"},{"key":"bibr58-0278364911430419","volume-title":"International Symposium on Robotics Research","author":"Smith R","year":"1987"},{"key":"bibr59-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509636"},{"key":"bibr60-0278364911430419","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"bibr61-0278364911430419","volume-title":"Probabilistic Robotics","author":"Thrun S","year":"2005"},{"key":"bibr62-0278364911430419","first-page":"298","volume-title":"Vision Algorithms: Theory and Practice (Lecture Notes in Computer Science, vol. 1883)","author":"Triggs B","year":"1999"},{"key":"bibr63-0278364911430419","unstructured":"Wang Z (2007) Exactly Sparse Information Filters for Simultaneous Localization and Mapping. PhD thesis, The University of Technology, Sydney."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364911430419","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364911430419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:38Z","timestamp":1777457858000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364911430419"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,20]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1177\/0278364911430419"],"URL":"https:\/\/doi.org\/10.1177\/0278364911430419","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12,20]]}}}