An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters

Bloom filters are a data structure for storing data in a compressed form. They offer excellent space and time efficiency at the cost of some loss of accuracy (so-called lossy compression). This work presents a yes-no Bloom filter, which as a data structure consisting of two parts: the yes-filter which is a standard Bloom filter and the no-filter which is another Bloom filter whose purpose is to represent those objects that were recognised incorrectly by the yes-filter (that is, to recognise the false positives of the yes-filter). By querying the no-filter after an object has been recognised by the yes-filter, we get a chance of rejecting it, which improves the accuracy of data recognition in comparison with the standard Bloom filter of the same total length. A further increase in accuracy is possible if one chooses objects to include in the no-filter so that the no-filter recognises as many as possible false positives but no true positives, thus producing the most accurate yes-no Bloom filter among all yes-no Bloom filters. This paper studies how optimization techniques can be used to maximize the number of false positives recognised by the no-filter, with the constraint being that it should recognise no true positives. To achieve this aim, an Integer Linear Program (ILP) is proposed for the optimal selection of false positives. In practice the problem size is normally large leading to intractable optimal solution. Considering the similarity of the ILP with the Multidimensional Knapsack Problem, an Approximate Dynamic Programming (ADP) model is developed making use of a reduced ILP for the value function approximation. Numerical results show the ADP model works best comparing with a number of heuristics as well as the CPLEX built-in solver (B&B), and this is what can be recommended for use in yes-no Bloom filters. In a wider context of the study of lossy compression algorithms, our researchis an example showing how the arsenal of optimization methods can be applied to improving the accuracy of compressed data.

Improving power and accuracy of genome-wide association studies via a multi-locus mixed linear model methodology

Genome-wide association studies (GWAS) have been widely used in genetic dissection of complex traits. However, common methods are all based on a fixed-SNP-effect mixed linear model (MLM) and single marker analysis, such as efficient mixed model analysis (EMMA). These methods require Bonferroni correction for multiple tests, which often is too conservative when the number of markers is extremely large. To address this concern, we proposed a random-SNP-effect MLM (RMLM) and a multi-locus RMLM (MRMLM) for GWAS. The RMLM simply treats the SNP-effect as random, but it allows a modified Bonferroni correction to be used to calculate the threshold p value for significance tests. The MRMLM is a multi-locus model including markers selected from the RMLM method with a less stringent selection criterion. Due to the multi-locus nature, no multiple test correction is needed. Simulation studies show that the MRMLM is more powerful in QTN detection and more accurate in QTN effect estimation than the RMLM, which in turn is more powerful and accurate than the EMMA. To demonstrate the new methods, we analyzed six flowering time related traits in Arabidopsis thaliana and detected more genes than previous reported using the EMMA. Therefore, the MRMLM provides an alternative for multi-locus GWAS.

Chemistry of mixed-ligand methoxy bonded oxidovanadium(V) complexes with a family of hydrazone ligands containing VO3+ core and their substituent controlled methoxy-bridged dimeric forms

[(VO)-O-IV(acac)(2)] reacts with an equimolar amount of benzoyl hydrazones of 2-hydroxyacetophenone (H2L1), 2-hydroxy-5-methylacetophenone (H2L2) and 5-chloro-2-hydroxyacetophenone (H2L4) in methanol to afford the penta-coordinated mixed-ligand methoxy bonded oxidovanadium(V) complexes [(VO)-O-V(L-1)-(OCHA(3))](1). [(VO)-O-V(L-2)(OCH3)](2), and [(VO)-O-V(L-4)(OCH3)](4), respectively, whereas, the similar reaction with the benzoyl hydrazone of 2-hydroxy-5-methoxyacetophenone (H2L3) producing only the hexa-coordinated dimethoxy-bridged dimeric complex [(VO)-O-V(L-3)(OCH3)](2) (3A). Similar type of hexa-coordinated dimeric analogue of 1 i.e., [(VO)-O-V(L-1)(OCH3)](2) (1A) was obtained from the reaction of [(VO)-O-IV(acac)(2)] with the equimolar amount of H2L1 in presence of half equivalent 4,4'-bipyridine in methanol while the decomposition of [(VO)-O-IV(L-2)(bipy)] complex in methanol afforded the dimeric analogue of 2 i.e., [(VO)-O-V(L-2)(OCH3)](2) (2A). All these dimeric complexes 1A-3A react with an excess amount of imidazole in methanol producing the respective monomeric complex. The X-ray structural analysis of 1-3 and their dimeric analogues 1A-3A indicates that the geometry around the vanadium center in the monomeric form is distorted square-pyramidal while that of their respective dimeric forms is distorted octahedral, where the ligands are bonded to vanadium meridionally in their fully deprotonated enol forms. Due to the formation of bridge, the V-O(methoxy) bond in the dimeric complexes is lengthened to such an extent that it becomes equal in length with the V-O(phenolate) bond in 3A and even longer in 1A and 2A, which is unprecedented. The H-1 NMR spectra of the complexes 1A-3A in CDCl3 solution, indicates that these dimeric complexes are converted appreciably into their respective monomeric form. Complexes are electro-active displaying one quasi-reversible reduction peak near +0.25 V versus SCE in CH2Cl2 solution. The E-1/2 values of the complexes show linear relationship with the Hammett parameter (sigma) of the substituents. All these VO3+-complexes are converted to the corresponding complexes with V2O34+ motif simply on refluxing them in acetone and to the complexes with VO2+ motif on reaction with 2 KOH in methanol. (C) 2008 Elsevier Ltd. All rights reserved.

