I see that apt-xapian-index has been removed from Debian (and it looks like Ubuntu, too). I can't say I entirely understand the reasons for the removal. At least one justification that was given for Ubuntu is the poor user experience for Synaptic when the index is being rebuilt. And while I agree that the experience is poor, I'd rather have that than have to use the standard Synaptic search UI, which I find klunky.
Anyway, is there some other package that provides an alternative to the standard Synaptic search UI? I suppose I could just start using "apt-cache search"... thanks, mike