Concretely, I'm looking for a method to search for all CPAN modules that use module X. Is this possible without having to download, uncompress, and inspect every module? If no, can this be added to search.cpan.org?
Many other scenarious could be stated in which a search on dependency would be useful. For example, how many modules make use of Module::Build? Such answers could factor into decision making, such as deciding which modules to include into the standard Perl distribution and when.
With this information, we could also apply a Google-like link analysis algorithm (where module dependencies define the links) to improve the relevency of search.cpan.org and weed out unpopular Acme::-like modules from the results. I believe this would be the most natural way to apply link analysis to CPAN. Link spamming, however, is unlikely:
# MyModule.pm use YourModule; use HisModule; use HerModule; use TheirModule; # ... do nothing with the above modules
# YourModule.pm use MyModule; use MyModule; use MyModule; use MyModule; # ... do nothing with MyModule
-davidm