Pagination of results from different sources merged by a unified scoring function

Assume a Hotel reservation scenario, given $$m$$ ranked lists of attribute values such as distance, price, amenities (normalized between $$0$$ and $$1$$), and a unifying linear score function $$F(\cdot)=\alpha_1*score_1+ \alpha_2*score_2+ \alpha_3*score_3$$, the Threshold Algorithm (TA) is optimal in finding top-$$k$$ results that have higher $$F$$ values.

However, consider a pagination scenario with page index $$p$$ and page size $$k$$. Indeed, instead of asking for top-$$k$$ that can be obtained from indices [0,k] in the final ranked list, we ask for [pk, (p+1)k]. What is the best solution to obtain this window of the results?

You may consider this problem as the pagination of the merged results over a unified scoring function when there are multiple data sources that each contains a score value but the merged results have a combined score value as a (linear) function of individual score values.

Some solutions:

Totally naive: given the multiple ranked results, compute the unified score, sort them, slice it as needed.

Potentially better but inefficient when asking lower-ranked results (farther pages): Execute Threshold Algorithm and ask for top-(p+1)k, return the [pk, (p+1)k] from it.

• What is meant by a "Hotel reservation scenario"? What is the "Threshold algorithm"? What is a "pagination scenario"? Can you make the question self-contained?
– D.W.
Mar 6, 2020 at 6:12

I think $$F$$ and its details are irrelevant, an appropriate comparison function that uses $$F$$ internally turns your problem into a regular sorting one. Then your problem is solved in $$O(n)$$ using a regular selection problem.
Find the element with rank $$pk$$ in $$O(n)$$ using a selection algorithm. Similarly find the element with rank $$(p+1)k$$. Then do a single linear scan over the array to find all elements that have a value between these two in $$O(n)$$.