Much research work has recently focused on the problem of representing historical information in XML. In this paper, we describe an ongoing work to represent XML changes. Our model is a three-dimensional XML-based model (3D_XML in short) for representing and querying histories of XML documents. The proposed model incorporates three time dimensions, valid time, transaction time, and efficacy time without extending the syntax of XML. We use XQuery to express complex temporal queries on the evolution of the document contents. We believe that native XML databases (NXDs) present a viable alternative to relational temporal databases when complex time dependent data has to be manipulated and stored. So NXDs will be our choice.

Since its introduction in 1997, the M-tree became a respected metric access method (MAM), while remaining, together with its descendants, still the only database-friendly MAM, that is, a dynamic structure persistent in paged index. Although there have been many other MAMs developed over the last decade, most of them require either static or expensive indexing. By contrast, the dynamic M-tree construction allows us to index very large databases in subquadratic time, and simultaneously the index can be maintained up-to-date (i.e., supports arbitrary insertions/deletions). In this article we propose two new techniques improving dynamic insertions in M-tree—the forced reinsertion strategies and so-called hybrid-way leaf selection. Both of the techniques preserve logarithmic asymptotic complexity of a single insertion, while they aim to produce more compact M-tree hierarchies (which leads to faster query processing). In particular, the former technique reuses the well-known principle of forced reinsertions, where the new insertion algorithm tries to re-insert the content of an M-tree leaf that is about to split in order to avoid that split. The latter technique constitutes an efficiency-scalable selection of suitable leaf node wherein a new object has to be inserted. In the experiments we show that the proposed techniques bring a clear improvement (speeding up both indexing and query processing) and also provide a tuning tool for indexing vs. querying efficiency trade-off. Moreover, a combination of the new techniques exhibits a synergic effect resulting in the best strategy for dynamic M-tree construction proposed so far.

Since its introduction in 1997, the M-tree became a respected metric access method (MAM), while remaining, together with its descendants, still the only database-friendly MAM, that is, a dynamic structure persistent in paged index. Although there have been many other MAMs developed over the last decade, most of them require either static or expensive indexing. By contrast, the dynamic M-tree construction allows us to index very large databases in subquadratic time, and simultaneously the index can be maintained up-to-date (i.e., supports arbitrary insertions/deletions). In this article we propose two new techniques improving dynamic insertions in M-tree—the forced reinsertion strategies and so-called hybrid-way leaf selection. Both of the techniques preserve logarithmic asymptotic complexity of a single insertion, while they aim to produce more compact M-tree hierarchies (which leads to faster query processing). In particular, the former technique reuses the well-known principle of forced reinsertions, where the new insertion algorithm tries to re-insert the content of an M-tree leaf that is about to split in order to avoid that split. The latter technique constitutes an efficiency-scalable selection of suitable leaf node wherein a new object has to be inserted. In the experiments we show that the proposed techniques bring a clear improvement (speeding up both indexing and query processing) and also provide a tuning tool for indexing vs. querying efficiency trade-off. Moreover, a combination of the new techniques exhibits a synergic effect resulting in the best strategy for dynamic M-tree construction proposed so far.

Definitions of two different ways of coarsening of basic belief assignments to opinions the simple coarsening and the normal coarsening are recalled in this contribution. A relation of results of combination of the normal opinions using the consensus operator to belief functions on an original n-element frame of discernment is examined. A questionable meaning of the normal coarsening is discussed.

In this study we engage in belief processing which enables managing of multiple and overlapping elements of a frame of discernment. Our focus is directed on DSm approach, which was originally introduced as a generalization of the Dempster-Shafer theory. Paradoxically, later it was presented also as a special case of the Dempster-Shafer approach applied on such frame of discernment. In this paper we discuss what is new in DSm approach, what are the benefits of DSm approach, and what is its real contribution to belief function theory.

Principal ideas of the minC combination are recalled. A mathematical structure of generalized frames of discernment is formalized. A generalized schema for a computation of the minC combination is presented. Conflicting belief masses redistribution among non-conflicting focal elements is overviewed. Final general formulas for computation of the minC combination are presented. Some examples of computation of the minC combination follow. Related works and approaches are referred in the end.

