Exploiting the Rubik's Cube 12-edge PDB by combining partial pattern databases and Bloom filters

Sturtevant, Nathan R. and Felner, Ariel and Helmert, Malte. (2014) Exploiting the Rubik's Cube 12-edge PDB by combining partial pattern databases and Bloom filters. In: Proceedings of the Seventh International Symposium on Combinatorial Search (SoCS-2014), 15 - 17 August 2014, Prague, Czech Republic. Palo Alto, Calif., pp. 175-183.

PDF - Published Version

Official URL: http://edoc.unibas.ch/dok/A6337573

Downloads: Statistics Overview


Pattern Databases (PDBs) are a common form of abstraction-based heuristic which are often compressed so that a large PDB can fit in memory. Partial Pattern Databases (PPDBs) achieve this by storing only layers of the PDB which are close to the goal. This paper studies the problem of how to best compress and use the 457 GB 12-edge Rubik's cube PDB, suggesting a number of ways that Bloom filters can be used to effectively compress PPDBs. We then develop a theoretical model of the common min compression approach and our Bloom filters, showing that the original method of compressed PPDBs can never be better than min compression. We conclude with experimental results showing that Bloom filter compression of PPDBs provides superior performance to min compression in Rubik's cube.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:27 Nov 2018 15:59
Deposited On:03 Jul 2015 08:53

Repository Staff Only: item control page