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 by 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 poprzez tzw. Zapytania eksploracyjne stanowiące specyfikację zbioru danych źródłowych, wymaganej drobnej częstości występowania i 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 danych. Proponowane rozwiązania odnoszą się przeważnie 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 dużo 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 stosowanych w eksploracji informacji, i zaproponowano szereg rozwiązań postawionego problemu. Większość opracowanych technik odnosi się do zaproponowanego modelu współdzielenia danych przez zapytania eksploracyjne, opartego na rozłącznych formułach selekcji reprezentujących podzbiory zbioru informacji współdzielone poprzez 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 potężnego algorytmu odkrywania zbiorów częstych oraz te zaprojektowane z myślą o konkretnym algorytmie. Niepowtarzalne metody wykonania zbiorów zapytań zostały opracowane dla algorytmów Apriori, FP-growth i Partition, które należą do najmocniej znaczących algorytmów odkrywania zbiorów częstych i jednocześnie są widoczne 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 informacji. 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 sporych zbiorów zapytań eksploracyjnych przez ich podział na niezależnie wykonywane podzbiory. Problem został sformułowany jako szczególny przypadek partycjonowania hipergrafu, udowodniono jego NP-trudność oraz opracowano dla niego kilka heurystyk.
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 by 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 poprzez tzw. Zapytania eksploracyjne stanowiące specyfikację zbioru danych źródłowych, wymaganej drobnej częstości występowania i 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 danych. Proponowane rozwiązania odnoszą się przeważnie 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 dużo 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 stosowanych w eksploracji informacji, i zaproponowano szereg rozwiązań postawionego problemu. Większość opracowanych technik odnosi się do zaproponowanego modelu współdzielenia danych przez zapytania eksploracyjne, opartego na rozłącznych formułach selekcji reprezentujących podzbiory zbioru informacji współdzielone poprzez 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 potężnego algorytmu odkrywania zbiorów częstych oraz te zaprojektowane z myślą o konkretnym algorytmie. Niepowtarzalne metody wykonania zbiorów zapytań zostały opracowane dla algorytmów Apriori, FP-growth i Partition, które należą do najmocniej znaczących algorytmów odkrywania zbiorów częstych i jednocześnie są widoczne 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 informacji. 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 sporych zbiorów zapytań eksploracyjnych przez ich podział na niezależnie wykonywane podzbiory. Problem został sformułowany jako szczególny przypadek partycjonowania hipergrafu, udowodniono jego NP-trudność oraz opracowano dla niego kilka heurystyk.
