- Run checkers on packages (lintian, piuparts, linda)
- Rebuild packages, check whether they correspond good enough with what's in
  the archive (still build? No added/dropped dependencies/other stuff?)
- Try building under 'weird' environments: different kernel, different
  filesystem (XFS has some nasty stuff), as root, etc
- Extract data you want readily available: changelog, watch files, copyright, control file
- Look at and compare/process such data: override disparities, installability
  by comparing the control files, etc
- Extract library type data (exported symbols, required symbols)
- Again, look at, and compare and warn about issues
- Store human-supplied info (graphics, descriptions, reviews)

Non-package based:
- By bug: store who sent in comments, so that you can easily search that
- By mirror: check whether the mirror is still alive and uptodate
- By maintainer: which packages one maintains
- By source: which binary packages are there (and use it throughout all the rest)