Selecione na união de matrizes classificadas: Já sabe?

Estou procurando referências bibliográficas para o seguinte algoritmo / problema: Chamei de "BiSelect" ou "t-ary Select" ou "Selecionar na união de matrizes classificadas", mas acho que foi introduzido anteriormente com outro nome?

Problema

Considere o seguinte problema:

Dado disjuntos ordenada matrizes , dos respectivos tamanhos , e um inteiro , qual é o valor -ésimo de sua união ordenada ?Um 1 , ... , A k n 1 , ... , n k t ∈ [ 1 .. Σ n i ] t ∪ i A $k$$A_1,\ldots, A_k$$n_1,\ldots,n_k$$t\in[1..\sum n_i]$$t$ $\cup_i A_i$

Soluções

Existe um algoritmo muito simples e elegante em execução no tempo se k = 2 : se k = 2 , basta comparar A_1 [t / 2] com A_2 [t / 2] e recorra a A_1 [t / 2..t] e A_2 [1..t / 2] ou A_1 [1..t / 2] e A_2 [t / 2..t] de acordo, nos dois casos com parâmetro t / 2 (e algumas otimizações menores quando n_1 ou n_2 são menores que t ).$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$

Isso generaliza para um algoritmo um pouco mais sofisticado, executando no tempo $O(k\lg t)$ para valores maiores de $k$ , com base no cálculo da mediana dos valores $A_i[t/k]$ para $i\in[1..k]$ : o $t/k$ menores podem ser ignorados ainda mais nas matrizes $k/2$ que $A_i[t/k]$ é menor que a mediana e os elementos das classificações em $[t-t/k..]$ podem ser ignorados ainda mais no $k/2$ outras matrizes, resultando em uma metade de $t$ em cada recorrência (e um custo de $O(k)$ para a mediana).

Referências?

Estou feliz com minhas soluções, mas suponho que o problema (e sua solução) já era conhecido. Está relacionado ao algoritmo de tempo linear para calcular a mediana (classificando grupos de tamanho e recursando na mediana de seus médios), mas é um pouco mais geral. Perguntei a várias faculdades em Madalgo, em Aarhus (Dinamarca), e depois a outras no workshop Stringology (Rouen), sem sucesso: Espero que alguém com mais conhecimento possa ajudar no Stack Exchange ...$5$

Motivações

As soluções para esse problema têm aplicativos para a Estrutura de dados adiados em matrizes (na verdade, pode ser visto como um operador em uma estrutura de dados adiada para a união de matrizes classificadas); e de uma maneira mais complicada, ao cálculo adaptativo dos códigos livres de prefixos ideais.

O algoritmo descrito por Frederickson e Johnson em 1982 considera que todos os conjuntos têm o mesmo tamanho. Eles também descreveram em 1980 uma solução ótima que tira proveito dos diferentes tamanhos dos conjuntos classificados. A complexidade desse algoritmo está dentro de .$O(k + \sum^k_{i=1}\log{n_i})$

Referência

Greg N. Frederickson e Donald B. Johnson. 1980. Seleção e classificação generalizada (Versão Preliminar). Em Anais do décimo segundo simpósio anual da ACM sobre Teoria da Computação (STOC '80). ACM, Nova Iorque, NY, EUA, 420-428. DOI = 10.1145 / 800141.804690 http://doi.acm.org/10.1145/800141.804690

Frederickson e Johnson obtiveram um resultado ótimo nos anos 80. Seja , então existe um algoritmo que resolve seu problema em .O ( k + p log $p=\min(k,t)$$O(k+p \log \frac{t}{p})$

Referência

GN Frederickson, DB Johnson " A complexidade da seleção e classificação em x + y e matrizes com colunas classificadas " J. Comput. System Sci., 24 (2) (1982), pp. 197–208

O caso k = 2 aparece em uma ordem de mesclagem paralela, pois a mesclagem de duas matrizes classificadas de diferentes threads precisa ser dividida entre dois threads para manter a mesma quantidade de paralelismo. Esta solução de lição de casa é uma referência.