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.

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Mar 6 '20 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.