A comparative analysis of parallel disk-based Methods for enumerating implicit graphs

ABSTRACT

It is only in the last five years that researchers have begun to use disk-based search techniques on a large scale. The primary examples of its use come from symbolic algebra and from artificial intelligence. In the field of parallel search, disk-based search has been forced on researchers because the historical growth in the amount of RAM per CPU core has now stopped. Indeed, the current trend toward multi-core CPUs now threatens to take us backwards.

This article makes an original contribution to the design of disk-based parallel search algorithms. It presents a survey of disk-based techniques side-by-side, for the first time. This allows researchers to choose from a menu of techniques, and also to create new hybrid algorithms from the building blocks presented here.

REFERENCES

• 1: Dina Bitton , David J. DeWitt, Duplicate record elimination in large data files, ACM Transactions on Database Systems (TODS), v.8 n.2, p.255-265, June 1983 [doi>10.1145/319983.319987]
• 2: J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson. Atlas of finite groups. Clarendon Press, Oxford, 1985.
• 3: Gene Cooperman , Larry Finkelstein, New methods for using Cayley graphs in interconnection networks, Discrete Applied Mathematics, 37-38, p.95-118, July 15, 1992 [doi>10.1016/0166-218X(92)90127-V ]
• 4: Gene Cooperman , Larry Finkelstein , Michael Tselman , Bryant York, Constructing permutation representations for matrix groups, Journal of Symbolic Computation, v.24 n.3-4, p.471-488, Sept./Oct. 1997 [doi>10.1006/jsco.1997.0146 ]
• 5: G. Cooperman, W. Lempken, G. Michler, and M. Weller. A new existence proof of Janko's simple group j4. In Progress In Mathematics, volume 173, pages 161--175. Birkhauser, 1999.
• 6: Gene Cooperman , Eric Robinson, Memory-based and disk-based algorithms for very high degree permutation groups, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.66-73, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860877]
• 7: Gene Cooperman , Michael Tselman, New sequential and parallel algorithms for generating high dimension Hecke algebras using the condensation technique, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.155-160, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236927]
• 8: A. H. Frey Jr. and D. Singmaster. Handbook of Cubik Math. Enslow Publishers, 1982.
• 9: R. E. Korf. Best-first frontier search with delayed duplicate detection. In AAAI, pages 650--657, 2004.
• 10: R. E. Korf and P. Schultze. Large-scale parallel breadth-first search. In AAAI, pages 1380--1385, 2005.
• 11: 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]
• 12: 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]
• 13: F. Lübeck and M. Neunhöffer. Enumerating large orbits and direct condensation. Experiment. Math, 10:197--206, 2001.
• 14: S. Radu. Solving Rubik's cube in 28 face turns. http: //cubezzz.homelinux.org/drupal/?q=node/view/37, 2005.
• 15: S. Radu. Rubik can be solved in 27f. http://cubezzz.homelinux.org/drupal/?q=node/view/53, 2006.
• 16: M. Reid. New upper bounds. http://www.math.rwth-aachen.de/?Martin.Schoenert/Cube-Lovers/michael reid new upper bounds.html, 1995.
• 17: M. Reid. Super ip requires 20 face turns. http://www.math.rwth-aachen.de/?Martin.Schoenert/Cube-Lovers/michael reid superflip requires 20 face turns.html, 1995.
• 18: Eric Robinson , Gene Cooperman, A parallel architecture for disk-based computing over the Baby Monster and other large finite simple groups, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145817]
• 19: Eric Robinson , Jürgen Müller , Gene Cooperman, A disk-based parallel implementation for direct condensation of large permutation modules, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277591]
• 20: 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
• 21: M. Weller. Construction of large permutation representations for matrix groups. In W. Jäger E. Krause, editor, High Performance Computing in Science and Engineering '98, pages 430--. Springer, 1999.
• 22: M. Weller. Construction of large permutation representations for matrix groups ii. Applicable Algebra in Engineering, Communication and Computing, 11:463--488, 2001.
• 23: R. Zhou and E. A. Hansen. Structured duplicate detection in external-memory graph search. In AAAI, pages 683--689, 2004.
• 24: R. Zhou and E. A. Hansen. Domain-independent structured duplicate detection. In AAAI, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms

Keywords:
disk-based, enumeration, implicit graphs, parallel, search