Subspace clustering has attracted great attention due to its capability of finding salient patterns in high dimensional data. Order preserving subspace clusters have been proven to be important in high throughput gene expression analysis, since functionally related genes are often co-expressed under a set of experimental conditions. Such co-expression patterns can be represented by consistent orderings of attributes. Existing order preserving cluster models require all objects in a cluster have identical attribute order without deviation. However, real data are noisy due to measurement technology limitation and experimental variability which prohibits these strict models from revealing true clusters corrupted by noise. In this paper, we study the problem of revealing the order preserving clusters in the presence of noise. We propose a noise-tolerant model called approximate order preserving cluster (AOPC). Instead of requiring all objects in a cluster have identical attribute order, we require that (1) at least a certain fraction of the objects have identical attribute order; (2) other objects in the cluster may deviate from the consensus order by up to a certain fraction of attributes. We also propose an algorithm to mine AOPC. Experiments on gene expression data demonstrate the efficiency and effectiveness of our algorithm.

As shown in literatures, partial reluctance based circuit analysis is efficient in capturing on-chip inductance effect, because the partial reluctance exhibits much better locality than partial inductance. However, most previous works on reluctance extraction did not take high frequency effect into account and were not efficient enough for 3D complex structure. In this paper, a new reluctance extraction algorithm is proposed considering the high frequency effect. Numerical experiments demonstrate that our algorithm can handle complex 3D interconnect structures while exhibiting high accuracy and a speed-up ratio of several tens to hundreds over FastHenry.

Inserting dummy (area fill) metals is necessary to reduce the pattern-dependent variation of dielectric thickness in the chemical-mechanical polishing (CMP) process. Such floating dummy metals affect interconnect capacitance and, therefore, signal delay and crosstalk significantly. To take the floating dummies into account, an efficient method for three-dimensional (3-D) capacitance extraction based on boundary element method is proposed. By introducing a floating condition into the direct boundary integral equation (BIE) and adopting an efficient preconditioning technique, and the quasi-multiple medium (QMM) acceleration, the method achieves very high computational speed. For some typical structures of area fill, the presented algorithm has shown over 1000/spl times/ speedup over the industry-standard Raphael while preserving high accuracy. Compared with the recently proposed PASCAL in the work of Park et al. (2000), the proposed method also has about ten times speedup. Since the dummies are not regarded as normal electrodes in capacitance extraction, the proposed method is much more efficient than the conventional method, especially in cases with a large number of floating dummies.