Szybkie Obliczenia na Podsumowaniach Danych – „Infobright’s Approximate Query” oraz Przykłady Algorytmów Eksploracyjnych

Infobright od pewnego czasu opracowuje silnik bazodanowy (o nazwie IAQ) nakierowany na szybkie aproksymacyjne odpowiedzi na kwerendy SQL. Silnik bazuje na idei przechowywania oryginalnych danych jedynie w formie ich zgranulowanych podsumowań (wyrażanych np. poprzez histogramy i najistotniejsze korelacje pomiędzy kolumnami) oraz na wykonywaniu wewnętrznych operacji SQL’owych w formie transformacji tychże podsumowań (przykładowo, wynikiem operacji filtrującej jest uaktualniona reprezentacja histogramowo-korelacyjna danej tabeli, którą silnik może traktować jako wejście do dalszych operacji). Podczas ładowania (a właściwie opisywania) nowych porcji danych, algorytmy zaimplementowane w IAQ optymalizują ich reprezentację pod kątem przewidywanej dokładności późniejszych kwerend. Testy wykonywane przez pierwszych komercyjnych użytkowników IAQ pokazują, iż tak rozumiane aproksymacje mogą być wyliczane bez porównania szybciej niż dokładne wyniki kwerend SQL, z zachowaniem wystarczającego poziomu ich dokładności.  

W ramach niniejszego seminarium – oprócz krótkiego przypomnienia założeń powyższego podejścia – przedstawię przykład alternatywnego wykorzystania produkowanych podsumowań. Przykład ten związany jest z zagadnieniami ekploracji danych, w szczególności z zadaniem selekcji cech. Okazuje się, że w dość łatwy sposób można przeformułować pewne metody selekcji cech w taki sposób, by pracowały one bezpośrednio na omawianych podsumowaniach histogramowo-korelacyjnych, bez konieczności dostępu do oryginalnych danych. Można wręcz uznać, że tego rodzaju wykorzystywanie podsumowań danych (nie tylko w selekcji cech, ale także w przypadku innych zadań związanych z eksploracją danych) jest – obok implementacji kwerend aproksymacyjnych w ramach IAQ – całkiem naturalną gałęzią zastosowań. Algorytmy uczące się z danych bazują bowiem na ogół na wyliczaniu pewnych agregacji bądź heurystycznych funkcji oceny. Proces budowy modeli predykcji czy klasyfikacji na podstawie przybliżonych wartości takich funkcji nie powinien zatem – w efekcie końcowym – odbiegać znacznie od wyników otrzymanych na podstawie bardziej dokładnych (lecz o parę rzędów wolniejszych) obliczeń. W istocie, analiza porównawcza wyników otrzymanych w sposób klasyczny i aproksymacyjny (przeprowadzana, przykładowo, poprzez porównanie rankingów ważności cech otrzymanych obiema technikami) może stać się niezależnym testem jakości produkowanych podsumowań.