17795196
Scalable model-based clustering by working on data summaries
The scalability problem in data mining involves the development of methods for handling large databases with limited computational resources. We present a two-phase scalable model-based clustering framework: first, a large data set is summed up into subclusters; Then, clusters are directly generated from the summary statistics of subclusters by a specifically designed expectation-maximization (EM) algorithm. Taking example for Gaussian mixture models, we establish a provably convergent EM algorithm, EMADS, which embodies cardinality, mean, and covariance information of each subcluster explicitly. Combining with different data summarization procedures, EMADS is used to construct two clustering systems: gEMADS and bEMADS. The experimental results demonstrate that they run several orders of magnitude faster than the classic EM algorithm with little loss of accuracy. They generate significantly better results than other model-based clustering systems using similar computational resources.
491232
A novel evolutionary drug scheduling model in cancer chemotherapy
In this paper, we introduce a modified optimal control model of drug scheduling in cancer chemotherapy and a new adaptive elitist-population-based genetic algorithm (AEGA) to solve it. Working closely with an oncologist, we first modify the existing model, because its equation for the cumulative drug toxicity is inconsistent with medical knowledge and clinical experience. To explore multiple efficient drug scheduling policies, we propose a novel variable representation-a cycle-wise representation, and modify the elitist genetic search operators in the AEGA. The simulation results obtained by the modified model match well with the clinical treatment experiences, and can provide multiple efficient solutions for oncologists to consider. Moreover, it has been shown that the evolutionary drug scheduling approach is simple, and capable of solving complex cancer chemotherapy problems by adapting multimodal versions of evolutionary algorithms
6136966
Operation Shipping for Mobile File Systems
This paper addresses a bottleneck problem in mobile file systems: the propagation of updated large tiles from a weakly-connected client to its servers. It proposes an efficient mechanism called operation shipping or operation-based update propagation. In the new mechanism, the client ships the user operation that updated the large files, rather than the files themselves, across the weak network. (in contrast, existing file systems use value shipping and ship the files.) The user operation is sent to a surrogate client that is strongly connected to the servers. The surrogate replays the user operation, regenerates the files, checks whether they are identical to the originals, and, it so, sends the files to the servers on behalf of the client. Care has been taken such that the new mechanism does not compromise correctness or server scalability. For example, we show how forward error correction (FEC) can restore minor reexecution discrepancies and, thus, make operation shipping work with more applications. Operation shipping can be further classified into two types: application-transparent and application-aware. Their feasibilities and benefits have been demonstrated by the design, implementation, and evaluation of a prototype extension to the Coda File System. In our controlled experiments, operation shipping achieved substantial performance improvements-network traffic reductions from 12 times to nearly 400 times and speedups in the range of 1.4 times to nearly 50 times.
6747363
A Stochastic Load Balancing Algorithm for Internet Computing Environment
18141920
Learning functional dependency networks based on genetic programming
Bayesian Network (BN) is a powerful network model, which represents a set of variables in the domain and provides the probabilistic relationships among them. But BN can handle discrete values only; it cannot handle continuous, interval and ordinal ones, which must be converted to discrete values and the order information is lost. Thus, BN tends to have higher network complexity and lower understandability. In this paper, we present a novel dependency network which can handle discrete, continuous, interval and ordinal values through functions; it has lower network complexity and stronger expressive power; it can represent any kind of relationships; and it can incorporate a-priori knowledge though user-defined functions. We also propose a novel Genetic Programming (GP) to learn dependency networks. The novel GP does not use any knowledge-guided nor application-oriented operator, thus it is robust and easy to replicate. The experimental results demonstrate that the novel GP can successfully discover the target novel dependency networks, which have the highest accuracy and the lowest network complexity.
320235
Handling signature purposes in workflow systems
Abstract In paper-based workflow systems, signatures of individuals or groups of people have been used extensively for different purposes. Currently there are numerous studies on computerizing workflow systems. Also there are studies on implementing digital signatures in electronic media. But the diversified purposes of a signature in workflow makes a straightforward implementation of digital signature schemes inadequate. There are few studies on the implication of different signature purposes on electronic workflow systems. The purposes of signature are closely associated with the two modes of decision making, namely single and group. These two modes of decision making in turn lead to single and group signatures. This paper reports our comprehensive studies on signature purposes. These include the analysis of common signature purposes in workflow, classification of these purposes, classification of modes of decision making associated with these signature purposes, signing and validation requirements for handling these signature purposes, and finally an architecture to be incorporated in workflow engines for handling these signature purposes. In summary, this paper addresses a commonly neglected problem in information systems research: management control by signature in workflow.
588086
Calculating normalization constants of closed queueing networks by numerically inverting their generating functions
A new algorithm is developed for calculating normalization constants (partition functions) and moments of product-form steady-state distributions of closed queuing networks and related models. The essential idea is to numerically invert the generating function of the normalization constant and related generating functions appearing in expressions for the moments. It is known that the generating function of the normalization constant often has a remarkably simple form, but numerical inversion evidently has not been considered before. For p-dimensional transforms, as occur with queuing networks having p closed chains, the algorithm recursively performs p one-dimensional inversions. The required computation grows exponentially in the dimension, but the dimension can often be reduced by exploiting conditional decomposition based on special structure. For large populations, the inversion algorithm is made more efficient by computing large sums using Euler summation. The inversion algorithm also has a very low storage requirement. A key ingredient in the inversion algorithm is scaling. An effective static scaling is developed for multichain closed queuing networks with only single-server and (optionally) infinite-server queues. An important feature of the inversion algorithm is a self-contained accuracy check, which allows the results to be verified in the absence of alternative algorithms.
14053268
Data Synchronization Methods Based on ShuffleNet and Hypercube for Networked Information Systems
In contrast to a typical single source of data updates in Internet applications, data files in a networked information system are often distributed, replicated, accessed and updated by multiple nodes. Due to concurrent updates, replicated data files must be synchronized. For certain applications, stringent concurrency control must be employed to ensure data integrity, while for other applications, periodic data synchronization may enable very efficient data sharing. For the latter applications, this paper devises the ShuffleNet and hypercube schemes for data synchronization in such networked information systems. Their performance in terms of update delay, processing complexity, failure tolerance and growth complexity is examined. Our results reveal that the ShuffleNet and hypercube scheme provide identical maximum update delay and similar processing complexity. However, as the number of nodes in the system changes (e.g., due to failure or temporary out of service for maintenance), the hypercube scheme maintains all existing synchronization sessions and greatly simplifies system administration overhead such as moving files from node to node for the purpose of data synchronization. The ShuffleNet scheme does provide a higher degree of failure tolerance for global data files, but the hypercube scheme provides more than adequate failure tolerance. Lastly, a generalization of the hypercube scheme, based on the ideas of shift registers, is also proposed for systems where the number of nodes is a perfect power of 2.
2298581
Global Mobility Management by Replicated Databases in Personal Communication Networks
This paper explores the use of replicated databases for management of customer data (e.g., mobility data, call routing logic) in global, intelligent, and wireless networks. We propose and analyze two, full and partial, data replication schemes-which are compatible with industry protocol standards-and compare them with the traditional, centralized database scheme. By identifying a set of key teletraffic and mobility parameters, we develop a modeling framework based on queueing models and apply it to assess the relative performance and merits of these schemes. The paper also addresses some implementation issues. Numerical results reveal that the full replication scheme outperforms the centralized one over a wide range of the parameters considered in this study. Furthermore, if some customer data-such as location data for highly mobile customers in wireless networks-change frequently, and if each call launches multiple queries into the databases, the partial replication scheme offers further performance improvement. In general, however, the choice of the database design would depend on the specific characteristics of the service and user behavior under consideration.
28941391
Optimum nested Miller compensation for low-voltage low-power CMOS amplifier design
An optimum structure of nested Miller compensation (NMC) is developed. The developed structure using a feedforward transconductance stage and null resistor on NMC, called NMCFNR, solves the bandwidth reduction and poor transient response problems of low-voltage low-power NMC amplifiers. For comparison, amplifiers compensated by NMC and NMCFNR have been fabricated. Experimental results show that NMCFNR improves the gain-bandwidth product, slew rate and settling time by more than three times with 8/spl deg/ increase on the phase margin and no increase of the power consumption. Moreover, it improves the negative power supply rejection ratio by at least 54 dB. The die area of the NMCFNR amplifier is about half of that of the NMC amplifier.