updatedb - апдейт базы данных.
Базы где хранятся имена всех файлов которые были на момент запуска updatedb. locate ищет не по диску, а в этой самой базе. Обычно запуск updatedb кладут в крон.дайли. Обычно на ночь. Это если комп не выключается. Так что обновить не помешает все равно, тем более если прога установлена десятью минутами ранее.