Use of a reduced Schiff-Base ligand to prepare novel chloro-bridged chains of rare Cu(II) trinuclear complexes with mixed azido/oxo and chloro/oxo bridges

Two mixed bridged one-dimensional (1D) polynuclear complexes, [Cu3L2(mu(1,1)-N-3)(2)(mu-Cl)Cl](n) (1) and {[Cu3L2(mu-Cl)(3)Cl]center dot 0.46CH(3)OH}(n), (2), have been synthesized using the tridentate reduced Schiff-base ligand HL (2-[(2-dimethylamino-ethylamino)-methyl]-phenol). The complexes have been characterized by X-ray structural analyses and variable-temperature magnetic susceptibility measurements. In both complexes the basic trinuclear angular units are joined together by weak chloro bridges to form a 1D chain. The trinuclear structure of 1 is composed of two terminal square planar [Cu(L)(mu(1,1)-N-3)] units connected by a central Cu(II) atom through bridging nitrogen atoms of end-on azido ligands and the phenoxo oxygen atom of the tridentate ligand. These four coordinating atoms along with a chloride ion form a distorted trigonal bipyramidal geometry around the central Cu(II). The structure of 2 is similar; the only difference being a Cl bridge replacing the mu(1,1)-N-3 bridge in the trinuclear unit. The magnetic properties of both trinuclear complexes can be very well reproduced with a simple linear symmetrical trimer model (H = JS(i)S(i+1)) with only one intracluster exchange coupling (J) including a weak intertrimer interaction (.j) reproduced with the molecular field approximation. This model provides very satisfactory fits for both complexes in the whole temperature range with the following parameters: g = 2.136(3), J = 93.9(3) cm(-1) and zj= -0.90(3) cm(-1) (z = 2) for 1 and g = 2.073(7), J = -44.9(4) cm(-1) and zJ = -1.26(6) cm(-1) (z = 2) for 2.

Optimal control of a class of discrete–continuous non-linear systems — decomposition and hierarchical structure

A technique is derived for solving a non-linear optimal control problem by iterating on a sequence of simplified problems in linear quadratic form. The technique is designed to achieve the correct solution of the original non-linear optimal control problem in spite of these simplifications. A mixed approach with a discrete performance index and continuous state variable system description is used as the basis of the design, and it is shown how the global problem can be decomposed into local sub-system problems and a co-ordinator within a hierarchical framework. An analysis of the optimality and convergence properties of the algorithm is presented and the effectiveness of the technique is demonstrated using a simulation example with a non-separable performance index.

Minimum norm regularization of descriptor systems by mixed output feedback

We study the regularization problem for linear, constant coefficient descriptor systems Ex' = Ax+Bu, y1 = Cx, y2 = Γx' by proportional and derivative mixed output feedback. Necessary and sufficient conditions are given, which guarantee that there exist output feedbacks such that the closed-loop system is regular, has index at most one and E+BGΓ has a desired rank, i.e., there is a desired number of differential and algebraic equations. To resolve the freedom in the choice of the feedback matrices we then discuss how to obtain the desired regularizing feedback of minimum norm and show that this approach leads to useful results in the sense of robustness only if the rank of E is decreased. Numerical procedures are derived to construct the desired feedback gains. These numerical procedures are based on orthogonal matrix transformations which can be implemented in a numerically stable way.

The role of sky conditions on gross primary production in a mixed deciduous forest