V tomto příspěvku se zbýváme extrakcí informací z webových zdrojů převážně textového charakteru. K tomuto účelu jsme se pokusili využít několik lingvistických nástrojů pro zpracování přirozeného textu v češtině. Jmenovitě se jedná o nástroje pražského projektu PDT a český WordNet. Cílem příspěvku je přiblížit možnosti, které tyto nástroje pro extrakci informací z textu poskytují. Extrakcí informací se zde zabýváme především v kontextu sémantického webu a zkoumáme možnosti, jak tyto nástroje využít pro automatizaci sémantické anotace stránek současného webu.

The metric space paradigm has recently received attention as an important model of similarity in the area of Bioinformatics. Numerous techniques have been proposed to solve similarity (range or nearest-neighbor) queries on collections of data from metric domains. Though important representatives are outlined, this chapter is not trying to substitute existing comprehensive surveys. The main objective is to explain and prove by experiments that similarity searching is typically an expensive process which does not easily scale to very large volumes of data, thus distributed architectures able to exploit parallelism must be employed. After a review of applications using the metric space approach in the field of Bioinformatics, the chapter provides an overview of methods used for creating index structures able to speedup retrieval. In the metric space approach, only pair-wise distances between objects are quantified, so they represent the level of dissimilarity. The key idea of index structures is to partition the data into subsets so that queries are evaluated without examining entire collections -- minimizing both the number of distance computations and the number of I/O accesses. These objectives are obtained by exploiting the property of metric spaces called the triangle inequality which states that if two objects are near a third object, they cannot be too distant to one another. Unfortunately, computational costs are still high and the linear scalability of single-computer implementations prevents from searching in large and ever growing data files efficiently. For these reasons, we describe very recent parallel and distributed similarity search techniques and study performance of their implementations. Specifically, Section 12.1 presents the metric space approach and its applications in the field of Bioinformatics. Section 12.2 describes some of the most popular centralized disk-based metric indexes. Consequently, Section 12.3 concentrates on parallel and distributed access methods which can deal with data collections that for practical purposes can be arbitrary large, which is typical for Bioinformatics workloads. An experimental evaluation of the presented distributed approaches on real-life data sets is presented in 12.4. The chapter concludes in Section 12.5.

Due to the exponential growth of digital data and its complexity, we need a technique which allows us to search such collections efficiently. A suitable solution is based on the peer-to-peer (P2P) network paradigm and the metric-space model of similarity. When a large volume of data is being inserted, the P2P network must expand to new peers in order to maintain its efficiency. Thus, many peers must be split. During a peer split, the data is halved and one half is migrated to a new peer. In this paper, we study the problem of peer splits and propose a specialized algorithm for speeding it up. In particular, we use the structured P2P network called the M-Chord. Search performance within a single peer is enhanced by the M-tree. In experimental evaluation, we compare the proposed algorithm with several straightforward solutions on a real network organizing 10 million images. Our algorithm provides a significant performance boost.

We have developed and implemented [1,2] infrastructure and RDF storage for the Semantic Web. When we filled it with data the need for some tool that could explore the data became evident. Unfortunately, none of existing solutions fulfills requirements imposed by the data and users expectations. This paper presents our RDF visualizer that was designed specifically to handle large RDF data by means of incremental navigation. A detailed description of the algorithm is given as well as actual results produced by the visualizer.

V tomto příspěvku je popsán přístup k virtuální integraci dat využívající současných principů, metod a nástrojů sémantického webu. Přístup pracuje s daty ve formátu RDF a předpokládá dostupnost ontologií, které je popisují. Ontologie jsou základem pro všechny kroky prezentovaného integračního procesu. Jsou využity jak k určení vztahů mezi daty a poskytovaným integrovaným pohledem, tak i k zápisu nalezených korespondencí. Ty jsou dále použity při zpracování dotazů kladených na integrovaná data.

