Linear-time disk-based implicit graph search

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear-time disk-based implicit graph search

Full text

Pdf (266 KB)

Source

Journal of the ACM (JACM) archive
Volume 55 , Issue 6 (December 2008) table of contents

Article No. 26

Year of Publication: 2008

ISSN:0004-5411

Author

Richard E. Korf

University of California, Los Angeles, Los Angeles, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 456, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1455248.1455250 What is a DOI?

ABSTRACT

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 × 7, 3 × 5, 4 × 4, and 2 × 8 sliding-tile Puzzles, verifying the radius of the 4 × 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Deepak Ajwani , Roman Dementiev , Ulrich Meyer, A computational study of external-memory BFS algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.601-610, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109623]
	2	Bao, T., and Jones, M. 2005. Time-efficient model checking with magnetic disk. In Proceedings of the 11th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). Lecture Notes in Computer Science, vol. 3440. Springer-Verlag, New York, 526--540.
	3	Bode, J.-P., and Hinz, A. 1999. Results and open problems on the Tower of Hanoi. In Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing.
	4	Bonet, B. 2008. Efficient algorithms to rank and unrank permutations in lexicographic order. In Proceedings of the 1st International Symposium on Search Techniques in AI and Robotics. Chicago, IL.
	5	Brungger, A., Marzetta, A., Fukuda, K., and Nievergelt, J. 1999. The parallel search bench ZRAM and its applications. Ann. Oper. Res. 90, 45--63.
	6	Culberson, J., and Schaeffer, J. 1998. Pattern databases. Computat. Intell. 14, 3, 318--334.
	7	Dijkstra, E. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269--271.
	8	Edelkamp, S., Jabbar, S., and Schroedl, S. 2004. External A*. In Proceedings of the 27th German Conference on Artificial Intelligence. Lecture Notes in Artificial Intelligence, vol. 3238, Springer-Verlag, New York, 226--240.
	9	Felner, A., Korf, R. E., Meshulam, R., and Holte, R. C. 2007. Compressed pattern databases. J. Artif. Intell. Res. 30 (Oct.), 213--247.
	10	A. Fiat , S. Moses , A. Shamir , I. Shimshoni , G. Tardos, Planning and learning in permutation groups, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.274-279, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63490]
	11	Frame, J. 1941. Solution to advanced problem 3918. Amer. Math. Monthly 48, 216--217.
	12	Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
	13	Hart, P., Nilsson, N., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cyber. SSC-4, 2 (July), 100--107.
	14	Hinz, A. M. 1997. The Tower of Hanoi. In Algebras and Combinatorics: Proceedings of ICAC'97. Springer-Verlag, New York, 277--289.
	15	Johnson, W., and Storey, W. 1879. Notes on the 15 Puzzle. Amer. J. Math. 2, 397--404.
	16	Katriel, I., and Meyer, U. 2003. Elementary graph algorithms in external memory. In Algorithms for Memory Hierarchies. Lecture Notes in Computer Science, vol. 2625. Springer-Verlag, New York, 62--84.
	17	Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
	18	Korf, R. 1997. Finding optimal solutions to Rubik's cube using pattern databases. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI-97). AAAI Press, Menlo Park, CA, 700--705.
	19	Korf, R. 2003a. Breadth-first frontier search with delayed duplicate detection. In Proceedings of the IJCAI03 Workshop on Model Checking and Artificial Intelligence. http://www.ijcai.org, 87--92.
	20	Korf, R. 2003b. Delayed duplicate detection: Extended abstract. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-03). http://www.ijcai.org, 1539--1541.
	21	Korf, R. 2004. Best-first frontier search with delayed duplicate detection. In Proceedings of the National Conference on Artificial Intelligence (AAAI-2004). AAAI Press, Menlo Park, CA, 650--657.
	22	Korf, R. 2008. Minimizing disk I/O in two-bit breadth-first search. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-2008). AAAI Press, Menlo Park, CA.
	23	Richard E. Korf , Ariel Felner, Disjoint pattern database heuristics, Artificial Intelligence, v.134 n.1-2, p.9-22, January 2002 [doi>10.1016/S0004-3702(01)00092-3]
	24	Korf, R., and Felner, A. 2007. Recent progress in heuristic search: A case study of the four-peg towers of hanoi problem. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-07). http://www.ijcai.org, 2334--2329.
	25	Korf, R., and Shultze, P. 2005. Large-scale, parallel breadth-first search. In Proceedings of the 20th AAAI Conference on Artificial Intelligence. AAAI Press, Menlo Park, CA, 1380--1385.
	26	Richard E. Korf , Weixiong Zhang , Ignacio Thayer , Heath Hohwald, Frontier search, Journal of the ACM (JACM), v.52 n.5, p.715-748, September 2005 [doi>10.1145/1089023.1089024]
	27	Daniel Kunkle , Gene Cooperman, Twenty-six moves suffice for Rubik's cube, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277581]
	28	Kurt Mehlhorn , Ulrich Meyer, External-Memory Breadth-First Search with Sublinear I/O, Proceedings of the 10th Annual European Symposium on Algorithms, p.723-735, September 17-21, 2002
	29	Ulrich Meyer, External memory BFS on undirected graphs with bounded degree, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.87-88, January 07-09, 2001, Washington, D.C., United States
	30	Kameshwar Munagala , Abhiram Ranade, I/O-complexity of graph algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.687-694, January 17-19, 1999, Baltimore, Maryland, United States
	31	Wendy Myrvold , Frank Ruskey, Ranking and unranking permutations in linear time, Information Processing Letters, v.79 n.6, p.281-284, September 30, 2001 [doi>10.1016/S0020-0190(01)00141-7]
	32	Bradford Nichols , Dick Buttlar , Jacqueline Proulx Farrell, Pthreads programming, O'Reilly & Associates, Inc., Sebastopol, CA, 1996
	33	Niewiadomski, R., Amaral, J., and Holte, R. 2006. Sequential and parallel algorithms for frontier a* with delayed duplicate detection. In Proceedings of the National Conference on Artificial Intelligence (AAAI-2006). AAAI Press, Menlo Park, CA, 1039--1044.
	34	David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
	35	Giuseppe Della Penna , Benedetto Intrigila , Enrico Tronci , Marisa Venturini Zilli, Exploiting Transition Locality in the Disk Based Mur phi Verifier, Proceedings of the 4th International Conference on Formal Methods in Computer-Aided Design, p.202-219, November 06-08, 2002
	36	A. W. Roscoe, Model-checking CSP, A classical mind: essays in honour of C. A. R. Hoare, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1994
	37	Ulrich Stern , David L. Dill, Using Magnatic Disk Instead of Main Memory in the Murphi Verifier, Proceedings of the 10th International Conference on Computer Aided Verification, p.172-183, June 28-July 02, 1998
	38	Stewart, B. 1941. Solution to advanced problem 3918. Amer. Math. Monthly 48, 217--219.
	39	Zhou, R., and Hansen, E. 2003. Sparse-memory graph search. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-03). http://www.ijcai.org, 1259--1266.
	40	Zhou, R., and Hansen, E. 2004. Structured duplicate detection in external-memory graph search. In Proceedings of the National Conference on Artificial Intelligence (AAAI-2004). AAAI Press, Menlo Park, CA, 683--688.
	41	Zhou, R., and Hansen, E. 2005. External memory pattern databases using structured duplicate detection. In Proceedings of the National Conference on Artificial Intelligence (AAAI-2005). AAAI Press, Menlo Park, CA, 1398--1404.
	42	Rong Zhou , Eric A. Hansen, Breadth-first heuristic search, Artificial Intelligence, v.170 n.4, p.385-408, April 2006 [doi>10.1016/j.artint.2005.12.002]
	43	Zhou, R., and Hansen, E. 2006b. Domain-independent structured duplicate detection. In Proceedings of the National Conference on Artificial Intelligence (AAAI-2006). AAAI Press, Menlo Park, CA, 1082--1087.
	44	Zhou, R., and Hansen, E. 2007a. Edge partitioning in external-memory graph search. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-07). http://www.ijcai.org, 2410--2416.
	45	Zhou, R., and Hansen, E. 2007b. Parallel structured duplicate detection. In Proceedings of the National Conference on Artificial Intelligence (AAAI-2007). AAAI Press, Menlo Park, CA, 1217--1223.