Search

Indexing is a well-known database technique used to facilitate data access and speed up query processing. Nevertheless, the construction and modification of indexes are very expensive. In traditional approaches, all records in the database table are equally covered by the index. It is not effective, since some records may be queried very often and some never. To avoid this problem, adaptive merging has been introduced. The key idea is to create an index adaptively and incrementally as a side-product of query processing. As a result, the database table is indexed partially depending on the query workload. This paper faces the problem of adaptive merging for phase change memory (PCM). The most important features of this memory type are limited write endurance and high write latency. As a consequence, adaptive merging should be investigated from the scratch. We solve this problem in two steps. First, we apply several PCM optimization techniques to the traditional adaptive merging approach. We prove that the proposed method (eAM) outperforms a traditional approach by 60%. After that, we invent the framework for adaptive merging (PAM) and propose a new variant of the PCM-optimized index. It further improves the system performance by 20% for databases where search queries interleave with data modifications. [ABSTRACT FROM AUTHOR]

A lot of research activity has recently taken place around the chase procedure, due to its usefulness in data integration, data exchange, query optimization, peer data exchange and data correspondence, to mention a few. As the chase has been investigated and further developed by a number of research groups and authors, many variants of the chase have emerged and associated results obtained. Due to the heterogeneous nature of the area it is frequently difficult to verify the scope of each result. In this paper we take closer look at recent developments, and provide additional results. Our analysis allows us create a taxonomy of the chase variations and the properties they satisfy. Two of the most central problems regarding the chase is termination, and discovery of restricted classes of sets of dependencies that guarantee termination of the chase. The search for the restricted classes has been motivated by a fairly recent result that shows that it is undecidable (RE-complete, to be more precise) to determine whether the chase with a given dependency set will terminate on a given instance. There is a small dissonance here, since the quest has been for classes of sets of dependencies guaranteeing termination of the chase on all instances, even though the latter problem was not known to be undecidable. We resolve the dissonance in this paper by showing that determining whether the chase with a given set of dependencies terminates on all instances is unsolvable, and on level II02 in the Arithmetical Hierarchy. For this we use a reduction from word rewriting systems, thereby also showing the close connection between the chase and word rewriting. The same reduction also gives us the aforementioned instancedependent RE-completeness result as a byproduct. For one of the restricted classes guaranteeing termination on all instances, the stratified sets dependencies, we provide new complexity results for the problem of testing whether a given set of dependencies belongs to it. These results rectify some previous claims that have occurred in the literature. [ABSTRACT FROM AUTHOR]

Particle Swarm Optimization (PSO), though originally introduced for continuous search spaces, has been increasingly applied to combinatorial optimization problems. In this paper, we focus on the PSO applications to permutation-based problems. As far as we know, the most popular and general PSO schemes for permutation solutions are those based on random key techniques. After highlighting the main criticalities of the random key approach, we introduce a discrete PSO variant for permutation-based optimization problems. By simulating search moves through a vector space, the proposed algorithm, Algebraic PSO (APSO), allows the original PSO design to be applied to the permutation search space. APSO directly represents both particle positions and velocities as permutations. The APSO search scheme is based on a general algebraic framework for combinatorial optimization based on strong mathematical foundations. However, in order to make this new scheme viable, some challenges have to be overcome: the choice of the order of the velocity terms, and the rationale behind the PSO inertial move. Design solutions have been proposed for both the issues. Furthermore, an alternative geometric interpretation of classical PSO dynamics allows to introduce a major APSO variant based on a novel concept of convex combination between permutation objects. In total, four APSO schemes have been introduced. Experiments have been held to compare the performances of the APSO schemes with respect to the random key based PSO schemes in literature. Widely adopted benchmark instances of four popular permutation problems have been considered. The experimental results clearly show that, with high statistical evidence, APSO outperforms its competitors and it reaches results comparable with state-of-the-art on most of the instances considered. [ABSTRACT FROM AUTHOR]

