Die Suche nach Sätzen, die spezifische Untergruppen haben

https://stackoverflow.com/questions/494502

20-08-2019
|

Frage

Ich bin ein Student der Physik und arbeite ich einige Code auf das Schreiben mehrere hundert Gigabyte an Daten zu sortieren und Scheiben, die Daten zurückgeben, wenn ich danach fragen. Hier ist der Trick, ich keine gute Methode kennen, Sortier- und Suchdaten dieser Art.

Meine Daten bestehen im wesentlichen aus einer großen Anzahl von Sätzen von Zahlen. Diese Sätze können überall von 1 bis n Zahlen in sie enthalten (obwohl in 99,9% der Mengen, n kleiner als 15) und gibt es etwa 1,5 bis 2 Milliarden dieser Sätze (leider diese Größe steht eine Brute-Force-Methode).

Ich brauche einen Satz mit k Elementen angeben zu können und habe mir jeden Satz mit k + 1 Elementen oder mehr, die die angegebene Teilmenge enthalten zurückgegeben.

Einfaches Beispiel:
Angenommen, ich habe folgende Sätze für meine Daten:
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

Wenn ich die Anfrage geben (1,3) Ich würde die Sätze hat: (1,2,3), (1,2,3,4,5) und (1,3,8,9).
Der Antrag (11) zurückkehren würde den Satz:. (5,8,11)
Der Antrag (1,2,3) würde die Sätze zurück: (1,2,3) und (1,2,3,4,5)
Die Anforderung (50) würde keine Mengen zurückgeben:

Nun sollte das Muster klar sein. Der wesentliche Unterschied zwischen diesem Beispiel und meine Daten ist, dass die Sätze withn meine Daten größer sind, die Zahlen für jedes Element der Sätze 0-16.383 (14 Bits) Lauf verwendet, und es gibt viele, viele viele mehr Sätze.

Wenn es darauf ankommt ich dieses Programm in C ++ schreibe obwohl ich weiß auch, Java, C, eine Versammlung, einige Fortran, und einige Perl.

Hat jemand irgendwelche Hinweise darauf, wie diese abziehen?

edit:
Um ein paar Fragen zu beantworten und ein paar Punkte hinzufügen:

1.) Die Daten ändert sich nicht. Es war alles in einer langen Reihe von Läufen genommen (jeweils unterteilt in 2 Gig-Dateien).

2.) Wie für Stauraum. Die Rohdaten dauert etwa 250 Gigabyte. Ich schätze, dass nach der Verarbeitung und eine Menge von Fremd Metadaten Abstreifen, die ich in Ich bin nicht daran interessiert, dass könnte abreißen, um überall von 36 bis 48 Gigabyte je nachdem, wie viel Metadaten ich entscheiden (ohne Indizes) zu halten. Außerdem, wenn in meiner anfänglichen Verarbeitung der Daten, die mir genug Sätze begegnen, die gleich sind könnte ich in der Lage sein, die Daten comress noch weiter durch die Zähler für Wiederholungs Ereignisse Hinzufügen anstatt einfach die Ereignisse immer und immer wieder.

3). Jede Zahl in einem Satz verarbeitet tatsächlich enthält mindestens zwei Zahlen 14 Bits für die Daten selbst (detektierte Energie) und 7 Bits für Metadaten (Meldernummer). Also muss ich mindestens drei Bytes pro Nummer.

4.) Mein „obwohl in 99,9% der Mengen, n kleiner als 15“ Kommentar war irreführend. In einem vorläufigen Blick durch einige der Stücke der Daten finde ich, dass ich Sätze, die so viele wie 22 Zahlen enthalten aber der Median 5 Zahlen pro Satz und der Durchschnitt liegt bei 6 Zahlen pro Satz.

5.) Während ich die Idee, einen Index von Zeigern in Dateien wie bin ich ein bisschen misstrauisch, weil für Anfragen mehr als eine Nummer die ich mit der halb langsam Aufgabe links bin (zumindest glaube ich es langsam ist) von die Menge aller Zeiger gemeinsam auf die Listen zu finden, dh die größte gemeinsame Teilmenge für eine bestimmte Anzahl von Sätzen zu finden.

6.) Im Hinblick auf den Ressourcen zur Verfügung zu mir, ich kann ca. 300 Gigs von Raum aufbringen, nachdem ich die Rohdaten auf dem System (der Rest meiner Quote auf diesem System). Das System ist ein Dualprozessor-Server mit 2 Quad Core AMD Opterons und 16 Gigabyte RAM.

7.) Ja 0 kann auftreten, ist es ein Artefakt des Datenerfassungssystems ist, wenn es funktioniert, aber es kann vorkommen.

Lösung 4

Ich habe Methoden vor kurzem entdeckt, dass die multidimensionalen Daten zur Karte auf eine einzige Dimension Fass-Kurve verwenden. Man kann dann die Daten-Index auf der Grundlage seines 1D-Index. Bereichsabfragen durch Auffinden der Segmente der Kurve leicht durchgeführt werden kann, dass die Box schneiden, der die Kurve darstellt, und dann diese Segmente abgerufen werden.

Ich glaube, dass diese Methode, weil damit nach Ablauf der wahnsinnigen Indizes wie vorgeschlagen weit überlegen ist es nach einem Blick, würde der Index als Daten so groß sein speichere ich wollte, kaum eine gute Sache. Eine etwas ausführlichere Erklärung hierfür finden Sie unter:

