{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T17:02:54Z","timestamp":1783098174070,"version":"3.54.6"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2005,9,1]],"date-time":"2005-09-01T00:00:00Z","timestamp":1125532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,9]]},"abstract":"<jats:p>The critical resource that limits the application of best-first search is memory. We present a new class of best-first search algorithms that reduce the space complexity. The key idea is to store only the Open list of generated nodes, but not the Closed list of expanded nodes. The solution path can be recovered by a divide-and-conquer technique, either as a bidirectional or unidirectional search. For many problems, frontier search dramatically reduces the memory required by best-first search. We apply frontier search to breadth-first search of sliding-tile puzzles and the 4-peg Towers of Hanoi problem, Dijkstra's algorithm on a grid with random edge costs, and the A* algorithm on the Fifteen Puzzle, the four-peg Towers of Hanoi Problem, and optimal sequence alignment in computational biology.<\/jats:p>","DOI":"10.1145\/1089023.1089024","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"715-748","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Frontier search"],"prefix":"10.1145","volume":"52","author":[{"given":"Richard E.","family":"Korf","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weixiong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Washington University, St. Louis, Missouri"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ignacio","family":"Thayer","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Heath","family":"Hohwald","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, California"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Genome Informatics Workshop IV, 94--102","author":"Araki S."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL). Congressus Numerantium","volume":"139","author":"Bode J.-P."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1023\/A:1018972901171","article-title":"The parallel search bench ZRAM and its applications","volume":"90","author":"Brungger A.","year":"1999","journal-title":"Ann. Oper. Res."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90010-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1111\/0824-7935.00065","article-title":"Pattern databases","volume":"14","author":"Culberson J.","year":"1998","journal-title":"Computat. Intell."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra E.","year":"1959","journal-title":"Numer. Math."},{"key":"e_1_2_1_7_1","unstructured":"Dudeney H. 1908. The Canterbury Puzzles (and Other Curious Problems). E.P. Dutton New York.  Dudeney H. 1908. The Canterbury Puzzles (and Other Curious Problems). E.P. Dutton New York."},{"key":"e_1_2_1_8_1","first-page":"219","article-title":"Editorial note concerning advanced problem 3918","volume":"48","author":"Dunkel O.","year":"1941","journal-title":"Amer. Math. Month."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1613\/jair.1480","article-title":"Additive pattern database heuristics","volume":"22","author":"Felner A.","year":"2004","journal-title":"J. Artif. Intell. Res."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-04)","author":"Felner A."},{"key":"e_1_2_1_11_1","first-page":"216","article-title":"Solution to advanced problem 3918","volume":"48","author":"Frame J.","year":"1941","journal-title":"Amer. Math. Month."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 12th National Conference on Artificial Intelligence (AAAI-94)","author":"Ghosh S."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"2","author":"Hart P.","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cyber. SSC-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Hirschberg D. 1997. Serial computations of levenshtein distances. In Pattern Matching Algorithms A. Apostolic and Z. Galil Eds. Oxford University Press Oxford England 123--141.   Hirschberg D. 1997. Serial computations of levenshtein distances. In Pattern Matching Algorithms A. Apostolic and Z. Galil Eds. Oxford University Press Oxford England 123--141.","DOI":"10.1093\/oso\/9780195113679.003.0007"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03)","author":"Hohwald H."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00093-0"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"397","DOI":"10.2307\/2369492","article-title":"Notes on the 15","volume":"2","author":"Johnson W.","year":"1879","journal-title":"Puzzle. Amer. J. Math."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1613\/jair.460","article-title":"Bidirectional heuristic search reconsidered","volume":"7","author":"Kaindl H.","year":"1997","journal-title":"J. Artif. Intell. Res."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/PL00012582","article-title":"Simple explicit formulas for the Frame- Stewart numbers","volume":"6","author":"Klavzar S.","year":"2002","journal-title":"Ann. Combinat."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90084-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90045-D"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99)","author":"Korf R.","year":"1999"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03)","author":"Korf R.","year":"2003"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-2004)","author":"Korf R.","year":"2004"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 20th National Conference on Artificial Intelligence (AAAI-2005)","author":"Korf R.","year":"2005"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00096-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00094-7"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence (AAAI-00)","author":"Korf R."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1089\/106652701446134","article-title":"The practical use of the A&ast; algorithm for exact multiple sequence alignment","volume":"7","author":"Lermen M.","year":"2000","journal-title":"J. Computat. Biol."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequences of two proteins","volume":"48","author":"Needleman S.","year":"1970","journal-title":"J. Molec. Biol."},{"key":"e_1_2_1_32_1","unstructured":"Pearl J. 1984. Heuristics. Addison-Wesley Reading MA.  Pearl J. 1984. Heuristics. Addison-Wesley Reading MA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0004-3702(70)90007-X","article-title":"Heuristic search viewed as path finding in a graph","volume":"1","author":"Pohl I.","year":"1970","journal-title":"Artif. Intell."},{"key":"e_1_2_1_34_1","volume-title":"Machine Intelligence 6","author":"Pohl I."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93)","author":"Reinefeld A.","year":"1993"},{"key":"e_1_2_1_36_1","volume-title":"Annual Review of Computer Science","author":"Rudin H."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 10th European Conference on Artificial Intelligence (ECAI-92)","author":"Russell S.","year":"1992"},{"key":"e_1_2_1_38_1","volume-title":"Machine Intelligence 3","author":"Schofield P."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89)","author":"Sen A."},{"key":"e_1_2_1_40_1","unstructured":"Setubal J. and Meidanis J. 1997. Introduction to Computational Molecular Biology. PWS Publishing Boston MA.  Setubal J. and Meidanis J. 1997. Introduction to Computational Molecular Biology. PWS Publishing Boston MA."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0149094"},{"key":"e_1_2_1_42_1","first-page":"217","article-title":"Solution to advanced problem 3918","volume":"48","author":"Stewart B.","year":"1941","journal-title":"Amer. Math. Monthly"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-93)","author":"Taylor L."},{"key":"e_1_2_1_44_1","unstructured":"Thayer I. 2003. Methods for optimal multiple sequence alignment. M.S. dissertation. Computer Science Department University of California Los Angeles CA.  Thayer I. 2003. Methods for optimal multiple sequence alignment. M.S. dissertation. Computer Science Department University of California Los Angeles CA."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1093\/bioinformatics\/15.1.87","article-title":"BAli BASE: A benchmark alignment database for the evaluation of multiple alignment programs","volume":"15","author":"Thomson J.","year":"1999","journal-title":"Bioinformatics"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence (AAAI-00)","author":"Yoshizumi T."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-02)","author":"Zhou R."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03)","author":"Zhou R."},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 15th International Conference on Tools with Artificial Intelligence (ICTAI-03)","author":"Zhou R."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS-04)","author":"Zhou R."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089023.1089024","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1089023.1089024","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:21Z","timestamp":1750262901000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089023.1089024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":51,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["10.1145\/1089023.1089024"],"URL":"https:\/\/doi.org\/10.1145\/1089023.1089024","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,9]]},"assertion":[{"value":"2005-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}