In this paper, we approach the problem of accepting all recursively enumerable languages by accepting networks of evolutionary processors (ANEPs, for short) with a fixed architecture. More precisely, we show that every recursively enumerable language can be accepted by an ANEP with an underlying graph in the form of a star with 13 nodes or by an ANEP with an underlying grid with 13 × 4 = 52 nodes as well as by ANEPs having underlying graphs in the form of a chain, a ring, or a wheel with 29 nodes each. In all these cases, the size and form as well as the general working strategy of the constructed networks do not depend on the accepted language; only the rewriting rules and the filters associated to each node of the networks depend on this language. Noteworthy is also the fact that the filtering process is implemented using random context conditions only. Our results answer problems which were left open in a paper published by J. Dassow and F. Manea at the conference on Descriptional Complexity of Formal Systems (DCFS) 2010 and improve a result published by B. Truthe at the conference on Non-Classical Models of Automata and Applications (NCMA) 2013. [ABSTRACT FROM AUTHOR]

Minimum Latency Problem (MLP) is a class of NP-hard combinatorial optimization problems which has many practical applications. In this paper, we investigate the global structure of the MLP solution space to propose a suitable meta-heuristic algorithm for the problem, which combines Tabu search (TS) and Variable Neighborhood Search (VNS). In the proposed algorithm, TS is used to prevent the search from getting trapped into cycles, and guide VNS to escape local optima. In a cooperative way, VNS is employed to generate diverse neighborhoods for TS. We also introduce a novel neighborhoods' structure for VNS and present a constant time operation for calculating the latency cost of each neighboring solution. Extensive numerical experiments and comparisons with the state of the art meta-heuristic algorithms in the literature show that the proposed algorithm is highly competitive, providing the new best solutions for several instances. [ABSTRACT FROM AUTHOR]

In this paper, we propose a predictor-corrector infeasible interior-point algorithm for semidefinite optimization based on the Nesterov-Todd scaling scheme. In each iteration, the algorithm computes the new iterate using a new combination of the predictor and corrector directions. Using the Ai-Zhang's wide neighborhood for linear complementarity problems, and extended to semidefinite optimization by Li and Terlaky, it is shown that the iteration complexity bound of the algorithm is ..., where n is the dimension of the problem and ɛ is the required precision. [ABSTRACT FROM AUTHOR]

In this paper, we present a new optimization method based on a new class of functions, namely generalized polynomials (GPs) for solving linear and nonlinear fractional differential equations (FDEs). In the proposed method, the solution of the problem under study is expanded in terms of the GPs with fixed coefficients, free coefficients and control parameters. The initial conditions are employed to compute the fixed coefficients. The residual function and its ||.||2 are employed for converting the problem under consideration to an optimization one and then choosing the unknown free coefficients and control parameters optimally. As a useful result, the necessary conditions of optimality are derived as a system of nonlinear algebraic equations with unknown free coefficients and control parameters. The validity and accuracy of the approach are illustrated by some numerical examples. The obtained results show that the proposed method is very efficient and accurate. [ABSTRACT FROM AUTHOR]

In this paper, a new operational matrix of variable-order fractional derivative (OMV-FD) is derived for the second kind Chebyshev wavelets (SKCWs). Moreover, a new optimization wavelet method based on SKCWs is proposed to solve multi variable-order fractional differential equations (MV-FDEs). In the proposed method, the solution of the problem under consideration is expanded in terms of SKCWs. Then, the residual function and its errors in 2-norm are employed for converting the problem under study to an optimization one, which optimally chooses the unknown coefficients. Finally, the method of constrained extremum is applied, which consists of adjoining the constraint equations obtained from the given initial conditions to the object function obtained from residual function by a set of unknown Lagrange multipliers. The main advantage of this approach is that it reduces such problems to those optimization problems, which greatly simplifies them and also leads to obtain a good approximate solution for them. [ABSTRACT FROM AUTHOR]

In the paper, an application of dynamic programming approach to global optimization of approximate association rules relative to coverage and length is presented. It is an extension of the dynamic programming approach to optimization of decision rules to inconsistent tables. Experimental results with data sets from UCI Machine Learning Repository are included. [ABSTRACT FROM AUTHOR]

The paper deals with the concrete planning problem - a stage of the web service composition in the PlanICS framework. We present several known and new methods of concrete planning including those based on Satisfiability Modulo Theories (SMT), Genetic Algorithm (GA), as well as methods combining SMT with GA and other nature-inspired algorithms such as Simulated Annealing (SA) and Generalised Extremal Optimization (GEO). The discussion of all the approaches is supported by the complexity analysis, extensive experimental results, and illustrated by a running example. [ABSTRACT FROM AUTHOR]

