Lucenes Algorithmus

Question

Ich las das Papier von Doug Cutting; "Space optimizations for total ranking".

Da es vor langer Zeit geschrieben wurde, frage ich mich, welche Algorithmen Lucene verwendet (in Bezug auf Buchung Liste Traversal und Score-Berechnung, Ranking).

Insbesondere der gesamte Rangordnungsalgorithmus, der dort beschrieben wird, umfaßt das Durchlaufen der gesamten Buchungsliste für jeden Abfragebegriff, so daß im Falle sehr häufiger Abfragebegriffe wie "gelber Hund" jeder der 2 Begriffe sehr sehr lange Buchungen haben kann Liste im Falle der Websuche. Sind sie alle in der aktuellen Lucene/Solr wirklich durchquert? Oder gibt es irgendwelche Heuristiken, um die verwendete Liste zu kürzen?

In dem Fall, wenn nur die Top-k-Ergebnisse zurückgegeben werden, kann ich verstehen, dass die Verteilung Liste auf mehrere Maschinen verteilen, und dann die Top-k von jedem kombinieren würde funktionieren, aber wenn wir "100 Ergebnisseite ", dh die Ergebnisse werden von 990-1000 gewertet, dann müsste jede Partition immer noch die Top 1000 herausfinden, also würde Partitionierung nicht viel helfen.

Gibt es eine aktuelle detaillierte Dokumentation zu den von Lucene verwendeten internen Algorithmen?

Answer 1

Mir ist eine solche Dokumentation nicht bekannt, aber seit Lucene Open Source ist, ermutige ich Sie, den Quellcode zu lesen. Insbesondere enthält die aktuelle Trunk-Version flexible indexing, was bedeutet, dass die Speicher- und Buchungslisten-Traversierung vom Rest des Codes entkoppelt wurde, sodass benutzerdefinierte Codecs geschrieben werden können.

Sie Annahmen bezüglich Einlieferungsliste Traversal korrekt sind, standardmäßig (es hängt von Ihrer Scorer Implementierung) Lucene die gesamte Buchungsliste in der Abfrage für jeden Begriff durchsetz ​​und legt Dokumente in einem Haufen der Größe k Anpassung an die Spitze zu berechnen -k Dokumente (siehe TopDocsCollector). Wenn also Ergebnisse von 990 bis 1000 zurückgegeben werden, erzeugt Lucene einen Heap der Größe 1000. Und wenn Sie Ihren Index nach Dokument partitionieren (ein anderer Ansatz könnte sein, nach Begriffen zu trennen), muss jeder Shard die 1000 besten Ergebnisse an den Server senden verantwortlich für das Zusammenführen von Ergebnissen (siehe z. B. Solr QueryComponent, das eine Abfrage von N nach P> N in mehrere Shard-Anforderungen von 0 nach P sreq.params.set(CommonParams.START, "0"); übersetzt). Aus diesem Grund ist Solr im verteilten Modus möglicherweise langsamer als im Standalone-Modus bei extremem Paging.

Ich weiß nicht, wie Google effizient Ergebnisse erzielt, aber Twitter veröffentlicht eine paper on their retrieval engine Earlybird, wo erklären, wie sie Lucene gepatcht, um eine effiziente umgekehrte chronologische Reihenfolge Traversal der Buchungslisten zu tun, die sie am meisten zurückgeben können aktuelle Tweets, die zu einer Suchanfrage passen, ohne die gesamte Buchungsliste für jeden Begriff zu durchlaufen.

Update: ich diesen presentation von Googler gefunden Jeff Dean, die erklärt, wie Google die großangelegte Informationsabrufsystem aufgebaut. Insbesondere geht es um Sharding-Strategien und die Kodierung von Posting-Listen.