Seleccione en unión de matrices ordenadas: ¿Ya lo sabe?

Estoy buscando referencias bibliográficas para el siguiente algoritmo / problema: lo llamé "BiSelect" o "t-ary Select" o "Select in Union of Sorted Arrays", pero supongo que se introdujo antes con otro nombre.

Problema

Considere el siguiente problema:

Dados $k$ conjuntos ordenados disjuntos $A_1,\ldots, A_k$ , de tamaños respectivos $n_1,\ldots,n_k$ , y un número entero $t\in[1..\sum n_i]$ , ¿cuál es el valor $t$ de su unión ordenada $\cup_i A_i$ ?

Soluciones

$O(\lg\min\{n_1,n_2,t\})$k = 2 A 1 [ t / 2 ] A 2 [ t / 2 ] A 1 [ t / 2 .. t ] A 2 [ 1 .. t / 2 ] A 1 [ 1 .. t / 2 ] A 2 [ t / 2 .. t ] t / 2 n 1 n 2$k=2$$k=2$$A_1[t/2]$$A_2[t/2]$$A_1[t/2..t]$$A_2[1..t/2]$$A_1[1..t/2]$$A_2[t/2..t]$$t/2$$n_1$$n_2$$t$

Esto se generaliza a un algoritmo un poco más sofisticado que se ejecuta en el tiempo $O(k\lg t)$ para valores mayores de $k$ , basado en el cálculo de la mediana de los valores $A_i[t/k]$ para $i\in[1..k]$ : el $t/k$ elementos más pequeños de t / k pueden ignorarse aún más en las matrices $k/2$ donde $A_i[t/k]$ es más pequeño que la mediana, y los elementos de los rangos en $[t-t/k..]$ pueden ignorarse aún más en $k/2$ otras matrices, lo que resulta en una reducción a la mitad de $t$ en cada recurrencia (y un costo de $O(k)$ para la mediana).

Referencias

Estoy contento con mi (s) solución (es), pero supongo que el problema (y su solución) ya se conocía. Está relacionado con el algoritmo de tiempo lineal para calcular la mediana (al ordenar grupos de tamaño y recurrir a la mediana de sus medios), pero es un poco más general. Le pregunté a varias universidades en Madalgo en Aarhus (Dinamarca), y luego a otras en el taller Stringology (Rouen), sin éxito: espero que alguien más conocedor pueda ayudar en Stack Exchange ...$5$

Motivaciones

Las soluciones a este problema tienen aplicaciones para la Estructura de datos diferidos en matrices (de hecho, puede verse como un operador en una estructura de datos diferidos para la unión de matrices ordenadas); y de una manera más complicada, al cálculo adaptativo de códigos libres de prefijos óptimos.

El algoritmo descrito por Frederickson y Johnson en 1982 considera que todos los conjuntos tienen el mismo tamaño. También describieron en 1980 una solución óptima que aprovecha los diferentes tamaños de los conjuntos ordenados. La complejidad de este algoritmo está dentro de .$O(k + \sum^k_{i=1}\log{n_i})$

Referencia

Greg N. Frederickson y Donald B. Johnson. 1980. Selección y clasificación generalizadas (versión preliminar). En Actas del duodécimo simposio anual de ACM sobre Teoría de la computación (STOC '80). ACM, Nueva York, NY, EE. UU., 420-428. DOI = 10.1145 / 800141.804690 http://doi.acm.org/10.1145/800141.804690

Frederickson y Johnson obtuvieron un resultado óptimo en los años 80. Deje , entonces existe un algoritmo que resuelve su problema en .O ( k + p log $p=\min(k,t)$$O(k+p \log \frac{t}{p})$

Referencia

GN Frederickson, DB Johnson " La complejidad de la selección y clasificación en x + y y matrices con columnas ordenadas " J. Comput. System Sci., 24 (2) (1982), págs. 197–208

El caso k = 2 aparece en un orden de fusión en paralelo, ya que la fusión de dos matrices ordenadas de diferentes subprocesos debe dividirse entre dos subprocesos para mantener la misma cantidad de paralelismo. Esta solución de tarea es una referencia.