Processing sets of frequent itemset queries
25,81 zł
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 minimalnej częstości występowania oraz opcjonalnie ograniczeń nakładanych na odkrywane wzorce. Opierając się na istniejących rozwiązaniach w zakresie optymalizacji wykonania pojedynczych zapytań eksploracyjnych oraz 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ę głównie do systemów eksploracji danych przetwarzających zadania w trybie wsadowym, ale mogą znaleźć zastosowanie również w systemach wielodostępnych, obsługujących wiele 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 wykorzystywanych w eksploracji danych, 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 danych 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 konkretnego algorytmu odkrywania zbiorów częstych oraz te zaprojektowane z myślą o konkretnym algorytmie. Specyficzne metody wykonania zbiorów zapytań zostały opracowane dla algorytmów Apriori, FP-growth i Partition, które należą do najbardziej znaczących algorytmów odkrywania zbiorów częstych i jednocześnie są istotne z punktu widzenia potencjalnych zastosowań. Wszystkie zaproponowane techniki zostały najpierw sformułowane i eksperymentalnie zweryfikowane przy założeniu, że partycje danych 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 danych na ich wydajność.
Ważnym elementem rozprawy jest zidentyfikowany problem optymalizacyjny, występujący w jednej z technik zaproponowanych dla algorytmu Apriori. Problem ten dotyczy obsługi dużych zbiorów zapytań eksploracyjnych poprzez ich podział na niezależnie wykonywane podzbiory. Problem został sformułowany jako szczególny przypadek partycjonowania hipergrafu, udowodniono jego NP-trudność, a także 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 minimalnej częstości występowania oraz opcjonalnie ograniczeń nakładanych na odkrywane wzorce. Opierając się na istniejących rozwiązaniach w zakresie optymalizacji wykonania pojedynczych zapytań eksploracyjnych oraz 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ę głównie do systemów eksploracji danych przetwarzających zadania w trybie wsadowym, ale mogą znaleźć zastosowanie również w systemach wielodostępnych, obsługujących wiele 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 wykorzystywanych w eksploracji danych, 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 danych 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 konkretnego algorytmu odkrywania zbiorów częstych oraz te zaprojektowane z myślą o konkretnym algorytmie. Specyficzne metody wykonania zbiorów zapytań zostały opracowane dla algorytmów Apriori, FP-growth i Partition, które należą do najbardziej znaczących algorytmów odkrywania zbiorów częstych i jednocześnie są istotne z punktu widzenia potencjalnych zastosowań. Wszystkie zaproponowane techniki zostały najpierw sformułowane i eksperymentalnie zweryfikowane przy założeniu, że partycje danych 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 danych na ich wydajność.
Ważnym elementem rozprawy jest zidentyfikowany problem optymalizacyjny, występujący w jednej z technik zaproponowanych dla algorytmu Apriori. Problem ten dotyczy obsługi dużych zbiorów zapytań eksploracyjnych poprzez ich podział na niezależnie wykonywane podzbiory. Problem został sformułowany jako szczególny przypadek partycjonowania hipergrafu, udowodniono jego NP-trudność, a także opracowano dla niego kilka heurystyk.
Zobacz także te ebooki
