Mam dużą bazę danych (16M wierszy) zawierającą percepcyjne skróty obrazów.
Chciałbym móc wyszukiwać rzędy, zbijając odległość w rozsądnym czasie.
Obecnie, o ile dobrze rozumiem ten problem, myślę, że najlepszą opcją jest niestandardowa implementacja SP-GiST, która implementuje drzewo BK , ale wydaje się, że to dużo pracy, i wciąż jestem rozmyślany nad praktycznymi szczegóły dotyczące prawidłowego wdrażania indeksu niestandardowego. Obliczanie odległości uderzenia jest wystarczająco łatwe, ale znam C.
Zasadniczo, jakie jest tutaj właściwe podejście? Muszę być w stanie wyszukiwać dopasowania w obrębie określonej odległości edytowania skrótu. Jak rozumiem, odległość Levenshteina z łańcuchami o równej długości jest funkcjonalnie hamująca odległość, więc istnieje co najmniej pewne wsparcie dla tego, czego chcę, chociaż nie ma jasnego sposobu na utworzenie z niego indeksu (pamiętaj, o wartość, o którą pytam zmiany. Nie mogę wstępnie obliczyć odległości od stałej wartości, ponieważ byłoby to przydatne tylko dla tej jednej wartości).
Skróty są obecnie przechowywane jako 64-znakowy ciąg zawierający binarne kodowanie skrótu ASCII (np. „10010101 ...”), ale dość łatwo mogę przekonwertować je na int64. Prawdziwy problem polega na tym, że muszę stosunkowo szybko przesyłać zapytania.
Wydaje się, że można osiągnąć coś zgodnie z tym, czego chcę pg_trgm, ale nie jestem pewien, jak działa mechamizm dopasowywania trygramu (w szczególności, co w rzeczywistości reprezentuje wskaźnik podobieństwa, który zwraca ? coś w rodzaju odległości do edycji).
Wydajność wstawiania nie jest krytyczna (obliczanie wartości skrótu dla każdego wiersza jest bardzo drogie obliczeniowo), więc przede wszystkim zależy mi na wyszukiwaniu.
źródło
Odpowiedzi:
Cóż, poświęciłem chwilę na napisanie niestandardowego rozszerzenia Postgres C i skończyło się na napisaniu opakowania bazy danych Cython, które zachowuje strukturę drzewa BK w pamięci.
Zasadniczo przechowuje w pamięci kopię wartości phash z bazy danych, a wszystkie aktualizacje bazy danych są odtwarzane w drzewie BK.
Wszystko jest tutaj na githubie . Ma również wiele testów jednostkowych.
Zapytanie w zbiorze danych zawierającym 10 milionów wartości skrótu dla elementów o odległości 4 powoduje dotknięcie ~ 0,25% -0,5% wartości w drzewie i zajmuje ~ 100 ms.
źródło
MOAR ODPOWIEDZI!
Ok, w końcu poświęciłem czas na napisanie niestandardowego rozszerzenia do indeksowania PostgreSQL. Użyłem interfejsu SP-GIST .
Było to dość trudne, głównie dlatego, że Posgres jest duży .
W każdym razie, jak zwykle, jest tutaj na github .
Pod względem wydajności jest obecnie ~ 2-3 razy wolniejsza niż implementacja czysta w pamięci w mojej innej odpowiedzi na to pytanie, ale jest o wiele wygodniejsza w użyciu Z przyjemnością zjem ten hit wydajności (realistycznie, to ~ 50 ms / zapytanie - 150 ms / zapytanie, które wciąż jest dość małe).
źródło