Comparing Search Algorithms Using Sorting and Hashing on Disk and in Memory

Korf, Richard E.

Comparing Search Algorithms Using Sorting and Hashing on Disk and in Memory

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 610-615.

Abstract

We compare sorting and hashing for implicit graph search using disk storage. We first describe efficient pipelined implementations of both algorithms, which reduce disk I/O. We then compare the two algorithms and find that hashing is faster, but that sorting requires less disk storage. We also compare disk-based with in-memory search, and surprisingly find that there is little or no time overhead associated with disk-based search. We present experimental results on the sliding-tile puzzles, Rubik's Cube, and the 4-peg Towers of Hanoi.

Richard E. Korf. 2016. Comparing Search Algorithms Using Sorting and Hashing on Disk and in Memory. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 610–615. https://ijcai.org/proceedings/2016/93

@inproceedings{ijcai2016p93,
  title     = {Comparing Search Algorithms Using Sorting and Hashing on Disk and in Memory},
  author    = {Korf, Richard E.},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {610--615},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/93},
}

TY  - CPAPER
TI  - Comparing Search Algorithms Using Sorting and Hashing on Disk and in Memory
AU  - Korf, Richard E.
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 610
EP  - 615
UR  - https://ijcai.org/proceedings/2016/93
ER  -