Článek se zabývá přístupem, jak se pokusit zautomatizovat mnohdy netriviální úlohu nalezení pravidel pro integraci dat. Předkládaný přístup automaticky generuje kandidáty pravidel včetně jejich ohodnocení pomocí nepřímé míry definující jejich prioritu. Priorita může následně být použita buďto návrhářem (člověkem) jako pomocný prvek pro přípravu návrhu, nebo při automatickém návrhu integračního procesu zahrnující pravidla s maximální prioritou. Studie v příspěvku se detailně věnuje dvěma základním typům pravidel, ekvivalenci a hierarchii, přičemž ohodnocení kandidátů je založeno na (strukturální) analýze aktivních domén atributů. V neposlední řadě příspěvek ukazuje možnost decentralizovaného přístupu k integraci dat, jenž je inspirován webovými technologiemi.

In this paper we introduce a new M-tree building method, utilizing the classic idea of forced reinsertions. In case a leaf is about to split, some distant objects are removed from the leaf (reducing the covering radius), and then again inserted into the M-tree in a usual way. A regular leaf split is performed only after a series of unsuccessful reinsertion attempts. We expect the forced reinsertions will result in more compact Mtree hierarchies (i.e., more efficient query processing), while the index construction costs should be kept as low as possible. Considering both low construction costs and low querying costs, we examine several combinations of construction policies with reinsertions. The experiments show that forced reinsertions could significantly decrease the number of distance computations, thus speeding up indexing as well as querying.

As the XML has become a standard for data representation, it is inevitable to propose and implement techniques for efficient managing of XML data. A natural alternative is to exploit features of (object-)relational database systems, i.e. to rely on their long theoretical and practical history. The main concern of such techniques is the choice of an appropriate XML-to-relational mapping strategy. In this paper we focus on enhancing of user-driven techniques which leave the mapping decisions in hands of users who specify their requirements using schema annotations. We describe our prototype implementation called UserMap which is able to exploit the annotations more deeply searching the user-specified “hints” in the rest of the schema and applies an adaptive method on the remaining schema fragments. Using a sample set of supported fixed mapping methods we discuss problems related to query evaluation for storage strategies generated by the system, in particular correction of the candidate set of annotations and related query translation. And finally, we describe the architecture of the whole system.

As the popularity of XML as a format for data representation grows the need for storing XML data in an effective way grows as well. Recent research has provide us with effeective solutions based on storing XML data into relational databases and with new technologies based on storing XML data in the native form. However, design of XML databases has not been studied su±ciently yet. In this paper, we suppose a set of XML schemes that describe XML representation of our data in several types of XML documents. We show that we can not usually store the data directly in this representation because it can contain redundancies. To design an optimal database schema we therefore need to locate these redundancies and eliminate them.We describe two types of redundancies in XML data in this paper and show how to utilize a conceptual schema of the XML schemes to locate such redundancies. We also show how to normalize the XML schemes to eliminate these redundancies.

The notion of preference poses a new prospect of personalization of database queries. In addition, it can be exploited to optimize query execution. Indeed, a novel optimization technique involving preference is developed, and its algorithm presented.

A formalism for the logical description of computational agents and multi-agent systems is given. It is explained how it such a formal description can be used to configure and reason about multi-agent systems realizing computational intelligence models. A usage within a real software system Bang 3 is demonstrated. A way to extend the system toward dynamic environments with migrating agents is discussed.

This work deals with a problem of automatic composition of multi-agent system satisfying given constraints. A general concept of representation of connected groups of agents (schemes) within a multi-agent system is introduced and utilized for automatic building of schemes to solve a given computational intelligence task. We propose a combination of an evolutionary algorithm and a formal logic resolution system which is able to propose and verify new schemes. The approach is illustrated on simple examples.

Amorphous computing differs from the classical ideas about computations almost in every aspect. The architecture of amorphous computers is random, since they consist of a plethora of identical computational units spread randomly over a given area. Within a limited radius the units can communicate wirelessly with their neighbors via a single-channel radio.We consider a model whose assumptions on the underlying computing and communication abilities are among the weakest possible: all computational units are finite state probabilistic automata working asynchronously, there is no broadcasting collision detection mechanism and no network addresses. We show that under reasonable probabilistic assumptions such amorphous computing systems can possess universal computing power with a high probability. The underlying theory makes use of properties of random graphs and that of probabilistic analysis of algorithms. To the best of our knowledge this is the first result showing the universality of such computing systems.

