Wyniki wyszukiwania - BazTech

1

Badanie wydajności elementów bibliotek STL i Qt w przetwarzaniu wie-lowątkowym

Krasowski Piotr, Smołka Jakub

Journal of Computer Sciences Institute

|

2020

|

Vol. 16

247--251

EN

In recent years multithreaded processing has become a important programming aspect. Computers with a multi-core processor are now widely available, enabling the creation of more efficient applications. Many libraries support multi-threaded solutions, but performance information is often lacking. The use of appropriate data structures and algorithms significantly speeds up the process of creation and development of applications. Article describes selected elements of the Qt and STL library and compares their performance in concurrent programming. The test was performed with custom applications created with C++. The time needed to perform individual operations was analysed.

PL

Przetwarzanie wielowątkowe na przestrzeni ostatnich lat stało się ważnym aspektem programistycznym. Komputery dysponujące procesorem wielordzeniowym są obecnie powszechnie dostępne co umożliwia tworzenie wydajniejszych aplikacji. Wiele bibliotek wspiera rozwiązania wielowątkowe lecz często brakuje informacji o wydajności. W artykule opisano wybrane elementy biblioteki Qt i STL oraz porównano ich wydajność w programowaniu współbieżnym. Testy zostały przeprowadzone za pomocą autorskich aplikacji napisanych w języku C++. Wyniki przedstawiono w postaci analizy czasów potrzebnych na wykonanie poszczególnych operacji.

2

The Number of Distinct Subpalindromes in Random Words

Rubinchik M., Shur A. M.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

371--384

EN

