Biblio

A comparative analysis of the classical and approximation methods of spectral analysis of fast-variable processes in technical systems is carried out. It is shown that the approximation methods make it possible to substantially remove the contradiction between the requirements for spectrum smoothing and its frequency resolution. On practical examples of vibroacoustic signals, the effectiveness of approximation methods is shown. The Prony method was used to process the time series. The interactive frequency segmentation method and the direct identification method were used for approximation and frequency characteristics.

This paper studies the deletion propagation problem in terms of minimizing view side-effect. It is a problem funda-mental to data lineage and quality management which could be a key step in analyzing view propagation and repairing data. The investigated problem is a variant of the standard deletion propagation problem, where given a source database D, a set of key preserving conjunctive queries Q, and the set of views V obtained by the queries in Q, we try to identify a set T of tuples from D whose elimination prevents all the tuples in a given set of deletions on views △V while preserving any other results. The complexity of this problem has been well studied for the case with only a single query. Dichotomies, even trichotomies, for different settings are developed. However, no results on multiple queries are given which is a more realistic case. We study the complexity and approximations of optimizing the side-effect on the views, i.e., find T to minimize the additional damage on V after removing all the tuples of △V. We focus on the class of key-preserving conjunctive queries which is a dichotomy for the single query case. It is surprising to find that except the single query case, this problem is NP-hard to approximate within any constant even for a non-trivial set of multiple project-free conjunctive queries in terms of view side-effect. The proposed algorithm shows that it can be approximated within a bound depending on the number of tuples of both V and △V. We identify a class of polynomial tractable inputs, and provide a dynamic programming algorithm to solve the problem. Besides data lineage, study on this problem could also provide important foundations for the computational issues in data repairing. Furthermore, we introduce some related applications of this problem, especially for query feedback based data cleaning.

In this article, we introduce a new method for computing fixed points of a class of iterated functions in a finite time, by exponentiating linear multivalued operators. To better illustrate this approach and show that our method can give fast and accurate results, we have chosen two well-known applications which are difficult to handle by usual techniques. First, we apply the exponentiation of linear operators to a digital filter in order to get a fine approximation of its behavior at an arbitrary time. Second, we consider a PID controller. To get a reliable estimate of its control function, we apply the exponentiation of a bundle of linear operators. Note that, our technique can be applied in a more general setting, i.e. for any multivalued linear map and that the general method is also introduced in this article.

We investigate the complexity of computing an optimal repair of an inconsistent database, in the case where integrity constraints are Functional Dependencies (FDs). We focus on two types of repairs: an optimal subset repair (optimal S-repair) that is obtained by a minimum number of tuple deletions, and an optimal update repair (optimal U-repair) that is obtained by a minimum number of value (cell) updates. For computing an optimal S-repair, we present a polynomial-time algorithm that succeeds on certain sets of FDs and fails on others. We prove the following about the algorithm. When it succeeds, it can also incorporate weighted tuples and duplicate tuples. When it fails, the problem is NP-hard, and in fact, APX-complete (hence, cannot be approximated better than some constant). Thus, we establish a dichotomy in the complexity of computing an optimal S-repair. We present general analysis techniques for the complexity of computing an optimal U-repair, some based on the dichotomy for S-repairs. We also draw a connection to a past dichotomy in the complexity of finding a "most probable database" that satisfies a set of FDs with a single attribute on the left hand side; the case of general FDs was left open, and we show how our dichotomy provides the missing generalization and thereby settles the open problem.

Hardware Trojans have become in the last decade a major threat in the Integrated Circuit industry. Many techniques have been proposed in the literature aiming at detecting such malicious modifications in fabricated ICs. For the most critical circuits, prevention methods are also of interest. The goal of such methods is to prevent the insertion of a Hardware Trojan thanks to ad-hoc design rules. In this paper, we present a novel prevention technique based on approximation. An approximate logic circuit is a circuit that performs a possibly different but closely related logic function, so that it can be used for error detection or error masking where it overlaps with the original circuit. We will show how this technique can successfully detect the presence of Hardware Trojans, with a solution that has a smaller impact than triplication.

In order to compactly represent a set of data, its medoid (the element with minimum summed distance to all other elements) is a useful choice. This has applications in clustering, compression and visualisation of data. In multimedia data, the set of data is often sampled as a sequence in time or space, such as a video shot or views of a scene. The exact calculation of the medoid may be costly, especially if the distance function between elements is not trivial. While approximation methods for medoid selection exist, we show in this work that they do not perform well on sequences of images. We thus propose a novel algorithm for efficiently selecting an approximate medoid of a temporal sequence and assess its performance on two large-scale video data sets.