Algorytm Lucene'a

Question

Czytam artykuł Douga Cutting; "Space optimizations for total ranking".

Odkąd został napisany dawno temu, zastanawiam się, jakich algorytmów używa lucene (w odniesieniu do przechodzenia listy wpisów i obliczania wyniku, rankingu).

W szczególności, opisany tam algorytm klasyfikacji całkowitej obejmuje przechodzenie przez całą listę księgowań dla każdego zapytania, więc w przypadku bardzo popularnych terminów zapytań, takich jak "żółty pies", jedno z dwóch terminów może mieć bardzo długie posty lista w przypadku wyszukiwania w Internecie. Czy naprawdę są oni obecni w Lucene/Solr? Czy są jakieś heurystyki do skracania listy?

W przypadku, gdy zwracane są tylko najwyższe wyniki k, rozumiem, że dystrybucja listy księgowań na wielu komputerach, a następnie łączenie najwyższego k z każdego z nich zadziała, ale jeśli będziemy musieli zwrócić "setną strona wyników ", czyli wyniki w rankingu od 990-1000th, wtedy każda partycja będzie musiała jeszcze znaleźć top 1000, więc partycja niewiele by pomogła.

Czy istnieje jakaś szczegółowa dokumentacja dotycząca wewnętrznych algorytmów używanych przez Lucene?

Answer 1

Nie znam takiej dokumentacji, ale skoro Lucene jest open-source, zachęcam do przeczytania kodu źródłowego. W szczególności bieżąca wersja magistrali zawiera flexible indexing, co oznacza, że ​​przechodzenie listy przechowywania i publikowania zostało odłączone od reszty kodu, co umożliwia pisanie niestandardowych koderów-dekoderów.

Twoje założenia są poprawne, jeśli chodzi o zaksięgowanie przeniesienia listy, domyślnie (zależy to od implementacji Scorer). Lucene przegląda całą listę księgowań dla każdego terminu obecnego w zapytaniu i umieszcza pasujące dokumenty w stercie o rozmiarze k, aby obliczyć szczyt -k docs (patrz TopDocsCollector). Powracające wyniki od 990 do 1000 powodują, że Lucene tworzy instancję o wielkości 1000. Jeśli podzielisz indeks według dokumentu (inne podejście może być podzielone według terminu), każdy fragment będzie musiał wysłać najlepsze 1000 wyników do serwera, który jest odpowiedzialny za łączenie wyników (patrz np. Solr QueryComponent, który tłumaczy zapytanie z N na P> N na kilka żądań od 0 do P sreq.params.set(CommonParams.START, "0");). Dlatego Solr może działać wolniej w trybie rozproszonym niż w trybie autonomicznym w przypadku ekstremalnego stronicowania.

Nie wiem, jak Google udaje się skutecznie oceniać wyniki, ale Twitter opublikował numer paper on their retrieval engine Earlybird, w którym wyjaśnił, w jaki sposób załatał Lucene, aby wykonać odwrotną kolejność chronologicznych list, co pozwala im zwrócić najwięcej ostatnie tweety pasujące do zapytania bez przechodzenia przez całą listę księgowań dla każdego terminu.

Aktualizacja: Znalazłem presentation z Googler Jeff Dean, która wyjaśnia, jak Google zbudował swój system pobierania informacji dużą skalę. W szczególności mówi o strategiach shardowania i kodowaniu list.