Zatímco dílčí ontologie pokrývají jeden pohled na úzce vymezenou oblast, mnohé aplikace vyžadují obecnější přístup k popisovaným datům. Z tohoto důvodu se přistupuje ke srovnávání ontologií (Ontology Matching), které, pokud je to možné, transformuje několik různých ontologických popisů do jediného. Příspěvek popisuje případovou studii takového procesu za využití různých metod, srovnává jejich úspěšnost a diskutuje možnost využití dílčích výsledků k definici výsledné ontologie. Pro experiment byly nezávisle vytvořeny dvě triviální ontologie, které byly různými nástroji a metodami integrovány do jedné.

Vize sémantického webu byla představena před skoro již 10 lety, avšak žádná z její aplikací prozatím nedokázala oslovit takové množství lidí, jaké dnes používá web v současné podobě. Příspěvek se věnuje možnostem sémantického webu a přínosům, které může přinést pro koncové uživatele. Nejprve podává přehled o současných technologiích i jejich použití a následně diskutuje možnosti plynoucí z použití odkazů v prostředí sémantického webu tak, jak je známe z webu současného, tedy rozšiřující, zpřesňující či udávající kontext prezentované informace.

Exploiting the concepts of social networking represents a novel approach to the approximate similarity query processing. We present a metric social network where relations between peers, giving similar results, are established on per-query basis. Based on the universal law of generalization, a new query forwarding algorithm is proposed. The same principle is used to manage query histories of individual peers with the possibility to tune the tradeoff between the extent of the history and the level of the query-answer approximation. All algorithms are tested on real data and real network of computers.

This prototype implements the idea of social networking in metric spaces. The metric social network is a peer-to-peer network in which users can share their data without the need to send them to a centralized node. Searching in this system is based on the notion of similarity which is modelled using metric spaces. The architecture of the metric social network is formally defined by using acquaintance and friendship relations. The implementation builds on top of the MESSIF framework library.

XBW [10] is modular program for lossless compression that enables testing various combinations of algorithms. We obtained best results with XML parser creating dictionary of syllables or words combined with Burrows-Wheeler transform - hence the name XBW. The motivation for creating parser that handles non-valid XML and HTML files, has been system EGOTHOR [5] for full-text searching. On files of size approximately 20MB, formed by hundreds of web pages, we achieved twice the compression ratio of bzip2 while running only twice as long. For smaller files, XBWhas very good results, compared with other programs, especially for languages with rich morphology such as Slovak or German. For any big textual files, our program has good balance of compression and run time. Program XBW enables use of parser and coder with any implemented algorithm for compression.We have implemented Burrows-Wheeler transform which together with MTF and RLE forms block compression, dictionary methods LZC and LZSS, and finally statistical method PPM. Coder offers choice of Huffman and arithmetic coding.

We study behavioural patterns learned by a robotic agent by means of two different control and adaptive approaches - a radial basis function neural network trained by evolutionary algorithm, and a traditional reinforcement Q-learning algorithm. In both cases, a set of rules controlling the agent is derived from the learned controllers, and these sets are compared. It is shown that both procedures lead to reasonable and compact, albeit rather different, rule sets.

The thesis deals with security hazards in distributed environments where traditional centralized approaches are only of limited serviceability. One of the very successful model for treating security and access management in distributed systems are so called reputation systems. The main goal of the rep- utation systems is to provide entities in the environment with mechanisms for inferring and building trust consequently used for access control. If the trust between two entities is high enough, transactions are likely to be allowed. The thesis proposes a new security model with trust management system for dynamic and distributed environments with huge number of entities. In dynamic systems new entities or relationships are likely to emerge or existing entities or relationships may often disappear. Such dynamics pose severe problems even for traditional reputation systems. Therefore our approach differs from the traditional ones in the way adopted for establishment and management of trust between entities in our point of view trust is not assigned to particular relationships but the trust is common for a group of entities. In this way, our proposal significantly enhances ability to infer trust between entities with no previous personal experiences with each other or in environments with huge number of entities. For the proposal differs in understanding of trust, it uses a hypergraph model for representation of system of entities. The security model proposed in the thesis contains two algorithms for transformation of a general input graph structure into hypergraph model, an algorithm treating dynamics of the distributed environment and a security subsystem. Our experimental implementation SecGrid utilizes proposed algorithms and it is used for experimental verification of the security models. The experiments investigate ability of the transformation algorithms; in details the dynamic part of our proposal together with the security subsystem proposed specially for the hypergraph model. Experiments show that our model overcame the traditional graph model in many ways especially in dynamic environments with huge amount of entities.

