Przestrzenne, probabilistyczne struktury danych do pobierania numerów

Question

Uważamy, że mamy algorytm, który odbiera hipotetycznie długi strumień kluczy. Następnie generuje wartość od 0 do 1 dla każdego klucza, podczas jego przetwarzania, w celu pobrania z tyłu. Zestaw wejściowy jest wystarczająco duży, że nie możemy pozwolić sobie na zapisanie jednej wartości dla każdego klucza. Reguła generująca wartości jest niezależna między kluczami.

Teraz załóżmy, że możemy tolerować błąd w tylnej odnośnika, ale chcemy jeszcze zminimalizować Różnica pobierane i oryginalnych wartości (tj asymptotycznie ciągu wielu przypadkowych wyszukiwań).

Na przykład, jeśli pierwotna wartość dla danego klucza wynosiła 0,008, pobieranie 0,06 jest znacznie lepsze niż pobieranie 0.6.

Jakie struktury danych lub algorytmy możemy zastosować, aby rozwiązać ten problem?

Filtry Bloom są najbliższymi strukturami danych, jakie mogę wymyślić. Można skwantyfikować zakres wyjściowy, użyć filtru Blooma dla każdego kubełka i jakoś połączyć ich wyniki w czasie pobierania, aby oszacować najbardziej prawdopodobną wartość. Zanim przejdę do tej ścieżki i wymyślę nowe koło, czy istnieją znane struktury danych, algorytmy, teoretyczne lub praktyczne podejścia do rozwiązania tego problemu?

Idealnie szukam rozwiązania, które może ustawić parametryzować kompromis między przestrzenią i współczynników błędów.

Answer 1

Być może wariant filtru Bloom o nazwie Compact Approximator: jak filtr kwitnący, ale uogólniony, więc wpisy są wartościami z siatki. Ta krata jest tutaj po prostu płynie pomiędzy 0 a 1 (ma więcej struktury niż tylko krata, ale spełnia wymagania) lub jednak przechowuje te liczby.

Aktualizacja zastępuje odpowiednie wpisy przez maksimum między nią a zapamiętaną wartością, zapytanie wylicza minimalną liczbę wszystkich odpowiednich wpisów (przykłady poniżej). Wyniki mogą jedynie zawyżać prawdziwą wartość. Odwracając kolejność (zamieniając min i max i inicjalizując na 1 zamiast 0) można uzyskać niedoszacowanie, razem dając przedział, który zawiera wartość rzeczywistą.

---

Tak na przykład, za pomocą pierwszych przybliżone (przeszacowania), stawiając w szeregu wygląda następująco:

index1 = hash1(key) 
data[index1] = max(data[index1], value); 
index2 = hash2(key) 
data[index2] = max(data[index2], value); 
... etc 

i coraz przeszacowania wygląda następująco:

result = 1 
index1 = hash1(key) 
result = min(data[index1], result); 
index2 = hash2(key) 
result = min(data[index2], result); 
... etc