The role of different sky conditions on diffuse PAR fraction (ϕ), air temperature (Ta), vapor pressure deficit (vpd) and GPP in a deciduous forest is investigated using eddy covariance observations of CO2 fluxes and radiometer and ceilometer observations of sky and PAR conditions on hourly and growing season timescales. Maximum GPP response occurred under moderate to high PAR and ϕ and low vpd. Light response models using a rectangular hyperbola showed a positive linear relation between ϕ and effective quantum efficiency (α = 0.023ϕ + 0.012, r2 = 0.994). Since PAR and ϕ are negatively correlated, there is a tradeoff between the greater use efficiency of diffuse light and lower vpd and the associated decrease in total PAR available for photosynthesis. To a lesser extent, light response was also modified by vpd and Ta. The net effect of these and their relation with sky conditions helped enhance light response under sky conditions that produced higher ϕ. Six sky conditions were classified from cloud frequency and ϕ data: optically thick clouds, optically thin clouds, mixed sky (partial clouds within hour), high, medium and low optical aerosol. The frequency and light responses of each sky condition for the growing season were used to predict the role of changing sky conditions on annual GPP. The net effect of increasing frequency of thick clouds is to decrease GPP, changing low aerosol conditions has negligible effect. Increases in the other sky conditions all lead to gains in GPP. Sky conditions that enhance intermediate levels of ϕ, such as thin or scattered clouds or higher aerosol concentrations from volcanic eruptions or anthropogenic emissions, will have a positive outcome on annual GPP, while an increase in cloud cover will have a negative impact. Due to the ϕ/PAR tradeoff and since GPP response to changes in individual sky conditions differ in sign and magnitude, the net response of ecosystem GPP to future sky conditions is non-linear and tends toward moderation of change.

The effect of adding stinging nettle (Urtica dioica) haylage to a total mixed ration on performance and rumen function of lactating dairy cows

In vitro studies found that inclusion of dried stinging nettle (Urtica dioica) at 100 mg/g dry matter (DM) increased the pH of a rumen fluid inoculated fermentation buffer by 30% and the effect was persistent for 7 days. Our objective was to evaluate the effects of adding stinging nettle haylage to a total mixed ration on feed intake, eating and rumination activity, rumen pH, milk yield, and milk composition of lactating dairy cows. Six lactating Holstein-Friesian cows were used in a replicated 3 × 3 Latin Square design experiment with 3 treatments and 3 week periods. Treatments were a control (C) high-starch (311 g/kg DM) total mixed ration diet and two treatment diets containing 50 (N5) and 100 (N10) g nettle haylage (DM/kg) as a replacement for ryegrass silage (Lolium perenne). There was an increase (linear, P < 0.010) in the proportion of large particles and a reduction in medium (linear, P = 0.045) and fine particles (linear, P = 0.026) in the diet offered with increasing nettle inclusion. A numerical decrease (linear, P = 0.106) in DM intake (DMI) was observed as nettle inclusion in the diet increased. Milk yield averaged 20.3 kg/day and was not affected by diet. There was a decrease (quadratic, P = 0.01) in the time animals spent ruminating as nettle inclusion in the diet increased, in spite of an increase in the number of boli produced daily for the N5 diet (quadratic, P = 0.031). Animals fed the N10 diet spent less time with a rumen pH below 5.5 (P < 0.05) than cows fed the N5 diet. Averaged over an 8.5 h sampling period, there were no changes in the concentration or proportions of acetate or propionate in the rumen, but feeding nettle haylage reduced the concentrations of n-butyrate (quadratic, P < 0.001), i-butyrate (linear, P < 0.009) and n-caproate (linear, P < 0.003). Milk and fat and protein corrected milk yield were not affected when nettles replaced ryegrass silage in the diet of lactating dairy cows, despite a numerical reduction in feed intake. Rumination activity was reduced by the addition of nettle haylage to the diet, which may reflect differences in fibre structure between the nettle haylage and ryegrass silage fed. Changes observed in rumen pH suggest potential benefits of feeding nettle haylage for reducing rumen acidosis. However, the extent to which these effects were due to the fermentability and structure of the nettle haylage compared to the ryegrass silage fed, or a bioactive component of the nettles, is not certain

Software-based study of a non-sorting method for median calculation on a set of integer numbers

This paper presents a software-based study of a hardware-based non-sorting median calculation method on a set of integer numbers. The method divides the binary representation of each integer element in the set into bit slices in order to find the element located in the middle position. The method exhibits a linear complexity order and our analysis shows that the best performance in execution time is obtained when slices of 4-bit in size are used for 8-bit and 16-bit integers, in mostly any data set size. Results suggest that software implementation of bit slice method for median calculation outperforms sorting-based methods with increasing improvement for larger data set size. For data set sizes of N > 5, our simulations show an improvement of at least 40%.

Bit-index sort: a fast non-comparison integer sorting algorithm for permutations

This paper describes a fast integer sorting algorithm, herein referred as Bit-index sort, which is a non-comparison sorting algorithm for partial per-mutations, with linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers supported by machine hardware to retrieve the ordered output sequence. Results show that Bit-index sort outperforms in execution time to quicksort and counting sort algorithms. A parallel approach for Bit-index sort using two simultaneous threads is included, which obtains speedups up to 1.6.