Processing sets of frequent itemset queries

This dissertation is devoted to frequent itemset mining regarded as advanced database querying where users specify the source dataset, the minimum frequency threshold, and optionally pattern constraints narrowing the results, and it is up to the data mining system to execute the mining task as efficiently as possible. Building upon existing solutions optimizing the execution of individual queries or sequences of queries, we bring frequent itemset query optimization to another level and consider the problem of efficient processing of sets of frequent itemset queries, analogous to multi-query optimization in database systems. Our solutions target mainly batch processing mode but can be applied to multi-user interactive environments as well.
In this dissertation we formulate the problem of processing sets of frequent itemset queries in the context of a simple, general model of frequent itemset queries independent of particular languages and interfaces, and provide several solutions addressing the problem. The majority of the developed techniques are defined in terms of a data sharing model based on the concept of elementary data selection predicates which represent parts of the dataset shared among the queries. The developed methods of processing sets of frequent itemset queries can be broadly classified into two categories: methods independent of a particular frequent itemset mining algorithm, and the ones designed with a specific algorithm in mind. The explicitly addressed frequent itemset mining algorithms are: Apriori, FP-growth, and Partition, which we claim belong to the most influential ones, and in addition are important from the point of view of possible practical applications. All the proposed techniques are initially formulated and experimentally verified under the assumption that data partitions corresponding to elementary data selection predicates can be selectively retrieved from the database. Afterwards, theoretical and experimental analysis of the influence of available access paths to data on the proposed techniques is conducted.
An important contribution of the dissertation is related to the identified optimization problem occurring in one of the techniques for the Apriori algorithm. The problem concerns handling large batches of queries żeby dividing the set of queries into subsets executed independently. For the problem formulated as a particular case of hypergraph partitioning, its NP-hardness is proved and several heuristic solutions are provided. Rozprawa jest poświęcona problemowi odkrywania zbiorów częstych przez tzw. Zapytania eksploracyjne stanowiące specyfikację zbioru informacji źródłowych, wymaganej niewiele znaczącej częstości występowania, a także opcjonalnie ograniczeń nakładanych na odkrywane wzorce. Opierając się na istniejących rozwiązaniach w zakresie optymalizacji wykonania pojedynczych zapytań eksploracyjnych i sekwencji takich zapytań, w rozprawie przeniesiono optymalizację zapytań eksploracyjnych dotyczących problemu odkrywania zbiorów częstych na nowy poziom, koncentrując się na optymalizacji wykonania zbiorów zapytań eksploracyjnych, stanowiącej koncepcyjne nawiązanie do optymalizacji zbiorów zapytań w systemach baz informacji. Proponowane rozwiązania odnoszą się z reguły do systemów eksploracji informacji przetwarzających zadania w trybie wsadowym, lecz mogą znaleźć użycie także w systemach wielodostępnych, obsługujących mnóstwo współbieżnych sesji interaktywnych.
W rozprawie sformułowano problem przetwarzania zbiorów zapytań eksploracyjnych w kontekście prostego, ogólnego modelu zapytań dotyczącego problemu odkrywania zbiorów częstych, niezależnego od konkretnych języków oraz interfejsów użytkowanych w eksploracji danych, i zaproponowano szereg rozwiązań postawionego problemu. Większość opracowanych technik odnosi się do zaproponowanego modelu współdzielenia informacji poprzez zapytania eksploracyjne, opartego na rozłącznych formułach selekcji reprezentujących podzbiory zbioru informacji współdzielone przez zapytania. Przedstawione w rozprawie metody przetwarzania zbiorów zapytań eksploracyjnych dotyczących problemu odkrywania zbiorów częstych można ogólnie podzielić na dwie kategorie: metody niezależne od solidnego algorytmu odkrywania zbiorów częstych, a także te zaprojektowane z myślą o potężnym algorytmie. Specyficzne metody wykonania zbiorów zapytań zostały opracowane dla algorytmów Apriori, FP-growth i Partition, które należą do najistotniej znaczących algorytmów odkrywania zbiorów częstych i jednocześnie są wyraźne z punktu widzenia potencjalnych zastosowań. Wszystkie zaproponowane techniki zostały najpierw sformułowane i eksperymentalnie zweryfikowane przy założeniu, że partycje informacji odpowiadające rozłącznym formułom selekcji mogą być selektywnie odczytane z bazy danych. Następnie przeprowadzono teoretyczną i eksperymentalną analizę wpływu ścieżek dostępu do informacji na ich skuteczność.
Ważnym elementem rozprawy jest zidentyfikowany problem optymalizacyjny, występujący w jednej z technik zaproponowanych dla algorytmu Apriori. Problem ten dotyczy obsługi wielkich zbiorów zapytań eksploracyjnych poprzez ich podział na niezależnie realizowane podzbiory. Problem został sformułowany jako szczególny przypadek partycjonowania hipergrafu, udowodniono jego NP-trudność oraz opracowano dla niego kilka heurystyk.