Minimal packages/systems reduce potential problem surfaces and maintenance required.
No argument with that. It's just that locate is so universally useful that for me it makes it onto the Minimal Packages list. It's also sufficiently trivial in action and uses so few libraries that (again, IMHO) it does not overly expand the attack surface.
In heading off to CPAN to investigate further, I find a stack of modules (File::Locate::Harder not being least among them) which provide the locate facility. None that I can find, however, provide the database-creation side of it. That might be a worthy project for a rainy day.