Fundamenta Informaticae - Volume 135, issue 4

Authors: Przymus, Piotr | Kaczmarski, Krzysztof | Stencel, Krzysztof

Article Type: Research Article

Abstract: Graphics Processing Units (GPU) have significantly more applications than just rendering images. They are also used in general-purpose computing to solve problems that can benefit from massive parallel processing. However, there are tasks that either hardly suit GPU or fit GPU only partially. The latter class is the focus of this paper. We elaborate on hybrid CPU/GPU computation and build optimization methods that seek the equilibrium between these two computation platforms. The method is based on heuristic search for bi-objective Pareto optimal execution plans in presence of multiple concurrent queries. The underlying model mimics the commodity market where devices are …producers and queries are consumers. The value of resources of computing devices is controlled by supply-and-demand laws. Our model of the optimization criteria allows finding solutions of problems not yet addressed in heterogeneous query processing. Furthermore, it also offers lower time complexity and higher accuracy than other methods. Show more

Keywords: heterogeneous environment, GPU, CUDA, query processing

DOI: 10.3233/FI-2014-1136

Citation: Fundamenta Informaticae, vol. 135, no. 4, pp. 483-501, 2014

Authors: Suraj, Zbigniew | Grochowalski, Piotr

Article Type: Research Article

Abstract: The aim of this paper is to present a new version of a bibliographic database system - Rough Set Database System (RSDS). The RSDS system, among others, includes bibliographic descriptions of publications on rough set theory and its applications. This system is also an experimental environment for research related to the processing of bibliographic data using the domain knowledge and the related information retrieval.

Keywords: rough sets, data mining, knowledge discovery, pattern recognition, database systems

DOI: 10.3233/FI-2014-1137

Citation: Fundamenta Informaticae, vol. 135, no. 4, pp. 503-519, 2014

Authors: Wagler, Annegret K. | Wegener, Jan-Thierry

Article Type: Research Article

Abstract: The context of this work is the reconstruction of Petri net models for biological systems from experimental data. Such methods aim at generating all network alternatives fitting the given data. For a successful reconstruction, the data need to satisfy two properties: reproducibility and monotonicity. In this paper, we focus on a necessary preprocessing step for a recent reconstruction approach. We test the data for reproducibility, provide a feasibility test to detect cases where the reconstruction from the given data may fail, and provide a strategy to cope with the infeasible cases. After having performed the preprocessing step, it is guaranteed …that the (given or modified) data are appropriate as input for the main reconstruction algorithm. Show more

DOI: 10.3233/FI-2014-1138

Citation: Fundamenta Informaticae, vol. 135, no. 4, pp. 521-535, 2014

Authors: Wiśniewski, Piotr | Stencel, Krzysztof

Article Type: Research Article

Abstract: Analytic database queries are exceptionally time consuming. Decision support systems employ various execution techniques in order to accelerate such queries and reduce their resource consumption. Probably the most important of them consists in materialization of partial results. However, any introduction of derived objects into the database schema increases the cost of software development, since programmers must take care of their usage and synchronization. In this article we consider using partial aggregations materialized in additional tables. The idea is based on the concept of metagranules that represent the information on grouping and used aggregations. Metagranules have a natural partial order that …guides the optimisation process. We present solutions to two problems. Firstly, we assume that a set of stored metagranules is given and we optimize a query. We present a novel query rewriting method to make analytic queries use the information stored in metagranules. We also describe our proof-of-concept implementation of this method and perform an extensive experimental evaluation using databases of the size up to 0:5 TiB and 6 billions rows. Secondly, we assume that a database workload is given and we want to select the optimal set of metagranules to materialize. Although each metagranule accelerates some queries, it also imposes a significant overhead on updates. Therefore, we propose a cost model that includes both benefits for queries and penalties for updates. We experiment with the complete search in the space of sets of metagranules to find the optimum. Finally, we empirically verify identified optimal sets against database instances up to 0:5 TiB with billions of rows and hundreds millions of aggregated rows. Show more

DOI: 10.3233/FI-2014-1139

Citation: Fundamenta Informaticae, vol. 135, no. 4, pp. 537-551, 2014

Authors: Woźna-Szcześniak, Bożena | Zbrzezny, Andrzej

Article Type: Research Article

Abstract: We investigate a SAT-based bounded model checking (BMC) method for MTL (metric temporal logic) that is interpreted over linear discrete infinite time models generated by discrete timed automata. In particular, we translate the existential model checking problem for MTL to the existential model checking problem for a variant of linear temporal logic (called HLTL), and we provide a SAT-based BMC technique for HLTL. We show how to implement the BMC technique for HLTL and discrete timed automata, and as a case study we apply the technique in the analysis of GTPP, a Generic Timed Pipeline Paradigm modelled by a network …of discrete timed automata. Show more

DOI: 10.3233/FI-2014-1140

Citation: Fundamenta Informaticae, vol. 135, no. 4, pp. 553-568, 2014

Article Type: Other

Citation: Fundamenta Informaticae, vol. 135, no. 4, pp. 569-570, 2014