Select in union of sorted arrays: Already known?

Question

I am looking for bibliographic references for the following algorithm/problem: I named it "BiSelect" or "t-ary Select" or "Select in Union of Sorted Arrays", but I guess it was introduced before under another name?

Problem

Consider the following problem:

Given $k$ disjoint sorted arrays $A_1,\ldots, A_k$, of respective sizes $n_1,\ldots,n_k$, and an integer $t\in[1..\sum n_i]$, what is the $t$-th value of their sorted union $\cup_i A_i$?

Solutions

There is a very simple and elegant algorithm running in time $O(\lg\min\{n_1,n_2,t\})$ if $k=2$: if $k=2$, just compare $A_1[t/2]$ with $A_2[t/2]$ and recurse on $A_1[t/2..t]$ and $A_2[1..t/2]$ or $A_1[1..t/2]$ and $A_2[t/2..t]$ accordingly, in both cases with parameter $t/2$ (and some minor optimizations when $n_1$ or $n_2$ are smaller than $t$).

This generalizes to a slightly more sophisticated algorithm running in time $O(k\lg t)$ for larger values of $k$, based on computing the median of the values $A_i[t/k]$ for $i\in[1..k]$: the $t/k$ smallest elements can be further ignored in the $k/2$ arrays where $A_i[t/k]$ is smaller than the median, and the elements of ranks in $[t-t/k..]$ can be further ignored in the $k/2$ other arrays, resulting in a halving of $t$ in each recurrence (and a cost of $O(k)$ for the median).

References?

I am happy with my solution(s), but I suppose that the problem (and its solution) was already known. It is related to the linear time algorithm for computing the median (by sorting groups of size $5$, and recurse on the median of their middles), but is slightly more general. I asked several colleges at Madalgo in Aarhus (Denmark), and then some others at the workshop Stringology (Rouen), without success: I am hoping that someone more knowledgeable might help on Stack Exchange...

Motivations

Solutions to this problem have applications to Deferred Data Structure on arrays (indeed, it can be seen as an operator in a deferred data structure for the union of sorted arrays); and in a more convoluted way, to the adaptive computation of optimal prefix free codes.

Answer 1

The algorithm described by Frederickson and Johnson in 1982 considers that all sets have the same size. They also described in 1980 an optimal solution that takes advantage of the different sizes of the sorted sets. The complexity of this algorithm is within $O(k + \sum^k_{i=1}\log{n_i})$.

Reference

Greg N. Frederickson and Donald B. Johnson. 1980. Generalized selection and ranking (Preliminary Version). In Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80). ACM, New York, NY, USA, 420-428. DOI=10.1145/800141.804690 http://doi.acm.org/10.1145/800141.804690

Answer 2

Frederickson and Johnson obtained an optimal result in the 80s. Let $p=\min(k,t)$, then there exist an algorithm solves your problem in $O(k+p \log \frac{t}{p})$.

Reference

G.N. Frederickson, D.B. Johnson "The complexity of selection and ranking in x+y and matrices with sorted columns" J. Comput. System Sci., 24 (2) (1982), pp. 197–208

Answer 3

The k=2 case comes up in parallel merge sort since the merging of two sorted arrays from different threads needs to be split up among two threads to maintain the same amount of parallelism. This homework solution is one reference.