TopN

Top-N refers to the task of identifying the N items with the highest scores, relevance, or probability from a set of candidates. The concept is used across information retrieval, machine learning, and data mining to produce compact, interpretable results such as the top search results, top recommended items, or top predicted classes. In classification, top-N predictions are the N class labels with the highest predicted probabilities; in retrieval, top-N refers to the highest-ranked documents or items.

Computationally, top-N can be obtained by scoring all candidates and selecting the N highest scores. Exact approaches include sorting the entire list in descending order, or using a min-heap (priority queue) of size N to maintain the current top-N as items arrive, yielding O(m log N) time for m candidates and O(N) space. If full sorting is expensive, selection algorithms like Quickselect can find the Nth largest value in O(m) average time, after which one can collect those above the threshold. In streaming or large-scale settings, approximate top-N methods or probabilistic data structures may be used to reduce cost at the expense of occasional inaccuracies.

Evaluation and practical considerations often involve metrics such as top-N accuracy, precision at N, recall at N, or ranking measures like NDCG, depending on the application. Details include handling ties when multiple items share identical scores, determinism in tie breaking, and choosing N based on user experience or system constraints. Common implementations exist in SQL with ORDER BY score DESC LIMIT N, in Python with heapq.nlargest, and in machine learning libraries as part of prediction or evaluation tooling.