http://www.ddj.com/184410998
und
http://www.dcs.bbk.ac.uk/~jkl/ publikationen.html

Andere Tipps

Ihr Problem ist das gleiche wie die von Suchmaschinen konfrontiert. „Ich habe ein bajillion Dokumente. Ich brauche diejenigen, die diese Gruppe von Wörtern enthalten.“ Sie müssen nur (sehr günstig), ganze Zahlen anstelle von Worten und eher klein Dokumente. Die Lösung ist eine invertierten Index rel="nofollow. Einführung in Information Retrieval von Manning et al (zumin dass Link) kostenlos online verfügbar, ist sehr gut lesbar, und viele Details über geht darüber, wie dies zu tun.

Sie gehen zu müssen, einen Preis in Speicherplatz bezahlen, aber es kann parallelisiert werden, und als schnell mehr sein sollen genug, um Ihre Timing-Anforderungen gerecht zu werden, sobald der Index aufgebaut ist.

eine zufällige Verteilung von 0-16.383 Unter der Annahme, mit einem konsistenten 15 Elementen pro Satz, und zwei Milliarden Sätze würde jedes Element erscheint in etwa 1,8 M-Sets. Haben Sie darüber nachgedacht (und Sie haben die Fähigkeit zu) den Aufbau einer 16384x ~ 1.8M (30B Einträge, 4 Bytes each) Lookup-Tabelle? Bei einer solchen Tabelle können Sie abfragen, welche enthalten Sets (1) und (17) und (5555) und dann finden die Schnittpunkte dieser drei ~ 1.8M-Element-Listen.

Meine Vermutung ist, wie folgt.

Es sei angenommen, dass jeder Satz einen Namen oder eine ID oder Adresse hat (eine 4-Byte-Zahl wird tun, wenn es nur 2 Milliarden von ihnen ist).

Nun gehen durch alle Sätze einmal, und erstellen Sie die folgenden Ausgabedateien:

Eine Datei, die die IDs aller Sätze enthält, die enthalten ‚1‘
Eine Datei, die die IDs aller Sätze enthält, die enthalten ‚2‘
Eine Datei, die die IDs aller Sätze enthält, die enthalten ‚3‘
... etc ...

Wenn es 16 Einträge pro Satz, dann im Durchschnitt jeder dieser 2 ^ 16 Dateien werden die IDs von 2 ^ 20 Sätze enthalten; wobei jede ID 4 Bytes ist, würde dies erfordern, 2 ^ 38 Bytes (256 GB) Speicher.

Sie werden die oben einmal tun, bevor Sie Anfragen verarbeiten.

Wenn Sie Anfragen erhalten, verwenden Sie diese Dateien wie folgt:

Schauen Sie sich ein paar Zahlen in der Anfrage
ein paar von den entsprechenden Indexdateien Öffnen Sie
Holen Sie die Liste aller Sätze, die diese Dateien in beide existieren (es gibt nur eine Million IDs in jeder Datei, so dass diese should't schwierig sein)
Sie, welche von diesen wenigen Sätzen den Rest der Anfrage

Meine Vermutung ist, dass, wenn Sie die oben tun, wird die Erstellung von Indizes (sehr) langsam und Handhabungsanforderungen werden (sehr) schnell sein.

Machen 16383 Index-Dateien, ein für jeden möglichen Suchwert. Für jeden Wert in Ihrem Eingangssatz, schreibt die Datei Position des Beginns des Satzes in die entsprechende Indexdatei. Es ist wichtig, dass jeder der Indexdateien die gleiche Anzahl für den gleichen Satz enthält. Nun hat jede Indexdatei von aufsteigend Indizes in die Master-Datei bestehen wird.

suchen, starten Sie die Index-Dateien lesen zu jedem Suchwert entspricht. Wenn Sie einen Index gelesen, als der Index niedriger ist man aus einer anderen Datei zu lesen, verwerfen und eine anderen lesen. Wenn Sie den gleichen Index von allen Dateien bekommen, das ist ein Spiel - den Satz von der Master-Datei erhalten, und einen neuen Index von jedem der Index-Dateien lesen. Sobald das Ende eines der Index-Dateien erreichen, sind Sie fertig.

Wenn Sie Ihre Werte gleichmäßig verteilt sind, wird jede Indexdatei 1/16383 der Eingangssätze enthält. Wenn Ihr durchschnittlicher Such Satz von 6 Werten besteht, erhalten Sie einen linearen Durchlauf über 6/16383 Ihre ursprüngliche Eingabe tun. Es ist immer noch eine O (n) Lösung, aber Ihre n ist jetzt ein bisschen kleiner.

P. S. Null ist ein unmögliches Ergebnis Wert, oder haben Sie wirklich 1638 4 Möglichkeiten?

spielen gerade Advocatus Diaboli für einen Ansatz, der Brute-Force-+ Indexsuche enthält:

Erstellen Sie einen Index mit der Min-, Max- und keine Elemente von Sätzen.
gelten dann Brute-Force ohne Sätze innerhalb der max min (eingestellt wird gesucht)
In brutalen Gewalt ausschließt auch Sätze ganzes Element Zahl kleiner ist als die des Satzes gesucht.

95% Ihrer Suche würde wirklich brutaler sein, eine sehr kleine Teilmenge zwingt. Nur so ein Gedanke.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow