mlocate binary package in Ubuntu Xenial amd64

 mlocate is a new implementation of locate, a tool to find files
 anywhere in the filesystem based on their name, using a fixed pattern
 or a regular expression. Unlike other tools like find(1), locate uses
 a previously created database to perform the search, allowing queries
 to execute much faster. This database is updated periodically from
 cron.
 .
 Several implementations of locate exist: the original implementation
 from GNU's findutils, slocate, and mlocate. The advantages of mlocate
 are:
 .
  * it indexes all the filesystem, but results of a search will only
    include files that the user running locate has access to. It does
    this by updating the database as root, but making it unreadable for
    normal users, who can only access it via the locate binary. slocate
    does this as well, but not the original locate.
 .
  * instead of re-reading all the contents of all directories each time
    the database is updated, mlocate keeps timestamp information in its
    database and can know if the contents of a directory changed without
    reading them again. This makes updates much faster and less demanding
    on the hard drive. This feature is only found in mlocate.
 .
 Installing mlocate will change the /usr/bin/locate binary to point to
 mlocate via the alternatives mechanism. After installation, you may
 wish to run /etc/cron.daily/mlocate by hand to create the database,
 otherwise mlocate won't work until that script is run from cron itself
 (since mlocate does not use the same database file as standard locate).
 Also, you may wish to remove the "locate" package in order not to have
 two different database files updated regularly on your system.

Source package