Fagin's Algorithm is a popular algorithm for finding the top-$k$ items from multiple ranked lists of the items (i.e., via different scoring functions), using some monotonic aggregation function for the final list's scores.

I'm wondering if there has been any research into a similar algorithm for when the multiple lists have not been ranked yet. My goal is to avoid scoring all the items before finding the top-$k$ in the final list. Approximations or some probabilistic approach would be fine; I'm just not finding the area of research to look into.

Example Data: given $N$ cars, assume there are several scoring functions representing someone's preferences: safetyPreference(), coolnessPreference(), etc., where these functions return a value from $1-5$, with higher being more preferred, and the aggregate preference being the sum across all preference functions.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.