Lucene ' s Algorithmus
Ich lese die Zeitung von Doug Cutting; "Raum-Optimierungen für die Gesamtwertung".
Da war es vor langer Zeit geschrieben, Frage ich mich, welche algorithmen lucene verwendet (Bezug auf postings list traversal-und score-Berechnung, ranking).
Insbesondere, die gesamten ranking-Algorithmus beschrieben, beinhaltet die Traversierung entlang der gesamten postings-Liste für jeden Suchbegriff an, damit im Falle von sehr Allgemeine Suchbegriffe wie "gelbe Hund", eine der 2 Bedingungen haben kann, einen sehr, sehr langen postings-Liste bei der web-Suche. Sind Sie alle wirklich Durchlaufen in der aktuellen Lucene/Solr? Oder gibt es irgendwelche Heuristiken zum abschneiden der Liste angestellt?
In dem Fall, wenn nur die top-k Ergebnisse werden zurückgegeben, ich kann verstehen, dass die Verteilung der Buchungen-Liste auf mehreren Rechnern, und dann die Kombination der top-k aus jeder funktionieren würde, aber wenn wir verpflichtet sind, die Rückkehr "zum 100 - - Ergebnis-Seite", d.h. die Ergebnisse in einer Rangfolge von 990--1000, dann jede partition müsste noch die top 1000, also
partitionieren würde nicht viel helfen.
Insgesamt ist es up-to-date ausführliche Dokumentation der internen algorithmen, die Verwendung von Lucene?
- zusätzlich, jemand weiß, rund (natürlich die details sind geheim, aber ich denke, die wichtigsten Ideen werden sollten, Häufig genug in diesen Tagen), wie google funktioniert schnell ranking in Fällen von multi-term-Abfragen mit UND ? (wenn Ihre postings sind sortiert nach PageRank bestellen, dann ist es verständlich, dass ein einzelner Begriff-Abfrage würde schnell wieder die top-k, aber wenn es multi-Begriff, hätten Sie Durchlaufen die ganze Listen zu finden, die insersection gesetzt, denn die Listen sind nicht sortiert nach docId, wie in der Lucene-Papier-Fall)
- Ich weiß nicht, wie das tatsächlich funktioniert, aber wenn Sie wollen, um früh-Abfrage Kündigung, sollten Sie die index-Reihenfolge (doc-ids) übereinstimmen, die Relevanz (pagerank in Ihrem Fall), um zumindest auf der pro-segment-basis. Dies würde Ihr problem lösen, für multi-Begriff Abfragen.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich bin mir nicht bewusst, wie Dokumentation, aber da Lucene ist open-source, ich ermutige Sie, gehen Sie Lesen den Quellcode. Insbesondere die aktuelle trunk-version enthält flexible Indizierung, was bedeutet, dass die Speicherung und Veröffentlichung der Liste-traversal wurde abgekoppelt vom rest des Codes, wodurch es möglich ist, schreiben Sie benutzerdefinierte codecs.
Sie Annahmen richtig sind, bezüglich der posting-Liste-traversal standardmäßig (es hängt von Ihrem Torschütze Umsetzung) Lucene durchläuft die gesamte posting-Liste für jeden Begriff vorhanden in der Abfrage und legt übereinstimmenden Dokumente, die in einem heap der Größe k zur Berechnung der top-k Dokumente (siehe TopDocsCollector). Also die Rückgabe von 990 bis 1000 macht Lucene instanziieren Sie ein heap der Größe 1000. Und wenn Sie partition Ihrer index-Dokument (ein anderer Ansatz könnte sein, die durch split-term), jeder Splitter benötigen, senden die top 1000 Ergebnisse an den server, der verantwortlich ist für die Zusammenführung der Ergebnisse (siehe Solr QueryComponent zum Beispiel, was gleichbedeutend ist mit einer Abfrage von N zu P>N mehrere Splitter Anfragen von 0 bis P
sreq.params.set(CommonParams.START, "0");). Dies ist der Grund, warum Solr könnte langsamer im verteilten Modus als standalone-Modus-bei extrem paging.Ich weiß nicht, wie Google gelingt Ergebnisse effizient, aber Twitter veröffentlicht Papier auf die retrieval-engine Earlybird, wo Sie erklären, wie Sie gepatcht Lucene um eine effiziente umgekehrter chronologischer Reihenfolge Durchlaufen der posting-Listen, die Ihnen erlaubt, zurückzukehren die aktuellsten tweets die Anpassung einer Abfrage ohne das Durchlaufen der gesamten posting-Liste für jeden Begriff.
Update:
Ich fand diese Präsentation von Googler Jeff Dean, die erklärt, wie Google aufgebaut, large scale information-retrieval-system. Insbesondere, er spricht über Splitter-Strategien und-Buchung-Liste-Codierung.