A time-efficient pattern reduction algorithm for k-means clustering

This paper presents an efficient algorithm, called pattern reduction (PR), for reducing the computation time of k-means and k-means-based clustering algorithms. The proposed algorithm works by compressing and removing at each iteration patterns that are unlikely to change their membership thereafter. Not only is the proposed algorithm simple and easy to implement, but it can also be applied to many other iterative clustering algorithms such as kernel-based and population-based clustering algorithms. Our experiments—from 2 to 1000 dimensions and 150 to 10,000,000 patterns—indicate that with a small loss of quality, the proposed algorithm can significantly reduce the computation time of all state-of-the-art clustering algorithms evaluated in this paper, especially for large and high-dimensional data sets.     

A graph-theoretic model for optimizing queries involving methods

Traditional algorithms for optimizing the execution order of joins are no more valid when selections and projections involve methods and become very expensive operations. Selections and projections could be even more costly than joins such that they are pulled above joins, rather than pushed down in a query tree. In this paper, we take a fundamental look at how to approach query optimization from a top-down design perspective, rather than trying to force one model to fit into another. We present a graph model which is designed to characterize execution plans. Each edge and each vertex of the graph is assigned a weight to model execution plans. We also design algorithms that use these weights to optimize the execution order of operations. A cost model of these algorithms is developed. Experiments are conducted on the basis of this cost model. The results show that our algorithms are superior to similar work proposed in the literature. Received 20 April 1999 / Accepted 9 August 2000 Published online 20 April 2001     

A cluster validity measure with outlier detection for support vector clustering

This paper focuses on the development of an effective cluster validity measure with outlier detection and cluster merging algorithms for support vector clustering (SVC). Since SVC is a kernel-based clustering approach, the parameter of kernel functions and the soft-margin constants in Lagrangian functions play a crucial role in the clustering results. The major contribution of this paper is that our proposed validity measure and algorithms are capable of identifying ideal parameters for SVC to reveal a suitable cluster configuration for a given data set. A validity measure, which is based on a ratio of cluster compactness to separation with outlier detection and a cluster-merging mechanism, has been developed to automatically determine ideal parameters for the kernel functions and soft-margin constants as well. With these parameters, the SVC algorithm is capable of identifying the optimal number of clusters with compact and smooth arbitrary-shaped cluster contours for the given data set and increasing robustness to outliers and noise. Several simulations, including artificial and benchmark data sets, have been conducted to demonstrate the effectiveness of the proposed cluster validity measure for the SVC algorithm.     

Moving cast shadow detection by exploiting multiple cues

Background subtraction or temporal differencing is commonly applied on an image sequence for foreground/background segmentation. However, cast shadows of moving foreground objects in a scene often result in detection errors for many vision-based applications. To address this problem, the authors propose an algorithm exploiting the information of colour, shading, texture, neighbourhood and temporal consistency to detect shadows efficiently and adaptively. The experimental results show that the proposed method can detect the penumbra as well as the umbra in different kinds of scenarios under various illumination conditions.     

Multi-objective decision-making methodology to create an optimal design chain partner combination

In today’s highly competitive business environment, many companies adopt the time-to-market strategy to obtain a competitive advantage. To reduce the time and cost of product development and to employ global product development resources, design chain partner evaluation and selection has become a crucial issue. Thus, establishing an optimal design chain partner combination has received significant attention because it has a far-reaching effect on the results of product development. With this perspective, this paper develops an integrated decision-making methodology to assist enterprises as they create an optimal design chain partner combination. First, this study establishes the framework and evaluation models of the criteria for the different roles of design chain partners, including system integration, functional module development and software and component development. Then, this paper applies a weight-restricted DEA (data envelopment analysis) approach to create the models for performance analysis of design chain partners to acquire the performance value of each candidate and select the efficient design chain partners. Moreover, this paper employs the multi-objective performance evaluation model proposed in this paper to analyze the synthesized performance of design chain combinations. Moreover, this research uses a multi-objective genetic algorithm (GA) to search efficiently for the optimal design chain partner combination to minimize product development cost and time and maximize product reliability. Finally, this study employs a derivative new product development project for a digital TV box as a case study to illustrate the efficacy of the proposed methodology.     

Soft syntactic constraints for Arabic–English hierarchical phrase-based translation

