A dynamic model for short-term prediction of stream attributes

Multiple data streams coming out of a complex system form the observable state of the system. The streams may correspond to various sensors attached with the system or outcome of internal processes. Such stream data may consist of multiple attributes and may differ in terms of their frequency of generation and observation. The streams may have dependency among themselves. One will have to rely on such data streams for monitoring the health of the system or to take any corrective measure. Predicting the value of certain stream data is an important task that can help one to take decision and act accordingly. In this work, a simple but generic visualization of a complex system is presented and thereafter a linear regression-based dynamic model for short-term prediction is proposed. The model is based on the past history of the attributes of multiple streams as suggested by the domain experts. But, it automatically determines the meaningful attributes and reformulates the model. The model is also re-computed if the prediction error exceeds the allowable tolerance. All these make the model dynamic. Experiment is carried out with stock market data streams to predict the close value well in advance. It is observed that in terms of quality of prediction and performance metric, the proposed model is quite effective.     

Autonomous clustering using rough set theory

This paper proposes a clustering technique that minimizes the need for subjective human intervention and is based on elements of rough set theory （RST）. The proposed algorithm is unified in its approach to clustering and makes use of both local and global data properties to obtain clustering solutions. It handles single-type and mixed attribute data sets with ease. The results from three data sets of single and mixed attribute types are used to illustrate the technique and establish its efficiency.     

Solving shortest path problem using particle swarm optimization

This paper presents the investigations on the application of particle swarm optimization (PSO) to solve shortest path (SP) routing problems. A modified priority-based encoding incorporating a heuristic operator for reducing the possibility of loop-formation in the path construction process is proposed for particle representation in PSO. Simulation experiments have been carried out on different network topologies for networks consisting of 15–70 nodes. It is noted that the proposed PSO-based approach can find the optimal path with good success rates and also can find closer sub-optimal paths with high certainty for all the tested networks. It is observed that the performance of the proposed algorithm surpasses those of recently reported genetic algorithm based approaches for this problem.     

Spatial interest pixels (SIPs): useful low-level features of visual media data

Visual media data such as an image is the raw data representation for many important applications. Reducing the dimensionality of raw visual media data is desirable since high dimensionality degrades not only the effectiveness but also the efficiency of visual recognition algorithms. We present a comparative study on spatial interest pixels (SIPs), including eight-way (a novel SIP detector), Harris, and Lucas‐Kanade, whose extraction is considered as an important step in reducing the dimensionality of visual media data. With extensive case studies, we have shown the usefulness of SIPs as low-level features of visual media data. A class-preserving dimension reduction algorithm (using GSVD) is applied to further reduce the dimension of feature vectors based on SIPs. The experiments showed its superiority over PCA.

Optimum image thresholding via class uncertainty and regionhomogeneity

Thresholding is a popular image segmentation method that converts a gray-level image into a binary image. The selection of optimum thresholds has remained a challenge over decades. Besides being a segmentation tool on its own, often it is also a step in many advanced image segmentation techniques in spaces other than the image space. We introduce a thresholding method that accounts for both intensity-based class uncertainty-a histogram-based property-and region homogeneity-an image morphology-based property. A scale-based formulation is used for region homogeneity computation. At any threshold, intensity-based class uncertainty is computed by fitting a Gaussian to the intensity distribution of each of the two regions segmented at that threshold. The theory of the optimum thresholding method is based on the postulate that objects manifest themselves with fuzzy boundaries in any digital image acquired by an imaging device. The main idea here is to select that threshold at which pixels with high class uncertainty accumulate mostly around object boundaries. To achieve this, a threshold energy criterion is formulated using class-uncertainty and region homogeneity such that, at any image location, a high energy is created when both class uncertainty and region homogeneity are high or both are low. Finally, the method selects that threshold which corresponds to the minimum overall energy. The method has been compared to a maximum segmented image information method. Superiority of the proposed method was observed both qualitatively on clinical medical images as well as quantitatively on 250 realistic phantom images generated by adding different degrees of blurring, noise, and background variation to real objects segmented from clinical images     

A stability-based distributed routing mechanism to support unicast and multicast routing in ad hoc wireless network

