FWIW.
As part of my recent rediscovery of Linux command line tools, I have become quite enamoured with fzf.
I now have a terminal tab with it permanently open.
It doesn't constantly rescan the filesystem but takes only about 30 seconds to run `cd /; fzf` on my system (about 1.5M files , most of which are on CIFS-mounted filesystems). So killing and restarting when I need it doesn't bother me.
It doesn't work the same way as ?locate in that you just start typing what you're looking for and it filters down the matches with each character you type.
Indeed, it's possible to use them together if plocate generates a large list of matches. Just pipe the output of plocate to fzf.