Dynamic subspace clustering for very large high-dimensional databases

Emerging high-dimensional data mining applications needs to find interesting clusters embeded in arbitrarily aligned subspaces of lower dimensionality. It is difficult to cluster high-dimensional data objects, when they are sparse and skewed. Updations are quite common in dynamic databases and they are usually processed in batch mode. In very large dynamic databases, it is necessary to perform incremental cluster analysis only to the updations. We present a incremental clustering algorithm for subspace clustering in very high dimensions, which handles both insertion and deletions of datapoints to the backend databases.

A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for ``near-feasibility'' of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. Note to Practitioners-Our results will be useful in all resource allocation problems that involve gathering of information privately held by strategic users, where the utilities are any concave function of the allocations, and where the resource planner is not interested in maximizing revenue, but in efficient sharing of the resource. Such situations arise quite often in fair sharing of internet resources, fair sharing of funds across departments within the same parent organization, auctioning of public goods, etc. We study methods to achieve near budget balance by first collecting payments according to the celebrated VCG mechanism, and then returning as much of the collected money as rebates. Our focus on linear rebate functions allows for easy implementation. The resulting convex optimization problem is solved via relaxation to a randomized linear programming problem, for which several efficient solvers exist. This relaxation is enabled by constraint sampling. Keeping practitioners in mind, we identify the number of samples that assures a desired level of ``near-feasibility'' with the desired confidence level. Our methodology will occasionally require subsidy from outside the system. We however demonstrate via simulation that, if the mechanism is repeated several times over independent instances, then past surplus can support the subsidy requirements. We also extend our results to situations where the strategic users' utility functions are not known to the allocating entity, a common situation in the context of internet users and other problems.

The Effect of Evacuated Backside Cavity on the Dynamic Characteristics of a Capacitive Micromachined Ultrasonic Transducer

In this paper, we investigate the effect of vacuum sealing the backside cavity of a Capacitive Micromachined Ultrasonic Transducer (CMUT). The presence or absence of air inside the cavity has a marked effect upon the system parameters, such as the natural frequency, damping, and the pull-in voltage. The presence of vacuum inside the cavity of the device causes a reduction in the effective gap height which leads to a reduction in the pull-in voltage. We carry out ANSYS simulations to quantify this reduction. The presence of vacuum inside the cavity of the device causes stress stiffening of the membrane, which changes the natural frequency of the device. A prestressed modal analysis is carried out to determine the change in natural frequency due to stress stiffening. The equivalent circuit method is used to evaluate the performance of the device in the receiver mode. The lumped parameters of the device are obtained and an equivalent circuit model of the device is constructed to determine the open circuit receiving sensitivity of the device. The effect of air in the cavity is included by incorporating an equivalent compliance and an equivalent resistance in the equivalent circuit.

Mathematical model of COREX melter gasifier: Part II. Dynamic model

A dynamic model of the COREX melter gasifier is developed to study the transient behavior of the furnace. The effect of pulse disturbance and step disturbance on the process performance has been studied. This study shows that the effect of pulse disturbance decays asymptotically. The step change brings the system to a new steady state after a delay of about 5 hours. The dynamic behavior of the melter gasifier with respect to a shutdown/blow-on condition and the effect of tapping are also studied. The results show that the time response of the melter gasifier is much less than that of a blast furnace.

The effect of T-stress on plane strain dynamic crack growth in elastic-plastic materials

In this paper, the effects of T -stress on steady, dynamic crack growth in an elastic-plastic material are examined using a modified boundary layer formulation. The analyses are carried out under mode I, plane strain conditions by employing a special finite element procedure based on moving crack tip coordinates. The material is assumed to obey the J (2) flow theory of plasticity with isotropic power law hardening. The results show that the crack opening profile as well as the opening stress at a finite distance from the tip are strongly affected by the magnitude and sign of the T -stress at any given crack speed. Further, it is found that the fracture toughness predicted by the analyses enhances significantly with negative T -stress for both ductile and cleavage mode of crack growth.

Pyrochlore ``dynamic spin-ice'' Pr(2)Sn(2)O(7) and monoclinic Pr(2)Ti(2)O(7): A comparative temperature-dependent Raman study

Here we report a temperature-dependent Raman study of the pyrochlore ``dynamic spin-ice'' compound Pr(2)Sn(2)O(7) and compare the results with its non-pyrochlore (monoclinic) counterpart Pr(2)Ti(2)O(7). In addition to phonon modes, we observe two bands associated with electronic Raman scattering involving crystal field transitions in Pr(2)Sn(2)O(7) at similar to 135 and 460 cm(-1) which couple strongly to phonons. Anomalous temperature dependence of phonon frequencies that are observed in Pyrochlore Pr(2)Sn(2)O(7) are absent in monoclinic Pr(2)Ti(2)O(7). This, therefore, confirms that the strong phonon-phonon anharmonic interactions, responsible for the temperature-dependent anomalous behavior of phonons, arise due to the inherent vacant sites in the pyrochlore structure. (C) 2011 Elsevier Inc. All rights reserved.

String-like propagation of the 5-coordinated defect state in supercooled water: molecular origin of dynamic and thermodynamic anomalies