In adding syntax to statistical machine translation, there is a tradeoff between taking advantage of linguistic analysis and allowing the model to exploit parallel training data with no linguistic analysis: translation quality versus coverage. A number of previous efforts have tackled this tradeoff by starting with a commitment to linguistically motivated analyses and then finding appropriate ways to soften that commitment. We present an approach that explores the tradeoff from the other direction, starting with a translation model learned directly from aligned parallel text, and then adding soft constituent-level constraints based on parses of the source language. We argue that in order for these constraints to improve translation, they must be fine-grained: the constraints should vary by constituent type, and by the type of match or mismatch with the parse. We also use a different feature weight optimization technique, capable of handling large amount of features, thus eliminating the bottleneck of feature selection. We obtain substantial improvements in performance for translation from Arabic to English.     

Thermal resistance analysis and validation of flip chip PBGA packages

This work proposes a finite element numerical methodology to predict the thermal resistance of both flip chip-plastic ball grid array (FC-PBGA) with a bare die and FC-PBGA with a metal cap. The 3D finite element model was initially constructed to simulate the thermal resistance of FC-PBGA. A thermal resistance experiment was performed to verify the FEM results, following the construction of specimens of FC-PBGA with a bare die and with an aluminum cap, using six-layered substrate. The verified finite element model was employed to determine the thermal resistance of FC-PBGA with a copper cap using four-layered and six-layered substrates. Experimental results demonstrated that FC-PBGA with a metal cap improves thermal performance by 35% over with a bare die. FC-PBGA with a copper cap slightly improves thermal performance from 2% to 2.8% over that of FC-PBGA with an aluminum cap. The thermal resistance of FC-PBGA with a four-layered substrate is reduced by 4.0% to 5.9% from that of FC-PBGA with a six-layered substrate, since the four-layered substrate contains less metal. The finite element numerical results negligibly differ from the experimental results by 6% to 8.1%. A finite element numerical methodology is here proposed to predict the thermal resistance of FC-PBGA. The methodology is effective in researching and developing new products or improving existing packages.     

Progressive Simplification of Tetrahedral Meshes Preserving All Isosurface Topologies

In this paper, we propose a novel technique for constructing multiple levels of a tetrahedral volume dataset whilepreserving the topologies of all isosurfaces embedded in the data. Our simplification technique has two majorphases. In the segmentation phase, we segment the volume data into topological‐equivalence regions, that is, thesub‐volumes within each of which all isosurfaces have the same topology. In the simplification phase, we simplifyeach topological‐equivalence region independently, one by one, by collapsing edges from the smallest to the largesterrors (within the user‐specified error tolerance, for a given error metrics), and ensure that we do not collapseedges that may cause an isosurface‐topology change. We also avoid creating a tetrahedral cell of negative volume(i.e., avoid the fold‐over problem). In this way, we guarantee to preserve all isosurface topologies in the entiresimplification process, with a controlled geometric error bound. Our method also involves several additionalnovel ideas, including using the Morse theory and the implicit fully augmented contour tree, identifying typesof edges that are not allowed to be collapsed, and developing efficient techniques to avoid many unnecessary orexpensive checkings, all in an integrated manner. The experiments show that all the resulting isosurfaces preservethe topologies, and have good accuracies in their geometric shapes. Moreover, we obtain nice data‐reductionrates, with competitively fast running times.     

A new kernel-based fuzzy clustering approach: support vector clustering with cell growing

In this paper, the support vector clustering is extended to an adaptive cell growing model which maps data points to a high dimensional feature space through a desired kernel function. This generalized model is called multiple spheres support vector clustering, which essentially identifies dense regions in the original space by finding their corresponding spheres with minimal radius in the feature space. A multisphere clustering algorithm based on adaptive cluster cell growing method is developed, whereby it is possible to obtain the grade of memberships, as well as cluster prototypes in partition. The effectiveness of the proposed algorithm is demonstrated for the problem of arbitrary cluster shapes and for prototype identification in an actual application to a handwritten digit data set.     

Query optimization in multidatabase systems considering schemaconflicts

In a multidatabase system, the participating databases are autonomous. The schemas of these databases may be different in various ways, while the same information is represented. A global query issued against the global database needs to be translated to a proper form before it can be executed in a local database. Since data requested by a query (or a part of a query) is sometimes available in multiple sites, the site (database) that processes the query with the least cost is the desired query processing site. The authors study the effect of differences in schemas on the cost of query processing in a multidatabase environment. They first classify schema conflicts to different types. For each type of conflict, they show how much more or less complex a translated query can become in comparison with the originally user-issued global query. Based on this observation, they propose an analytical method that considers the conflicts between local databases and finds the database(s) that renders the least execution cost in processing a global query. This research introduces a new level of query optimization (termed the schema-level optimization) in multidatabase environments. The results provide a new dimension of enhancement for the capability of a query optimizer in multidatabase systems