Prioritizing information for the discovery of phenomena. Final report

We consider the problem of prioritizing a collection of discrete pieces of information, or transactions. The goal is to rank the transactions in such a way that the user can best pursue a subset of the transactions in hopes of discovering those which were generated by an interesting source. The problem is shown to differ from traditional classification in several fundamental ways. Ranking algorithms are divided into two classes, depending on the amount of information they may utilize. We demonstrate that while ranking by the less constrained algorithm class is consistent with classification, such is not the case for the more constrained class of algorithms. We demonstrate also that while optimal ranking by the former class is {open_quotes}easy{close_quotes}, optimal ranking by the latter class is NP-hard. We present heuristics for optimally solving restricted versions of the detection problem, including symmetric anomaly detection. Finally, we explore heuristics for more general detection applications and present preliminary results of an experimental implementation of these heuristics