{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:28:15Z","timestamp":1762100895996,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2008,12,1]],"date-time":"2008-12-01T00:00:00Z","timestamp":1228089600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["EIA-0113313IIS-0713178"],"award-info":[{"award-number":["EIA-0113313IIS-0713178"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["EIA-0113313IIS-0713178"],"award-info":[{"award-number":["EIA-0113313IIS-0713178"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:p>Many search algorithms are limited by the amount of memory available. Magnetic disk storage is over two orders of magnitude cheaper than semiconductor memory, and individual disks can hold up to a terabyte. We augment memory with magnetic disks to perform brute-force and heuristic searches that are orders of magnitude larger than any previous such searches. The main difficulty is detecting duplicate nodes, which is normally done with a hash table. Due to long disk latencies, however, randomly accessed hash tables are infeasible on disk, and are replaced by a mechanism we call delayed duplicate detection. In contrast to previous work, we perform delayed duplicate detection without sorting, which runs in time linear in the number of nodes in practice. Using this technique, we performed the first complete breadth-first searches of the 2 x 7, 3 x 5, 4 x 4, and 2 x 8 sliding-tile Puzzles, verifying the radius of the 4 x 4 puzzle and determining the radius of the others. We also performed the first complete breadth-first searches of the four-peg Towers of Hanoi problem with up to 22 discs, discovering a surprising anomaly regarding the radii of these problems. In addition, we performed the first heuristic searches of the four-peg Towers of Hanoi problem with up to 31 discs, verifying a conjectured optimal solution length to these problems. We also performed partial breadth-first searches of Rubik's Cube to depth ten in the face-turn metric, and depth eleven in the quarter-turn metric, confirming previous results.<\/jats:p>","DOI":"10.1145\/1455248.1455250","type":"journal-article","created":{"date-parts":[[2008,12,17]],"date-time":"2008-12-17T13:25:20Z","timestamp":1229520320000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Linear-time disk-based implicit graph search"],"prefix":"10.1145","volume":"55","author":[{"given":"Richard E.","family":"Korf","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109623"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31980-1_34"},{"volume-title":"Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing.","author":"Bode J.-P.","key":"e_1_2_1_3_1"},{"volume-title":"Proceedings of the 1st International Symposium on Search Techniques in AI and Robotics","year":"2008","author":"Bonet B.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018972901171"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/0824-7935.00065"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"volume":"3238","volume-title":"Proceedings of the 27th German Conference on Artificial Intelligence. Lecture Notes in Artificial Intelligence","author":"Edelkamp S.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622637.1622643"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63490"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2304268"},{"key":"e_1_2_1_12_1","unstructured":"Garcia-Molina H. Ullman J. D. and Widom J. 2000. Database System Implementation. Prentice-Hall Englewood Cliffs NJ.   Garcia-Molina H. Ullman J. D. and Widom J. 2000. Database System Implementation. Prentice-Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"volume-title":"The Tower of Hanoi. In Algebras and Combinatorics: Proceedings of ICAC'97","year":"1997","author":"Hinz A. M.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/2369492"},{"volume":"2625","volume-title":"Algorithms for Memory Hierarchies. Lecture Notes in Computer Science","author":"Katriel I.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90084-0"},{"volume-title":"Proceedings of the 14th National Conference on Artificial Intelligence (AAAI-97)","year":"1997","author":"Korf R.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the IJCAI03 Workshop on Model Checking and Artificial Intelligence. http:\/\/www.ijcai.org, 87--92","year":"2003","author":"Korf R.","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-03)","year":"2003","author":"Korf R.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI-2004)","year":"2004","author":"Korf R.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-2008)","year":"2008","author":"Korf R.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00092-3"},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-07)","author":"Korf R.","key":"e_1_2_1_24_1"},{"volume-title":"Proceedings of the 20th AAAI Conference on Artificial Intelligence. AAAI Press","author":"Korf R.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089024"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277548.1277581"},{"volume":"2461","volume-title":"Proceedings of the 10th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science","author":"Mehlhorn K.","key":"e_1_2_1_28_1"},{"volume-title":"Proceedings of the 12th Annual Symposium on Discrete Algorithms. ACM-SIAM","year":"2001","author":"Meyer U.","key":"e_1_2_1_29_1"},{"volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Munagala K.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00141-7"},{"key":"e_1_2_1_32_1","unstructured":"Nichols B. Butler D. and Farrell J. 1996. Pthreads Programming. O'Reilly.   Nichols B. Butler D. and Farrell J. 1996. Pthreads Programming. O'Reilly."},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI-2006)","author":"Niewiadomski R.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50214"},{"volume":"2517","volume-title":"Proceedings of the 4th International Conference on Formal Methods in Computer-Aided Design. Lecture Notes in Computer Science","author":"Penna G. D.","key":"e_1_2_1_35_1"},{"volume-title":"A Classical Mind, Essays in Honour of CAR Hoare","author":"Roscoe A.","key":"e_1_2_1_36_1"},{"volume-title":"Proceedings of the 10th International Conference on Computer-Aided Verification. 172--183","author":"Stern U.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","first-page":"217","article-title":"Solution to advanced problem 3918","volume":"48","author":"Stewart B.","year":"1941","journal-title":"Amer. Math. Monthly"},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-03)","author":"Zhou R.","key":"e_1_2_1_39_1"},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI-2004)","author":"Zhou R.","key":"e_1_2_1_40_1"},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI-2005)","author":"Zhou R.","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2005.12.002"},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI-2006)","author":"Zhou R.","key":"e_1_2_1_43_1"},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-07)","author":"Zhou R.","key":"e_1_2_1_44_1"},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI-2007)","author":"Zhou R.","key":"e_1_2_1_45_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1455248.1455250","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1455248.1455250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:00Z","timestamp":1750253400000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1455248.1455250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1145\/1455248.1455250"],"URL":"https:\/\/doi.org\/10.1145\/1455248.1455250","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2008,12]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}