Wyniki wyszukiwania - BazTech

1

Checking Sets of Pure Evolving Association Rules

Combi Carlo, Rizzi Romeo, Sala Pietro

Fundamenta Informaticae

|

2021

|

Vol. 178, nr 4

283--313

EN

Extracting association rules from large datasets has been widely studied in many variants in the last two decades; they allow to extract relations between values that occur more “often” in a database. With temporal association rules the concept has been declined to temporal databases. In this context the “most frequent” patterns of evolution of one or more attribute values are extracted. In the temporal setting, especially where the interference betweeen temporal patterns cannot be neglected (e.g., in medical domains), there may be the case that we are looking for a set of temporal association rules for which a “significant” portion of the original database represents a consistent model for all of them. In this work, we introduce a simple and intuitive form for temporal association rules, called pure evolving association rules (PE-ARs for short), and we study the complexity of checking a set of PE-ARs over an instance of a temporal relation under approximation (i.e., a percentage of tuples that may be deleted from the original relation). As a by-product of our study we address the complexity class for a general problem on Directed Acyclic Graphs which is theoretically interesting per se.

2

Złożoność danych pomiarowych i metody jej określania

Czajka A., Polak A.

Przegląd Elektrotechniczny

|

2010

|

R. 86, nr 9

9-12

PL

W referacie przedstawiono problematykę określania złożoności danych pomiarowych oraz przegląd pewnej klasy algorytmów wyznaczających złożoność. Omówiono złożoność Kołmogorowa, entropię Shannona oraz entropię próbek. Celem przeprowadzonych prac była analiza wybranych algorytmów zastosowanych do określania złożoności sygnałów generowanych przez coraz bardziej złożony system. Badania miały charakter eksperymentów symulacyjnych. Ich wyniki pokazują, że miara złożoności danych generowanych przez badany system może być powiązana ze złożonością jego struktury i procesów zachodzących w samym systemie. Jest to krok wstępny do opracowania metody monitorowania zmian zachodzących w systemach złożonych poprzez oceny złożoności generowanych przez nie sygnałów. Do systemów takich należy m.in. układ oddechowy monitorowany podczas bezdechu sennego.

EN

In this paper the problem of assessment of measurement data complexity is presented together with a review of a certain class of algorithms for complexity calculation. The Kolmogorov complexity, Shannon entropy and sample entropy are discussed. The aim of this work was to analyse the chosen algorithms used in the assessment of complexity of signals generated by a more and more complex system. The investigations were performed as simulation experiments. Their results show that the measure of complexity of data generated by the system under investigation can be related to the complexity of both the system’s structure and internal processes. This is a preliminary step towards the elaboration of a method for monitoring changes in complex systems by assessment of the complexity of generated by them signals. Such systems include e.g. the respiratory system monitored during sleep apnoea.

3

Foundations of Modal Deductive Databases

Nguyen L.A. L.A.

Fundamenta Informaticae

|

2007

|

Vol. 79, nr 1-2

85-135

EN

We give formulations for modal deductive databases and present a modal query language called MDatalog. We define modal relational algebras and give the seminaive evaluation algorithm, the top-down evaluation algorithm, and the magic-set transformation for MDatalog queries. The results of this paper like soundness and completeness of the top-down evaluation algorithm or correctness of the magic-set transformation are proved for the multimodal logics of belief KDI4s5, KDI45, KD4s5s, KD45(m), KD4Ig5a, and the class of serial context-free grammar logics. We also show that MDatalog has PTIME data complexity in the logics KDI4s5, KDI45, KD4s5s, and KD45(m).