We find that at low temperature water, large amplitude (similar to 60 degrees) rotational jumps propagate like a string, with the length of propagation increasing with lowering temperature. The strings are formed by mobile 5-coordinated water molecules which move like a Glarum defect (J. Chem. Phys., 1960, 33, 1371), causing water molecules on the path to change from 4-coordinated to 5-coordinated and again back to 4-coordinated water, and in the process cause the tagged water molecule to jump, by following essentially the Laage-Hynes mechanism (Science, 2006, 311, 832-835). The effects on relaxation of the propagating defect causing large amplitude jumps are manifested most dramatically in the mean square displacement (MSD) and also in the rotational time correlation function of the O-H bond of the molecule that is visited by the defect (transient transition to the 5-coordinated state). The MSD and the decay of rotational time correlation function, both remain quenched in the absence of any visit by the defect, as postulated by Glarum long time ago. We establish a direct connection between these propagating events and the known thermodynamic and dynamic anomalies in supercooled water. These strings are found largely in the regions that surround the relatively rigid domains of 4-coordinated water molecules. The propagating strings give rise to a noticeable dynamical heterogeneity, quantified here by a sharp rise in the peak of the four-point density response function, chi(4)(t). This dynamics heterogeneity is also responsible for the breakdown of the Stokes-Einstein relation.

A low power, process invariant keeper design for high speed dynamic logic circuits

A low power keeper circuit using the concept of rate sensing has been proposed. The proposed technique reduces the amount of short circuit power dissipation in the domino gate by 70% compared to the conventional keeper technique. Also the total power-delay product is 26% lower compared to the previously reported techniques. The process tracking capability of the design enables the domino gate to achieve uniform delay across different process corners. This reduces the amount of short circuit power dissipation that occurs in the cascaded domino gates by 90%. The use of the proposed technique in the read path of a register file reduces the energy requirement by 26% as compared to the other keeper techniques. The proposed technique has been prototyped in 130nm CMOS technology.

Size-dependent and strain rate effects in quantum dot nanostructures with molecular dynamic simulations

Size and strain rate effects are among several factors which play an important role in determining the response of nanostructures, such as their deformations, to the mechanical loadings. The mechanical deformations in nanostructure systems at finite temperatures are intrinsically dynamic processes. Most of the recent works in this context have been focused on nanowires [1, 2], but very little attention has been paid to such low dimensional nanostructures as quantum dots (QDs). In this contribution, molecular dynamics (MD) simulations with an embedded atom potential method(EAM) are carried out to analyse the size and strain rate effects in the silicon (Si) QDs, as an example. We consider various geometries of QDs such as spherical, cylindrical and cubic. We choose Si QDs as an example due to their major applications in solar cells and biosensing. The analysis has also been focused on the variation in the deformation mechanisms with the size and strain rate for Si QD embedded in a matrix of SiO2 [3] (other cases include SiN and SiC matrices).It is observed that the mechanical properties are the functions of the QD size, shape and strain rate as it is in the case for nanowires [2]. We also present the comparative study resulted from the application of different EAM potentials in particular, the Stillinger-Weber (SW) potential, the Tersoff potentials and the environment-dependent interatomic potential (EDIP) [1]. Finally, based on the stabilized structural properties we compute electronic bandstructures of our nanostructures using an envelope function approach and its finite element implementation.

Energy Reduction in SRAM using Dynamic Voltage and Frequency Management

This paper describes a dynamic voltage frequency control scheme for a 256 X 64 SRAM block for reducing the energy in active mode and stand-by mode. The DVFM control system monitors the external clock and changes the supply voltage and the body bias so as to achieve a significant reduction in energy. The behavioral model of the proposed DVFM control system algorithm is described and simulated in HDL using delay and energy parameters obtained through SPICE simulation. The frequency range dictated by an external controller is 100 MHz to I GHz. The supply voltage of the complete memory system is varied in steps of 50 mV over the range of 500 mV to IV. The threshold voltage range of operation is plusmn100 mV around the nominal value, achieving 83.4% energy reduction in the active mode and 86.7% in the stand-by mode. This paper also proposes a energy replica that is used in the energy monitor subsystem of the DVFM system.

Effects of phase inhomogeneity and boundary conditions on the dynamic response of SMA wire actuators

This paper reports the simulation results from the dynamic analysis of a Shape Memory Alloy (SMA) actuator. The emphasis is on understanding the dynamic behavior under various loading rates and boundary conditions, resulting in complex scenarios such as thermal and stress gradients. Also, due to the polycrystalline nature of SMA wires, presence of microstructural inhomogeneity is inevitable. Probing the effect of inhomogeneity on the dynamic behavior can facilitate the prediction of life and characteristics of SMA wire actuator under varieties of boundary and loading conditions. To study the effect of these factors, an initial boundary value problem of SMA wire is formulated. This is subsequently solved using finite element method. The dynamic response of the SMA wire actuator is analyzed under mechanical loading and results are reported. Effect of loading rate, micro-structural inhomogeneity and thermal boundary conditions on the dynamic response of SMA wire actuator is investigated and the simulation results are reported.

Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Dynamic matrix rank with partial lookahead

We consider the problem of maintaining information about the rank of a matrix $M$ under changes to its entries. For an $n \times n$ matrix $M$, we show an amortized upper bound of $O(n^{\omega-1})$ arithmetic operations per change for this problem, where $\omega < 2.376$ is the exponent for matrix multiplication, under the assumption that there is a {\em lookahead} of up to $\Theta(n)$ locations. That is, we know up to the next $\Theta(n)$ locations $(i_1,j_1),(i_2,j_2),\ldots,$ whose entries are going to change, in advance; however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner.