Auswahl in Vereinigung von sortierten Arrays: Bereits bekannt?

Ich suche bibliografische Referenzen für den folgenden Algorithmus / das folgende Problem: Ich habe es "BiSelect" oder "t-ary Select" oder "Select in Union of Sorted Arrays" genannt, aber ich denke, es wurde zuvor unter einem anderen Namen eingeführt?

Problem

Betrachten Sie das folgende Problem:

Gegeben $k$ disjunkt sortierten Arrays $A_1,\ldots, A_k$ , die jeweiligen Größen $n_1,\ldots,n_k$ , und eine ganze Zahl $t\in[1..\sum n_i]$ , was das ist $t$ - ten Wert ihrer sortierten Vereinigung $\cup_i A_i$ ?

Lösungen

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 $O(\lg\min\{n_1,n_2,t\})$$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$

Dies verallgemeinert sich auf einen etwas komplexeren Algorithmus, der in der Zeit für größere Werte von läuft , basierend auf der Berechnung des Medians der Werte für : the kleinste Elemente können in den Arrays weiter ignoriert werden, wobei kleiner als der Median ist, und die Elemente von Rängen in können in weiter ignoriert werden andere Arrays, was zu einer Halbierung von bei jeder Wiederholung führt (und zu Kosten von für den Median).$O(k\lg t)$$k$$A_i[t/k]$$i\in[1..k]$$t/k$$k/2$$A_i[t/k]$$[t-t/k..]$$k/2$$t$$O(k)$

Verweise?

Ich bin mit meinen Lösungen zufrieden, aber ich nehme an, dass das Problem (und seine Lösung) bereits bekannt war. Es ist verwandt mit dem linearen Zeitalgorithmus zur Berechnung des Medians (durch Sortieren von Gruppen der Größe und Rückgriff auf den Median ihrer Mitten), ist jedoch etwas allgemeiner. Ich habe mehrere Colleges bei Madalgo in Aarhus (Dänemark) und einige andere beim Workshop Stringology (Rouen) erfolglos befragt: Ich hoffe, dass jemand, der sich besser auskennt, bei Stack Exchange helfen kann ...$5$

Motivationen

Lösungen für dieses Problem haben Anwendungen für die verzögerte Datenstruktur auf Arrays (in der Tat kann dies als Operator in einer verzögerten Datenstruktur für die Vereinigung sortierter Arrays angesehen werden). und auf eine kompliziertere Art und Weise zur adaptiven Berechnung von freien Codes mit optimalen Präfixen.

Der von Frederickson und Johnson 1982 beschriebene Algorithmus geht davon aus, dass alle Mengen die gleiche Größe haben. Sie beschrieben 1980 auch eine optimale Lösung, die die unterschiedlichen Größen der sortierten Sätze ausnutzt. Die Komplexität dieses Algorithmus liegt innerhalb von .$O(k + \sum^k_{i=1}\log{n_i})$

Referenz

Greg N. Frederickson und Donald B. Johnson. 1980. Allgemeine Auswahl und Rangfolge (Vorläufige Fassung). In Proceedings des zwölften jährlichen ACM-Symposiums für Computertheorie (STOC '80). ACM, New York, NY, USA, 420-428. DOI = 10.1145 / 800141.804690 http://doi.acm.org/10.1145/800141.804690

Frederickson und Johnson erzielten in den 80er Jahren ein optimales Ergebnis. Sei , dann existiert ein Algorithmus, der dein Problem in O löst$p=\min(k,t)$.$O(k+p \log \frac{t}{p})$

Referenz

GN Frederickson, DB Johnson " Die Komplexität der Auswahl und Rangfolge in x + y und Matrizen mit sortierten Spalten " J. Comput. System Sci., 24 (2) (1982), S. 197–208

Der Fall k = 2 tritt bei der parallelen Zusammenführungssortierung auf, da das Zusammenführen von zwei sortierten Arrays aus verschiedenen Threads auf zwei Threads aufgeteilt werden muss, um das gleiche Maß an Parallelität aufrechtzuerhalten. Diese Hausaufgabenlösung ist eine Referenz.