Despite the tremendous research activity in the field of searching engines for the Internet, current searching engines still face some severe limitations. The paper presents an idea of a distributed data source environment to be build on the current state of the art technologies available on the Internet. The paper combines recent advances in the fields of a data inconsistency, a data integration and reputations of sources for further refinements of data searching and sharing processes. The paper generalizes the data binary formalism narrowly connected with the ideas of the semantic web into the <0,1> interval to enable the consideration of uncertainty at various levels.

While partial ontologies cover view at one-track area, many applications require much more general approach to describe their data. On this account it approaches to ontology matching as a headstone of further operations, that can transform several ontological descriptions into one. This paper describe case study of such process with using different methods, confront their fruitfulness and discuss a possibility of using particular results to definition of final ontology. Two trivial ontologies were created (independently of any tool) and they were matched using various selected tools.

A computational model of molecularly communicating mobile nanomachines is de¯ned. Nanomachines are modelled by timed probabilistic automata augmented by a severely restricted communication mechanism. We show that for molecular communication among such machines an asynchronous stochastic protocol originally designed for wireless communication in so-called amorphous computers with static computational units can also be used. We design an algorithm that using randomness and timing delays selects with a high probability a leader from among sets of anonymous candidates. This enables a simulation of counter automata proving that networks of mobile nanomachines possess universal computing power.

We propose a simple yet cognitively powerful architecture of an embodied conscious agent whose functioning is in a good agreement with neurophysiological evidence. Our model differs from other proposals by exploiting two complementary internal world models having a different purpose than that in similar models known from the literature. The first model captures the sensorimotor "syntax" of the agent's behavior and is used for situating the agent in its environment. The second model describes the sensorimotor dynamics of the world and is used for controlling the agent's behavior. Both internal world models are built automatically, autonomously in the course of agent's interaction with the environment and their coop- eration takes care of symbol grounding. We show that the cognitive potential of the proposed model goes substantially beyond that of earlier models since it supports algorithmic processes underlying phenomena similar to higher cognitive functions such as imitation learning and the development of commu- nication, language, thinking and consciousness.

Nastíníme jednoduchou, ale přesto kognitivně účinnou architekturu inteligentního agenta. Model využívá dvou komplementárních vnitřních modelů světa: jeden pro „syntax“ poznaného světa a druhý pro jeho sémantiku. Tyto modely řeší problém porozumění konceptům a podporují algoritmické procesy, jejichž efekty se pro pozorovatele jeví jako projevy vyšších kognitivních funkcí, jakými jsou imitační učení, rozvoj komunikace, řeči, myšlení a vědomí.

Classical models of computation no longer fully correspond to the current notions of computing in modern systems. Even in the sciences, many natural systems are now viewed as systems that compute. Can one devise models of computation that capture the notion of computing as seen today and that could play the same role as Turing machines did for the classical case? We propose two models inspired from key mechanisms of current systems in both artificial and natural environments: evolving automata and interactive Turing machines with advice. The two models represent relevant adjustments in our apprehension of computing: the shift to potentially non-terminating interactive computations, the shift towards systems whose hardware and/or software can change over time, and the shift to computing systems that evolve in an unpredictable, non-uniform way. The two models are shown to be equivalent and both are provably computationally more powerful than the models covered by the old computing paradigm. The models also motivate the extension of classical complexity theory by non-uniform classes, using the computational resources that are natural to these models. Of course, the additional computational power of the models cannot in general be meaningfully exploited in concrete goal-oriented computations.