KwickFind is a GUI frontend for locate.
Instantly find files on your computer. Results are returned in about 1 second.
If a file has recently been added to the system you should update the database (you will be prompted for the root password). Cron may already be setup on your computer to run updatedb every night. If not you may want to add it.
For more info on the linux locate command type man locate in konsole.