It seems very clear to me that the Menu package is what you are looking for. it's strange that nobody has said anything about it since you posted your question; The README file of /usr/doc/menu answers most of your askings.
First, you must have a debian system, this shouldn't be a problem _here_ . I believe the menu package is installed by default. of course, the system is more complex, but here is rufly how it work: almost all package you install via a normal way (eg dpkg -i ) create a file in /usr/lib/menu/package-name. this file contains: the name of the program, a one-line description (maybe a little more precise than apropos, definitly not the same) the type (X11,text,...) the section (Apps/Editors, Games/Strategy ...) the path of a (very :-( ) optional icon, the executable file, and other stuff i cannot remenber so far i understood, the main goal of all this is to help users finding applications (!!!) and so far i know, only Window managers are using those files in order to create inteligent menus. i saw somewhere that one of them (afterstep ?) even use the "description" field to add mini-ballons's popups along the menus dynamicaly created. With this base installed, it should be a lot easier to create a frontend for finding apps than creating it from dpkg -l or -L outputs ( what is THE executable ?, and ignoring the secondary ones ). On the other side, for this to work, you must install well-made deb packages which include this feature. too often, package maintainers (?) forget this. This is included in debian since at least the bo (1.3) distribution. So Tommy, does it answers some questions ? the strangiest part is that i thought before that everybody was using it , and it's hard to admit that somes deactivate it. you probably use it and dislike it for unknown reasons. that's must be. PS: this is my second mail about "finding applications" , i wonder what happened to the first..