We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation,Θ(√n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit limn→∞ E(n, k)=√n does not exist for any κ ≥ 2, lim infn→∞ E(n; k)=√n =Θ(1), and lim supn→∞ E(n; k)=√n = Θ(√k). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.

3

Atomic-key B-trees

Drozdek A., Vujanović D.

Studia Informatica : systems and information technology

|

2015

|

Vol. 1-2(19)

15--26

EN

Atomic-key B-trees are B-trees with keys of different sizes. This note presents two versions of an insertion algorithm and a deletion algorithm for atomic-key B-trees.

4

The efficiency of the A* algorithm’s implementations in selected programming languages

Klimaszewski J.

Journal of Theoretical and Applied Computer Science

|

2014

|

Vol. 8, nr 2

63--71

EN

This article presents results of the experiment, in which data structures, used by the A* algorithm (i.e. priority queue and hash table), were tested. A* algorithm was used to solve 15-puzzle, where puzzle’s state was kept in the 64-bit integer variable. The algorithm used either built-in data structures (such as Python’s dictionary) or provided by a standard library (such as unordered map in the C++ Standard Template Library).

5

Floating Channels Between Communicating Nets

Czaja L.

Fundamenta Informaticae

|

2014

|

Vol. 133, nr 2/3

123--132

EN

A network system is given as a set of Petri net-like structures called agents. Each agent has a singled out place interpreted as a communication port with ingoing edges labelled with send(p1, ..., pn) and receive(q1, ..., qm) commands, where pi, qj are names of ports of its interlocutors. Every such edge exits a transition emiting a request for send or receivemessage. A transmission channel between the agent and its intelocutors is established when its port holds a send or receive command, while ports of its interlocutors hold respective (matching) communication commands. This gives rise to communication between the agent and its interlocutors, after which the channel is disrupted: hence floating channels. Some behavioural properties of such network system are examined, their decision complexity, deadlock and fairness in their number.

6

Analysis of Multi Layer Neural Networks with Direct and Cross Forward Connection

Płaczek S., Adhikari B.

Fundamenta Informaticae

|

2014

|

Vol. 133, nr 2/3

227--240

EN

Artificial Neural Networks are of much interest for many practical reasons. As of today, they are widely implemented. Of many possible ANNs, the most widely used one is the backpropagation model with direct connection. In this model the input layer is fed with input data and each subsequent layers are fed with the output of preceding layer. This model can be extended by feeding the input data to each layer. This article argues that this new model, named Cross Forward Connection, is optimal than the widely used Direct Connection.

7

A Decomposition Framework for Computing and Querying Multidimensional OLAP Data Cubes over Probabilistic Relational Data

Cuzzocrea A., Gunopulos D.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 2

239--266

EN

Focusing on novel database application scenarios, where data sets arise more and more in uncertain and imprecise formats, in this paper we propose a novel decomposition framework for efficiently computing and querying multidimensional OLAP data cubes over probabilistic data, which well-capture previous kind of data. Several models and algorithms supported in our proposed framework are formally presented and described in details, based on well-understood theoretical statistical/ probabilistic tools, which converge to the definition of the so-called probabilistic OLAP data cubes, the most prominent result of our research. Finally, we complete our analytical contribution by introducing an innovative Probability Distribution Function (PDF)-based approach, which makes use of well-known probabilistic estimators theory, for efficiently querying probabilistic OLAP data cubes, along with a comprehensive experimental assessment and analysis over synthetic probabilistic databases.

8

Generalized Hybrid Encoding of Polyhierarchical Structures

Lewandowski J., Rybiński H.

Fundamenta Informaticae

|

2013

|

Vol. 127, nr 1-4

461--477

EN

Polyhierarchical structures play an important role in artificial intelligence, especially in knowledge representation. The main problem with using them efficiently is lack of efficient methods of accessing related nodes, which limits the practical applications. The proposed hybrid indexing approach generalizes various methods and makes possible combining them in a uniform manner within one index, which adapts to a particular topology of the data structure. This gives rise to a balance between compactness of the index and fast responses to the search requests. The correctness of the proposed method is formally shown, and its performance is evaluated. The results prove its high efficiency.

9

Self-Indexed Grammar-Based Compression

Claude F., Navarro G.

Fundamenta Informaticae

|

2011

|

Vol. 111, nr 3

313-337

EN

Self-indexes aim at representing text collections in a compressed format that allows extracting arbitrary portions and also offers indexed searching on the collection. Current self-indexes are unable of fully exploiting the redundancy of highly repetitive text collections that arise in several applications. Grammar-based compression is well suited to exploit such repetitiveness. We introduce the first grammar-based self-index. It builds on Straight-Line Programs (SLPs), a rather general kind of context-free grammars. If an SLP of n rules represents a text T[1, u], then an SLP-compressed representation of T requires 2n log2 n bits. For that same SLP, our self-index takes O(n log n) + n log2 u bits. It extracts any text substring of length m in time O((m+ h) log n), and finds occ occurrences of a pattern string of length m in time O((m(m + h) + h occ) log n), where h is the height of the parse tree of the SLP. No previous grammar representation had achieved o(n) search time. As byproducts we introduce (i) a representation of SLPs that takes 2n log2 n(1+o(1)) bits and efficiently supports more operations than a plain array of rules; (ii) a representation for binary relations with labels supporting various extended queries; (iii) a generalization of our self-index to grammar compressors that reduce T to a sequence of terminals and nonterminals, such as Re-Pair and LZ78.

10

Hexagonal discrete global GRID systems for geospatial computing

Sahr K.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2011

|

Vol. 22

363--376

EN

Advanced geospatial applications often involve complex computing operations performed under sometimes severe resource constraints. These applications primarily rely on traditional raster and vector data structures based on square lattices. But there is a significant body of research that indicates that data structures based on hexagonal lattices may be a superior alternative for efficient representation and processing of raster and vector data in high performance applications. The advantages of hexagonal rasters for image processing are discussed, and hexagonal discrete global grid systems for location coding are introduced. The combination provides an efficient, unified approach to location representation and processing in geospatial systems.

11

Finding Patterns In Given Intervals

Crochemore M., Iliopoulos C.S., Kubica M., Rahman M.S., Waleń T.

Fundamenta Informaticae

|

2010

|

Vol. 101, nr 3

173-186

EN

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both the cases, we develop efficient solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.

12

A New Algorithm for Building Alphabetic Minimax Trees

Gagie T.

Fundamenta Informaticae

|

2009

|

Vol. 97, nr 3

321-329

EN

We show how to build an alphabetic minimax tree for a sequence W = w1, . . . ,wn of real weights in O(nd log log n) time, where d is the number of distinct integers .wi.. We apply this algorithm to building an alphabetic prefix code given a sample.

13

Usage of dedicated data structures for URL databases in a large-scale crawling

Dorosz K.

Computer Science

|

2009

|

Vol. 10

7-17

EN

The article discuss usage of Berkeley DB data structures such as hash tables and b-trees for implementation of a high performance URL database. The article presents a formal model for a data structures oriented URL database, which can be used as an alternative for a relational oriented URL database.

PL

W artykule omówiono zastosowanie struktur danych z pakietu Berkeley DB, takich jak: tablice z haszowaniem i b-drzewa do implementacji wysoko wydajnych baz danych adresów URL. Przedstawiono model formalny bazy danych zorientowanej na struktury pamieci, która może być alternatywa dla relacyjnie zorientowanej bazy danych linków URL.

14

On efficient implementations of median filters in theory and in practice

Stoliński S., Grabowski S., Bieniecki W.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2009

|

T. 13, z. 3/1

1021-1032

EN

The median filter, in its scalar and vector form, is a classic tool for suppressing impulse noise from images. In this paper we present a theoretical algorithm for worst-case optimized scalar median finding and an efficient implementation of the vector median filter (VMF). The former has not better complexity than two existing algorithms, but matches them for some relation between L and r, and is obtained using means which are novel in this context. The latter achievement is a simple practical idea which, for large enough masks, speeds up the standard (naive) implementation of VMF several times. We also presented results of a multi-threaded implementation, run on multicore machines.

PL

Filtr medianowy, w postaci skalarnej i wektorowej, jest klasycznym narzędziem usuwania szumu impulsowego z obrazów. W pracy przedstawiamy teoretyczny algorytm skalarnej filtracji medianowej, zoptymalizowany dla najgorszego przypadku, oraz efektywną implementację wektorowego filtru medianowego (VMF). Pierwszy z algorytmów nie osiąga lepszej złożoności niż dwa inne istniejące algorytmy dla tego problemu, ale wyrównuje ich złożoności dla pewnych L i r (odpowiednio: liczba poziomów jasności i promień maski), a środki użyte dla osiągnięcia tego celu stanowią w tym zastosowaniu nowość. Drugi z algorytmów to prosta idea praktyczna przyspieszająca, dla odpowiednio dużych masek, implementację standardową (naiwną) kilkakrotnie. Przedstawiliśmy również wyniki implementacji wielowątkowej, uruchomionej na maszynach wielordzeniowych.

15

Compile the Hypothesis Space: Do it Once, Use it Often

Fonseca N.A., Camacho R., Rocha R., Costa V.S.

Fundamenta Informaticae

|

2008

|

Vol. 89, nr 1

45-67

EN

Inductive Logic Programming (ILP) is a powerful and well-developed abstraction for multi-relational data mining techniques. Despite the considerable success of ILP, deployed ILP systems still have efficiency problems when applied to complex problems. In this paper we propose a novel technique that avoids the procedure of deducing each example to evaluate each constructed clause. The technique is based on the Mode Directed Inverse Entailment approach to ILP, where a bottom clause is generated for each example and the generated clauses are subsets of the literals of such bottom clause. We propose to store in a prefix-tree all clauses that can be generated from all bottom clauses together with some extra information. We show that this information is sufficient to estimate the number of examples that can be deduced froma clause and present an ILP algorithmthat exploits this representation. We also present an extension of the algorithm where each prefix-tree is computed only once (compiled) per example. The evaluation of hypotheses requires only basic and efficient operations on trees. This proposal avoids re-computation of hypothesis’ value in theorylevel search, in cross-validation evaluation procedures and in parameter tuning. Both proposals are empirically evaluated on real applications and considerable speedups were observed.

16

Problems with storing temporal data

Rybak T.

Zeszyty Naukowe Politechniki Białostockiej. Informatyka

|

2007

|

Z. 2

121-140

EN

Article shows problems with storing temporal data. It describes tree structures used to storę it, and problems with them. Then it describes using relational databases for storing temporal data, and how features provided in relational databases can be used to over-come problems present when trees are used to store temporal data.

PL

Artykuł przedstawia problemy implementacyjne związane z przechowywaniem danych temporalnych. Opisuje struktury drzewiaste, które mogą być użyte do przechowywania temporalnych danych oraz problemy z nimi związane. Przedstawia sposób użycia relacyjnych baz danych do przechowywania danych temporalnych, jakie wiążą się z tym problemy, jak można wykorzystać możliwości oferowane przez bazy danych do ułatwienia imple-menacji. Opisuje problemy z wydajnością oraz sposób ich rozwiązania w relacyjnych bazach danych.

17

Storing and sharing versions of data in multiversion data warehouse : implementation and experimental evaluation

Chmiel J., Wrembel R.

Foundations of Computing and Decision Sciences

|

2007

|

Vol. 32, No. 2

87-109

EN

In this paper we present a technique, called Bitmap Sharing, for sharing data among multiple versions of a data warehouse (DW). To this end. vre apply bitmaps that describe DW versions a given data item is shared by. Bitmap Sharing was implemented and experimentally compared to two other advanced data sharing techniques proposed in the literature. The results demonstrate that Bitmap Sharing outperforms these techniques for: inserting data into multiple DW versions, selecting data from given DW versions, and deriving multiple DW versions with shared data.

18

A Dichotomic Search Algorithm for Mining and Learning in Domain-Specific Logics

Ferré S., King R. D.

Fundamenta Informaticae

|

2005

|

Vol. 66, nr 1,2

1--32

EN

Many application domains make use of specific data structures such as sequences and graphs to represent knowledge. These data structures are ill-fitted to the standard representations used in machine learning and data-mining algorithms: propositional representations are not expressive enough, and first order ones are not efficient enough. In order to efficiently represent and reason on these data structures, and the complex patterns that are related to them, we use domain-specific logics. We show these logics can be built by the composition of logical components that model elementary data structures. The standard strategies of top-down and bottom-up search are ill-suited to some of these logics, and lack flexibility. We therefore introduce a dichotomic search strategy, that is analogous to a dichotomic search in an ordered array. We prove this provides more flexibility in the search, while retaining completeness and non-redundancy. We present a novel algorithm for learning using domain specific logics and dichotomic search, and analyse its complexity. We also describe two applications which illustrates the search for motifs in sequences; where these motifs have arbitrary length and length-constrained gaps. In the first application sequences represent the trains of the East-West challenge; in the second application they represent the secondary structure of Yeast proteins for the discrimination of their biological functions.

19

Textual model of graphic data

Żarnowski A.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2004

|

Vol. 14

1--6

EN

This paper presents a new, textual model of image geoinformation. This model can be applied to the digital photogrammetry and GIS. Black-and-white and color digital images are conversed into a text by means of an alphabet, context-free grammars, and a language belonging to the image languages class; all specially developed for this purpose. Geometrical properties of terrain objects are analysed with a distinct mathematical device. An important aspect of this textual model is that the generated text is a semantic network. Thus, lexicomorphologic, lexicologic and lexicographic methods of mathematical linguistics can be applied to the computer recognition of terrain objects and to the analysis of their properties. Examples of graphic data in the textual model are presented.