Znajdź górny adres URL odwiedzin z ostatniego dnia, ostatniej godziny lub ostatniej minuty?

Question

Pierwotnym pytaniem jest plik zawierający 5 GB URL odwiedzany w ostatnim dniu, znajdź najczęstszy częsty URL. Problem można rozwiązać, używając mapy skrótów, aby policzyć wystąpienia odrębnego adresu URL i znaleźć najlepsze k za pomocą min sterty, przyjmując czas O (n log k).

Teraz zastanawiam się, co jeśli dane wejściowe były nieograniczonym strumieniem danych online (zamiast pliku statycznego), to skąd mogę wiedzieć, jaki jest najwyższy adres URL ostatniego dnia?

Czy jest jakaś poprawa, którą mogę wprowadzić do systemu, który pozwala mi dynamicznie uzyskać górny adres URL k ostatniej minuty i ostatniego dnia i ostatniej godziny?

Każda wskazówka zostanie doceniona !!

Answer 1

Jeśli chcesz zgodzić się na probabilistyczną odpowiedź, która może zawierać kilka błędnych wpisów, zdecydowanie powinieneś zajrzeć do struktury danych. Został specjalnie zaprojektowany do oszacowania częstych elementów w strumieniu przy użyciu jak najmniejszej ilości pamięci, a większość implementacji obsługuje bardzo wydajne czasowo i przestrzennie aproksymowanie najlepszych elementów k ze strumienia. Co więcej, struktura pozwala dostosować wykorzystanie przestrzeni, co czyni ją idealną do takich sytuacji. IIRC Google używa tego do określenia najczęstszych zapytań.

Dostępne jest several implementations of this data structure dostępne online.

Mam nadzieję, że to pomoże!