I have history-search-backward and its reverse mapped to page up and page down. A rare few Linux distributions enable them by default, but the rest frequently have a commented example in /etc/inputrc that can be copied to your ~/.inputrc (note that programs using editline instead of readline will need additional configuration).