An ad hoc network can be envisioned as a collection of mobile routers, each equipped with a wireless transceiver, which are free to move about arbitrarily. In ad hoc wireless networks, even if two nodes are outside the wireless transmission range of each other, they may still be able to communicate in multiple hops using other intermediate nodes. However, the dynamics of these networks, as a consequence of mobility and disconnection of mobile hosts, pose a number of problems in designing routing schemes for effective communication between any pair of source and destination. In this paper, a stability-based unicast routing mechanism, that considers both link affinity and path stability in order to find out a stable route from source to destination, is proposed. It is then extended to support multicast routing as well where only local state information (at source) is utilized for constructing a multicast tree. The performance of the proposed scheme is evaluated on a simulated environment to show that the stability-based scheme provides a unified framework for both unicast and multicast routing and reduces the probability of route error drastically in both the cases.     

Reducing the overhead of dynamic compilation

The execution model for mobile, dynamically‐linked, object‐oriented programs has evolved from fast interpretation to a mix of interpreted and dynamically compiled execution. The primary motivation for dynamic compilation is that compiled code executes significantly faster than interpreted code. However, dynamic compilation, which is performed while the application is running, introduces execution delay. In this paper we present two dynamic compilation techniques that enable high performance execution while reducing the effect of this compilation overhead. These techniques can be classified as (1) decreasing the amount of compilation performed, and (2) overlapping compilation with execution. We first present and evaluate lazy compilation, an approach used in most dynamic compilation systems in which individual methods are compiled on‐demand upon their first invocation. This is in contrast to eager compilation, in which all methods in a class are compiled when a new class is loaded. In this work, we describe our experience with eager compilation, as well as the implementation and transition to lazy compilation. We empirically detail the effectiveness of this decision. Our experimental results using the SpecJVM Java benchmarks and the Jalapeño JVM show that, compared to eager compilation, lazy compilation results in 57% fewer methods being compiled and reductions in total time of 14 to 26%. Total time in this context is compilation plus execution time. Next, we present profile‐driven, background compilation, a technique that augments lazy compilation by using idle cycles in multiprocessor systems to overlap compilation with application execution. With this approach, compilation occurs on a thread separate from that of application threads so as to reduce intermittent, and possibly substantial, delay in execution. Profile information is used to prioritize methods as candidates for background compilation. Methods are compiled according to this priority scheme so that performance‐critical methods are invoked using optimized code as soon as possible. Our results indicate that background compilation can achieve the performance of off‐line compiled applications and masks almost all compilation overhead. We show significant reductions in total time of 14 to 71% over lazy compilation. Copyright © 2001 John Wiley & Sons, Ltd.     

Amounts of nondeterminism in finite automata

Summary The amount of nondeterminism in a nondeterministic finite automaton (NFA) is measured by counting the minimal number of guessing points a string w has to pass through on its way to an accepting state. NFA's with more nondeterminism can achieve greater savings in the number of states over their deterministic counterparts than NFA's with less nondeterminism. On the other hand, for some nontrivial infinite regular languages a deterministic finite automaton (DFA) can already be quite succinct in the sense that NFA's need as many states (and even context-free grammars need as many nonterminals) as the minimal DFA has states.This research was supported in part by the National Science Foundation under Grant No. MCS 76-10076     

Strict interpretations of deterministic pushdown acceptors

Three results are established. The first is that every nondeterministic strict interpretation of a deterministic pushdown acceptor (dpda) has an equivalent, deterministic, strict interpretation. The second is that ifM ₁ andM ₂ are two compatible strict interpretations of the dpdaM, then there exist deterministic strict interpretationsM andM such thatL(M ) =L(M ₁)L(M ₂) andL(M ) =L(M ₁)L(M ₂). The third states that there is no dpda whose strict interpretations yield all the deterministic context-free languages.This author was supported in part by the National Science Foundation under Grant MCS-77-22323.     

Pruning 2-Connected Graphs

Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of?G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log?nlog?k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac{1}{\epsilon}\log^{2} n)$ approximation, while violating the budget by a factor of at most 2+ε.