In the paper, an application of dynamic programming approach for optimization of association rules from the point of view of knowledge representation is considered. The association rule set is optimized in two stages, first for minimum cardinality and then for minimum length of rules. Experimental results present cardinality of the set of association rules constructed for information system and lower bound on minimum possible cardinality of rule set based on the information obtained during algorithm work as well as obtained results for length. [ABSTRACT FROM AUTHOR]

Efficiency, the basic concept of multi-objective optimization is investigated for the class of pairwise comparison matrices. A weight vector is called efficient if no alternative weight vector exists such that every pairwise ratio of the latter's components is at least as close to the corresponding element of the pairwise comparison matrix as the one of the former's components is, and the latter's approximation is strictly better in at least one position. A pairwise comparison matrix is called simple perturbed if it differs from a consistent pairwise comparison matrix in one element and its reciprocal. One of the classical weighting methods, the eigenvector method is analyzed. It is shown in the paper that the principal right eigenvector of a simple perturbed pairwise comparison matrix is efficient. An open problem is exposed: the search for a necessary and sufficient condition of that the principal right eigenvector is efficient. [ABSTRACT FROM AUTHOR]

The geometric Bonferroni mean (GBM) is an important aggregation technique which reflects the correlations of aggregated arguments. Based on the GBM, in this paper, we develop the optimized weighted geometric Bonferronimean (OWGBM) and the generalized optimized weighted geometric Bonferroni mean (GOWGBM), whose characteristics are to reflect the preference and interrelationship of the aggregated arguments. Furthermore, we develop the intuitionistic fuzzy optimized weighted geometric Bonferroni mean (IFOWGBM) and the generalized intuitionistic fuzzy optimized weighted geometric Bonferroni mean (GIFOWGBM), and study their desirable properties such as idempotency, commutativity, monotonicity and boundedness. Finally, based on the IFOWGBM and GIFOWGBM, we present an approach to multi-criteria decision making and illustrate it with a practical example. [ABSTRACT FROM AUTHOR]

In general, a theoretical Computerized Tomography (CT) imaging problem can be formulated as a system of linear equations. The discrete inverse problem of reconstructing finite subsets of the n-dimensional integer lattice Zn that are only accessible via their line sums (discrete x-rays), in a finite set of lattice directions, results into an even more ill-posed problem, from noisy data. Because of background noise in the data, the reconstruction process is more difficult since the system of equations becomes inconsistent easily. Unfortunately, with every different kind of CT, as with many contemporary advanced instrumentation systems, one is always faced with an additional experimental data noise reduction problem. By using Information Geometry (IG) and Geometric Science of Information (GSI) approach, it is possible to extend traditional statistical noise reduction concepts and to develop new algorithm to overcome many previous limitations. On the other end, in the past five decades, trend in Systems Theory, in specialized research area, has shifted from classic single domain information channel transfer function approach (Shannon's noisy channel) to the more structured ODR Functional Sub-domain Transfer Function Approach (Observation, Description and Representation), according to computational information conservation theory (CICT) Infocentric Worldview model (theoretically, virtually noise-free data). CICT achieves to bringing classical and quantum information theory together in a single framework, by considering information not only on the statistical manifold of model states but also from empirical measures. In fact, to grasp a more reliable representation of experimental reality and to get stronger physical and biological system correlates, researchers and scientists need two intelligently articulated hands: both stochastic and combinatorial approaches synergically articulated by natural coupling. As a matter of fact, traditional rational number system Q properties allow to generate an irreducible co-domain for every computational operative domain used. Then, computational information usually lost by using classic LTR computational approach only, based on the traditional noise-affected data model stochastic representation (with high-level perturbation computational model under either additive or multiplicative perturbation hypothesis), can be captured and fully recovered to arbitrary precision, by a corresponding complementary co-domain, step-by-step. In previous paper, we already saw that CICT can supply us with Optimized Exponential Cyclic numeric Sequences (OECS) co-domain perfectly tuned to low-level multiplicative noise source generators, related to experimental high-level overall perturbation. Now, associated OECS co-domain polynomially structured information can be used to evaluate any computed result at arbitrary scale, and to compensate for achieving multi-scale computational information conservation. [ABSTRACT FROM AUTHOR]