More Web Proxy on the site http://driver.im/

Article

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

Authors:

Gene CoopermanAuthors Info & Claims

PASCO '07: Proceedings of the 2007 international workshop on Parallel symbolic computation

Pages 78 - 87

https://doi.org/10.1145/1278177.1278190

Published: 27 July 2007 Publication History

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]

D. Bitton and D. J. DeWitt. Duplicate record elimination in large data files. ACM Trans. Database Syst., 8(2):255--265, 1983.

Digital Library

[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]

G. Cooperman and L. Finkelstein. New methods for using Cayley graphs in interconnection networks. Discrete Applied Mathematics, 37/38: 95--118, 1992. (special issue on Interconnection Networks).

Digital Library

[4]

G. Cooperman, L. Finkelstein, M. Tselman, and B. York. Constructing permutation representations for matrix groups. J. Symbolic Comput., 1997.

Digital Library

[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]

G. Cooperman and E. Robinson. Memory-based and disk-based algorithms for very high degree permutation groups. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC '03), pages 66--73. ACM Press, 2004.

Digital Library

[7]

G. Cooperman and M. Tselman. New sequential and parallel algorithms for generating high dimension Hecke algebras using the condensation technique. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC '96), pages 155--160. ACM Press, 1996.

Digital Library

[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.

Digital Library

[10]

R. E. Korf and P. Schultze. Large-scale parallel breadth-first search. In AAAI, pages 1380--1385, 2005.

Digital Library

[11]

R. E. Korf, W. Zhang, I. Thayer, and H. Hohwald. Frontier search. J. ACM, 52(5):715--748, 2005.

Digital Library

[12]

D. Kunkle and G. Cooperman. Twenty-six moves suffice for Rubik's cube. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC '07). ACM Press, 2007.

Digital Library

[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]

E. Robinson and G. Cooperman. A parallel architecture for disk-based computing over the Baby Monster and other large finite simple groups. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC '06), pages 298--305. ACM Press, 2006.

Digital Library

[19]

E. Robinson, G. Cooperman, and J. Müller. A disk-based parallel implementation for direct condensation of large permutation modules. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC '07). ACM Press, 2007.

Digital Library

[20]

A. W. Roscoe. Model-checking CSP. A classical mind: essays in honour of C. A. R. Hoare, pages 353--378, 1994.

Digital Library

[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.

Digital Library

[24]

R. Zhou and E. A. Hansen. Domain-independent structured duplicate detection. In AAAI, 2006.

Digital Library

Cited By

Korf R(2016)Comparing search algorithms using sorting and hashing on disk and in memoryProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060707(610-616)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060707
Slavici VKunkle DCooperman GLinton Svan der Hoeven Jvan Hoeij M(2012)An efficient programming model for memory-intensive recursive algorithms using parallel disksProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442876(327-334)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442876
Slavici VDong XKunkle DCooperman GKoepf W(2010)Fast multiplication of large permutations for disk, flash memory and RAMProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1838001(355-362)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1837934.1838001
Show More Cited By

Index Terms

A comparative analysis of parallel disk-based Methods for enumerating implicit graphs
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
      2. Game tree search
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

LoneStar RAID: Massive Array of Offline Disks for Archival Systems
Special Issue on Massive Storage Systems and Technologies (MSST 2015)

The need for huge storage archives rises with the ever growing creation of data. With today’s big data and data analytics applications, some of these huge archives become active in the sense that all stored data can be accessed at any time. Running and ...
Accelerated Parallel Hybrid GPU/CPU Hash Table Queries with String Keys
Database and Expert Systems Applications
Abstract
GPUs can accelerate hash tables for fast storage and look-ups utilizing their massive parallelism. State-of-the-art GPU hash tables use keys with fixed length like integers for optimal performance. Because strings are often used for structures ... $^{}$
Improving matrix-based dynamic programming on massively parallel accelerators

Dynamic programming techniques are well-established and employed by various practical algorithms, including the edit-distance algorithm or the dynamic time warping algorithm. These algorithms usually operate in an iteration-based manner where new values ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PASCO '07: Proceedings of the 2007 international workshop on Parallel symbolic computation

July 2007

116 pages

ISBN:9781595937414

DOI:10.1145/1278177

General Chair:
Marc Moreno Maza
The University of Western Ontario, Canada

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC07

Sponsor:

ISSAC07: International Symposium on Symbolic and Algebraic Computation

July 27 - 28, 2007

Ontario, London, Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
218
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Korf R(2016)Comparing search algorithms using sorting and hashing on disk and in memoryProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060707(610-616)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060707
Slavici VKunkle DCooperman GLinton Svan der Hoeven Jvan Hoeij M(2012)An efficient programming model for memory-intensive recursive algorithms using parallel disksProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442876(327-334)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442876
Slavici VDong XKunkle DCooperman GKoepf W(2010)Fast multiplication of large permutations for disk, flash memory and RAMProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1838001(355-362)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1837934.1838001
Kunkle D(2010)RoomyProceedings of the 4th International Workshop on Parallel and Symbolic Computation10.1145/1837210.1837216(22-25)Online publication date: 21-Jul-2010
https://dl.acm.org/doi/10.1145/1837210.1837216
Kunkle DCooperman G(2009)Harnessing parallel disks to solve Rubik's cubeJournal of Symbolic Computation10.1016/j.jsc.2008.04.01344:7(872-890)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.jsc.2008.04.013
Korf R(2008)Minimizing disk I/O in two-bit breadth-first searchProceedings of the 23rd national conference on Artificial intelligence - Volume 110.5555/1619995.1620047(317-324)Online publication date: 13-Jul-2008
https://dl.acm.org/doi/10.5555/1619995.1620047
Kunkle DCooperman G(2008)Solving Rubik's CubeCommunications of the ACM10.1145/1330311.133031951:4(31-33)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1145/1330311.1330319

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents