Comment 29 for bug 655831

Max Polk has a good analysis. Partly to help google, I would add that on a Quantal 64 bit server installed with "Install a minimal virtual machine" option and 256 MB RAM, the command (simulating the cron job)
  sudo /usr/sbin/update-apt-xapian-index -v -f
results in an additional 300 MB RAM usage (100 MB from swap).

I noticed this issue because almost every day I receive a mail from CRON saying:
  /etc/cron.daily/apt:
  Killed

Looking at syslog, the kernel frequently kills it:
Apr 13 10:37:43 regmail1 kernel: [325133.105582] select 1 (init), adj 0, size 167, to kill
Apr 13 10:37:43 regmail1 kernel: [325133.105592] select 625 (java), adj 0, size 15923, to kill
Apr 13 10:37:43 regmail1 kernel: [325133.105596] select 3915 (update-apt-xapi), adj 0, size 36048, to kill
Apr 13 10:37:43 regmail1 kernel: [325133.105598] send sigkill to 3915 (update-apt-xapi), adj 0, size 36048

Obviously the indexing algorithm which was chosen is either extremely RAM hungry, or the implementation has a bug.