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

Question

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.

Answer 1

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)$.