This paper introduces a hidden topic-based framework for processing short and sparse documents (e.g., search result snippets, product descriptions, book/movie summaries, and advertising messages) on the Web. The framework focuses on solving two main challenges posed by these kinds of documents: 1) data sparseness and 2) synonyms/homonyms. The former leads to the lack of shared words and contexts among documents while the latter are big linguistic obstacles in natural language processing (NLP) and information retrieval (IR). The underlying idea of the framework is that common hidden topics discovered from large external data sets (universal data sets), when included, can make short documents less sparse and more topic-oriented. Furthermore, hidden topics from universal data sets help handle unseen data better. The proposed framework can also be applied for different natural languages and data domains. We carefully evaluated the framework by carrying out two experiments for two important online applications (Web search result classification and matching/ranking for contextual advertising) with large-scale universal data sets and we achieved significant results.

The trade-off between resource efficiency and Quality of Service (QoS) is always a vital issue for communication networks, and link overbooking is a common technique used to improve resource efficiency. How to properly overbook a link and analytically determine its overbooking factor under QoS constraints are still problems, especially when achieving advanced QoS by per-flow queueing, as urged by the emerging mobilized applications in the access networks. This paper first proposes an Opportunistic Link Overbooking (OLO) scheme for an edge gateway to improve its link efficiency, and then develops an integrated analytical framework for determining the suitable link overbooking factor with service guarantee on flow level. In our scheme, once the idle time of a high priority flow's quasi-dedicated link is larger than a specified threshold, the link is temporarily overbooked to a low priority flow; and then when the high priority flow's subsequent packets start arriving, the link can be recovered at the expense of a setup delay. To explore the balance between link efficiency and the flow's QoS in the proposed scheme, we develop the corresponding queueing model under either bounded packet delay (relevant to delaysensitive flow) or finite buffer size (relevant to loss-sensitive flow). Our queueing analysis reveals the inherent trade-offs among the link overbooking factor, packet loss rate and delay/jitter under different traffic patterns.

The complexity of an interconnection network often determines the size of the parallel computer and thus the attainable performance of a parallel computer is limited by the characteristics of the interconnection network. Pruning technique reduces the complexity and hence increases the performance. In this paper, we apply the pruning technique on hierarchical torus network (HTN) and study the architectural details of the pruned HTN. We have explored the network diameter, average distance, bisection width, peak number of vertical links, and VLSI layout area of different HTN. It is shown that the pruned HTN possesses several attractive features including small diameter, small average distance, small number of wires, a particularly small number of vertical links, and economic layout area as compared to its non-pruned counterpart.

Web search clustering is a solution to reorganize search results (also called “snippets”) in a more convenient way for browsing. There are three key requirements for such post-retrieval clustering systems: (1) the clustering algorithm should group similar documents together; (2) clusters should be labeled with descriptive phrases; and (3) the clustering system should provide high-quality clustering without downloading the whole Web page. This article introduces a novel framework for clustering Web search results in Vietnamese which targets the three above issues. The main motivation is that by enriching short snippets with hidden topics from huge resources of documents on the Internet, it is able to cluster and label such snippets effectively in a topic-oriented manner without concerning whole Web pages. Our approach is based on recent successful topic analysis models, such as Probabilistic-Latent Semantic Analysis, or Latent Dirichlet Allocation. The underlying idea of the framework is that we collect a very large external data collection called “universal dataset,” and then build a clustering system on both the original snippets and a rich set of hidden topics discovered from the universal data collection. This can be seen as a richer representation of snippets to be clustered. We carry out careful evaluation of our method and show that our method can yield impressive clustering quality.

Optical buffering is fundamental to contention resolution in optical networks. The current works on this line mainly focus on the emulation of dedicated input/output buffer queue by using switched fiber delay lines (SDL). It is notable that the shared buffer queue, where a common buffer pool is shared by all the input/output ports of a switch, has the potential to significantly reduce the overall buffer capacity requirement. As far as we know, however, no related work is available yet on the exact emulation of a shared optical buffer queue with SDLs. In this paper, we focus on the design of first in first out (FIFO) shared optical buffer queue based on the optical feedback SDL construction. The construction considered consists of an (M + 2) x (M + 2) switch fabric and M fiber delay lines FDL1, . . ., FDLM, where FDLiconnects the ithoutput of the switch fabric with its ithinput. We show that by setting the length of FDL1as min(M + 1 - i, i), i = 1, . . . , M, such a construction can actually work as an 1-to-2 shared buffer queue. We then extend this emulation to the more general N-to-2 case.

Volunteer computing is very promising to build large scale parallel computing systems from enormous number of computers over the Internet. In a volunteer computing system, sabotage-tolerance is an important issue because there may be malicious users on the Internet who sabotage system by intentionally submitting erroneous results. In this paper, we consider the task scheduling problem of volunteer computing systems which implement sabotage-tolerance mechanism. Although existing sabotage-tolerance mechanisms can guarantee the requirement of credibility for computing results, however, such mechanisms always cause a high performance slowdown in terms of overall execution time. In this paper, we propose an efficient scheduling mechanism called Priority Round Robin (PRR) that takes into account the computing capacity of each volunteer computer. By grouping volunteer computers that have similar computing capacity, the PRR scheduling mechanism can help to reduce overall execution time in comparision with the conventional Round Robin (RR) scheduling, as shown by our extensive simulation results.

Shared-memory optical packet (SMOP) switch architecture is very promising for significantly reducing the amount of required optical memory, which is typically constructed from fiber delay lines (FDLs). The current reservation-based scheduling algorithms for SMOP switches can effectively utilize the FDLs and achieve a low packet loss rate by simply reserving the departure time for each arrival packet. It is notable, however, that such a simple scheduling scheme may introduce a significant packets out of order problem. In this paper, we first identify the two main sources of packets out of order in the current reservation-based SMOP switches. We then show that by introducing a "last-timestamp " variable and modifying the corresponding FDLs arrangement as well as the scheduling process in the current reservation-based SMOP switches, it is possible to keep packets in-sequence while still maintaining a similar delay and packet loss performance as the previous design.

This paper proposes an optimization technique for spot- checking to minimize the computation time of volunteer computing (VC) systems with malicious participants who return erroneous results. Credibility based voting with spot-checking is one of the most promising approaches to guaranteeing the computational correctness ofVC systems. There is an optimal value for the spot-check rate; that is, the increase of the spot-check rate reduces the necessary redundancy for voting, which in turn increases the computation time due to the spot-checking itself. From this tradeoff, the estimation of the optimal spot-check rate is therefore the major concern to minimize the computation time required for the credibility based voting. The key idea is to represent the mathematical expectation of the computation time as a function of the spot-check rate to obtain an estimate of the optimal spot-check rate before the computation. It is shown by Monte Carlo simulations that the proposed technique can always obtain an approximate estimate of the optimal spot-check rate and minimize the computation time with an uncertainty of 1 %.

Effective support of VoIP over Wireless LAN (WLAN) remains a crucial challenge for the last-mile wireless coverage of IP networks with mobility support. Due to the limited bandwidth available in a WLAN, an accurate analysis of voice capacity in such a network is critical for the efficient usage of WLAN's resources. The available upper or lower bound models on voice capacity may significantly overestimate or underestimate a WLAN's capacity to support VoIP, thus they are not suitable for above purpose. In this paper, we focus on the voice capacity analysis of a single wireless 802.11(a/b) network cell running the distributed coordination function (DCF). In particular, by taking into account the spatial distribution of clients, we propose a more accurate analytical model to estimate the average voice capacity of such a network cell. We further show that by properly exploring the clients' spatial distribution information in allocating the access points, we may be able to increase the overall voice capacity. The efficiency of our new voice capacity model and new access point allocation scheme is validated through simulation and comparisons with available ones.

A new packet-forwarding architecture, COPE [1], was proposed recently to demonstrate that by properly exploiting the network coding and physical-layer broadcast properties, the throughput of multihop wireless networks may be significantly improved. However, the theoretical framework is not available yet for a rigorous throughput study of COPE. As the first step toward this direction, in this paper we conduct an analytical analysis on coding opportunities that COPE can create in a multihop wireless network. For a given node, we first derive the probability density function (pdf) of overhearing probability between its two neighbor nodes. Then, based on the pdf of overhearing probability we further analyze the probability of encoding multiple packets together at the node. This work not only provides a framework for the node-level performance analysis of COPE but also lays a foundation for the further network-level performance analysis of COPE.

In online contextual advertising, ad messages are displayed related to the content of the target Web page. It leads to the problem in information retrieval community: how to select the most relevant ad messages given the content of a page. To deal with this problem, we propose a framework that takes advantage of large scale external datasets. This framework provides a mechanism to discover the semantic relations between Web pages and ad messages by analyzing topics for them. This helps overcome the problem of mismatch due to unimportant words and the difference in vocabularies between Web pages and ad messages. The framework has been evaluated through a number of experiments. It shows a significant improvement in accuracy over word/lexicon-based matching and ranking methods.

This paper presents a general framework for building classifiers that deal with short and sparse text & segments by making the most of hidden topics discovered from large-scale data collections. The main motivation of this work is that many classification tasks working with short segments of text & Web, such as search snippets, forum & chat messages, blog & news feeds, product reviews, and book & movie summaries, fail to achieve high accuracy due to the data sparseness. We, therefore, come up with an idea of gaining external knowledge to make the data more related as well as expand the coverage of classifiers to handle future data better. The underlying idea of the framework is that for each classification task, we collect a large-scale external data collection called universal dataset, and then build a classifier on both a (small) set of labeled training data and a rich set of hidden topics discovered from that data collection. The framework is general enough to be applied to different data domains and genres ranging from search results to medical text. We did a careful evaluation on several hundred megabytes of Wikipedia (30M words) and MEDLINE (18M words) with two tasks: Web search domain disambiguation and disease categorization for medical text, and achieved significant quality enhancement.

Multi-log2N networks (or vertically stacked banyan networks) have been an attractive class of switching networks due to their small depth O(log N), absolute signal loss uniformity and good fault tolerance property. Recently, F.K.Hwang extended the study of multi-log2N networks to the general f-cast case, which covers the unicast case (f = 1) and multicast case (f = N) as special cases, and determined the conditions for these networks to be f-cast strictly nonblocking when the fan-out capability is available at both the input stage and middle banyan stage. In this paper, we study the rearrangeable f-cast multilog2N networks under both node-blocking scenario (relevant to photonic switches) and link-blocking scenario (relevant to electronic switches). In particular, we consider the following three fan-out cases in our study: (1) no restriction on fan-out capability; (2) input stage has no fan-out capability; (3) middle banyan stage has no fan-out capability. We determine the necessary conditions for the first two cases while obtaining the necessary and also sufficient condition for the third one.

It is anticipated that a large amount of multicast traffic needs to be supported in future communication networks. The network coding technique proposed recently is promising for establishing multicast connections with a significantly lower bandwidth requirement than that of traditional Steiner-tree-based multicast connections. How to design multicast network topologies with the consideration of efficiently supporting multicast by the network coding technique becomes an important issue now. It is notable, however, that the conventional algorithms for network topology design are mainly unicast-oriented, and they cannot be adopted directly for the efficient topology design of network-coding-based multicast networks by simply treating each multicast as multiple unicasts. In this paper, we consider for the first time the novel topology design problem of network-coding-based multicast networks. Based on the characteristics of multicast and network coding, we first formulate this problem as a mixed-integer nonlinear programming problem, which is NP-hard, and then propose two heuristic algorithms for it. The effectiveness of our heuristics is verified through simulation and comparison with the exhaustive search method. We demonstrate in this paper that, in the topology design of multicast networks, adopting the network coding technique to support multicast transmissions can significantly reduce the overall topology cost as compared to conventional unicast-oriented design and the Steiner-tree-based design.

Current implementations of multi-hop wireless networks suffer from a severe throughput limitation and do not scale well with an increasing number of nodes. A promising architecture COPE [12], which exploits the physical-layer broadcast property and network coding technique, was recently proposed to significantly improve the throughput of multi-hop wireless networks. In this paper, we will improve the packet coding scheme in COPE to further reduce the number of bytes transmitted by a network node for forwarding its incoming packets to the respective neighbors. We first propose a more general packet coding framework, which covers the one in COPE as a special case and can offer us more coding opportunities. We then formulate the optimal packet coding problem under this general coding framework as an integer programming problem, and prove that it is NP-complete. Finally, we present an efficient algorithm to find the optimal coding solution for the proposed general packet coding framework.

Future communication networks should be designed with the consideration of efficiently supporting intensive multicast applications. Network coding technique proposed recently is promising for implementing multicast transmissions with low bandwidth requirement. This paper concerns the novel topology design problem of network coding-based multicast networks, and proposes an improved heuristic algorithm for it by adopting a new cost efficiency (CE) metric for link removal and introducing a local optimization in the design process. The effectiveness of the new heuristic is demonstrated through extensive simulations and comparisons with both the available heuristic and the exhaustive search method. The results in this paper also clearly indicate that applying the novel network coding technique in a multicast network can significantly reduce the overall topology cost.

Load balance (LB) switch architecture is attractive for building high speed switches since it does not require a centralized scheduler and still can guarantee 100% throughput under any admissible traffic. It is notable, however, that due to the multi-path property of LB switches, the packet out-of-sequence problem may happen in such switches. Several schemes have been proposed to tackle the above problem, but these schemes either require infinite central buffer or introduce a high average packet delay. In this paper, we propose a new LB switch architecture - central buffer one-packet-crosspoint (CBX-1). The key idea ofCBX-1 is to introduce a VIOQ (virtual input output queue) with capacity one (i.e., it can store only one packet) after the first stage of a LB switch to emulate a CIXB-1 switch (combined input-one-packet-crosspoint buffered switch). We show through both analysis and simulation that although our architecture requires only finite central buffer to tackle the packet out-of-sequence problem, it still guarantees 100% throughput and achieves a good delay performance.

Active restoration (AR) is a novel lightpath restoration scheme proposed recently to guarantee a certain degree of survivability in wavelength-division multiplexing (WDM) optical networks with a reasonable trade-off between capacity requirement and restoration time. In this paper, we conduct a comprehensive performance analysis for AR-based optical networks. In particular, we propose a novel analytical framework for modeling the restoration probability of a connection (the probability that the connection can be successfully restored in case of a failure) when the possible correlation among its multiple backup routes is incorporated. Although theoretically, we need to consider all the possible correlations between as many as Q) pairs of backup routes to analyze the restoration probability in a network with N nodes, and this high computation complexity may obscure the practicality of an approach, considering all the possible correlations among backup routes, our analysis in this paper indicates that by considering at most the possible correlations among any three successive backup routes of a connection, we can achieve a very good approximation to the simulated restoration probability of the connection, as verified by extensive simulation results upon two typical network topologies under various workloads. We find that the proposed framework can deeply investigate into the inherent relationship among restoration probability, wavelength channel utilization ratio, number of wavelengths per fiber, routes hop length, and wavelength conversion capability. As a result, the framework significantly contributes to the related areas by providing network designers with a quantitative tool to evaluate the restoration probability and, thus, the survivability of AR-based optical networks.

The future communication networks should have a good capability to support the rapidly growing multicast applications. It is notable, however, that the conventional algorithms for network design are mainly unicast-oriented, and they can not be adopted directly for the efficient topology design of multicast-capable networks by simply treating each multicast as multiple unicasts. The network coding technique proposed recently has the potential to efficiently support multicast transmissions with lower bandwidth requirement. In this paper we study the network-coding based network topology design problem with the consideration of efficiently supporting multicast traffic. Based on the characteristics of multicast and network coding, we first formulate this problem as a nonlinear integer programming problem, which is NP-hard. We then propose a heuristic algorithm for it. The efficiency of our algorithm is demonstrated by extensive simulation results under different traffic patterns. We conclude that our network-coding based topology design algorithm can be used to design multicast-capable networks with significantly lower cost than that of conventional unicast-oriented algorithms.

The evolution of VLSI chips towards larger die size, smaller feature size and faster clock speed makes the clock distribution an increasingly important issue. In this paper, we propose a new clock distribution network (CDN), namely Variant X-Tree, based on the idea of X-Architecture proposed recently for efficient wiring within VLSI chips. The Variant X-Tree CDN keeps the nice properties of equal-clock-path and symmetric structure of the typical H-tree CDN, but results in both a lower maximal clock delay and a lower clock skew than its H-tree counterpart, as verified by an extensive simulation study that incorporates simultaneously the effects of process variations and on-chip inductance.

Active restoration (AR) is a novel lightpath restoration scheme proposed recently for guaranteeing a certain degree of survivability in WDM optical networks with a reasonable tradeoff between capacity requirement and restoration time. An analytical model has been proposed to understand the restoration probability behavior of a connection request in optical networks employing AR based on the assumption that all the backup routes of the connection are independent. In a real AR-based optical network, however, the backup paths of a connection are likely correlated since they may share some common links along their routes. As the first step toward the restoration probability analysis incorporating the correlation among backup paths of a connection in AR-based networks, we propose in this paper an analytical approach to modeling the restoration probability of the connection by considering all the possible correlation between any two of its successive backup paths. Compared to the old restoration models without considering the correlation among backup paths, the proposed new model can significantly improve the accuracy in estimating the restoration probability for AR-based networks, as verified by extensive simulation results based on two typical backbone network topologies.

Additive Increase Multiplicative Decrease (AIMD) window adjustment mechanism has been embedded in TCP in order to regulate the transmission rate in modern communication networks. In recent years, the AIMD (1,0.5) traffic regulation mechanism along with possibly additional enhancements, such as false timeout detection and explicit notification, has been considered in the carriers with Optical Burst Switching (OBS) as the underlying transmission technology. This paper introduces a novel rate control mechanism based on Generalized AIMD (α,β), called Burst AIMD (BAIMD), for tuning the rate control parameters (α, β) at each sender. BAIMD is designed to improve throughput while maintaining friendliness with co-existing AIMD (1,0.5) flows, and is characterized in the following two folds: (1) no burst window is required in the TCP sender's level; (2) no explicit notifications are required. The above characteristics make the proposed scheme distinguished from all the past reported counterparts by minimizing the signalling efforts and control complexity. The simulation result shows that BAIMD can solidly outperform the past reported AIMD-based (1,0.5) rate control schemes under a wide range of traffic loads. We also suggest that BAIMD rate control mechanism may serve as a better choice than AIMD (1,0.5) in the bufferless OBS networks due to its dynamic and flexible (α,β) parameter pair.

Discriminative sequential learning models like Conditional Random Fields (CRFs) have achieved significant success in several areas such as natural language processing or information extraction. Their key advantage is the ability to capture various nonindependent and overlapping features of inputs. However, several unexpected pitfalls have a negative influence on the model's performance; these mainly come from a high imbalance among classes, irregular phenomena, and potential ambiguity in the training data. This article presents a data-driven approach that can deal with such difficult data instances by discovering and emphasizing important conjunctions or associations of statistics hidden in the training data. Discovered associations are then incorporated into these models to deal with difficult data instances. Experimental results of phrase-chunking and named entity recognition using CRFs show a significant improvement in accuracy. In addition to the technical perspective, our approach also highlights a potential connection between association mining and statistical learning by offering an alternative strategy to enhance learning performance with interesting and useful patterns discovered from large datasets.

Banyan networks are attractive for serving as the optical switch architectures due to their nice properties of small depth and absolutely signal loss uniformity. Combining the horizontal expansion and vertical stacking of optical banyan networks is a general scheme for constructing banyan-based optical switching networks. The resulting horizontally expanded and vertically stacked optical banyan (HVOB) networks usually take either a high hardware cost or a large network depth to guarantee the nonblocking property. Blocking behavior analysis is an effective approach to studying network performance and finding a graceful compromise among hardware cost, network depth, and blocking probability; however, little has been done to analyze the blocking behavior of general HVOB networks. In this paper, we study the overall blocking behavior of general HVOB networks, where an upper bound on the blocking probability of a HVOB network is developed with respect to the number of planes (stacked copies) and the number of stages. The upper bound accurately depicts the overall blocking behavior of a HVOB network as verified by an extensive simulation study, and it agrees with the strictly nonblocking condition of the network. The derived upper bound is significant because it reveals the inherent relationship among blocking probability, network depth, and network hardware cost, so that a desirable tradeoff can be made among them. In particular, our bound gives network developers an effective tool to estimate the maximum blocking probability of a HVOB network, in which different routing strategies can be applied with a guaranteed performance in terms of blocking probability, hardware cost and network depth. Our upper bound model predicts some unobvious qualitative behaviors of HVOB networks, and it draws an important conclusion that a very low blocking probability (e.g., less than 0.001 percent) can be achieved in a HVOB network without introducing either a significantly high hardware cost or a large network depth.

It is observed that the singular value decomposition (SVD) transformation based on min-plus algebra (or called tropical semi-rings) leads to a very good characteristic in zero underestimating the reconstructed matrix. This paper introduces a novel distributed control framework for shared protection in optical networks with reduced routing information based on the tropical semi-rings technique, called sharing with reduced information with tropical semi-rings (SRI-TROP). The design of the proposed framework aims to initiate a compromise between the amount of link-state dissemination and the performance impairment due to the incompleteness of routing information, such that the precision in the link-state matrix reconstruction can efficiently map to the reduction in blocking probability. Based on the framework, a series of novel schemes are proposed, which are verified and compared with the reported counterparts in a simulation. The simulation results show that the performance in terms of the precision in the reconstructed link-state and the resultant blocking probability can be significantly improved.

This paper proposes a novel framework of bandwidth provisioning based on optical burst switching (OBS), called optical flooding cluster switching (OFCS), which is developed to achieve a better resource allocation and efficiency by fully exploiting the potential characteristics of data-dominated traffic with a high self-similarity and burstiness in the modern communication networks. The concept of flooding clusters is first defined, which serves as basis of the study. The design objectives and the working principles of the OFCS scheme are introduced, where the corresponding advantages against the pure OBS, pure OCS (optical circuit switching), and the hybrid OBS/OCS architectures, are discussed. A comprehensive analytical model on the burst drop rate is formulated for the proposed scheme. To verify the analytical model and compare with the other counterparts, extensive simulation efforts have been addressed. The results reveal that OFCS can overcome the non-predictiveness of traffic self-similarity, where the flooding clusters are set up for a partial prediction of the burst arrival. We conclude that the flooding effect of data-dominated traffic can be successfully smoothed out by the proposed OFCS scheme

Horizontally expanded and vertically stacked optical banyan (HVOB) is a general architecture for constructing banyan-based optical switches. Blocking analysis is an effective approach to studying network performance and finding a graceful compromise among hardware cost, network depth and blocking probability; however, little has been done on analyzing the blocking behavior of general HVOB networks. In this paper, we study the overall blocking behavior of a HVOB network, where an upper bound on the blocking probability of the network is developed. The upper bound depicts accurately the overall performance behavior of a HVOB network as verified by extensive simulation results and it agrees with the strictly nonblocking condition of the network. The derived upper bound is significant because it reveals the inherent relationship among blocking probability, network depth, and network hardware cost, by which a desirable tradeoff can be made among them. In particular, our bound provides network developers an effective tool to estimate the maximum blocking probability of a HVOB network in which different routing algorithms can be applied with a guaranteed performance in terms of blocking probability, hardware cost and network depth. An important conclusion drawn from our work is that the hardware cost of HVOB networks can be reduced dramatically without introducing either significantly high blocking probability or a large network depth.

Discriminative sequential learning models like Conditional Random Fields (CRFs) have achieved significant success in several areas such as natural language processing or information extraction. Their key advantage is the ability to capture various non--independent and overlapping features of inputs. However, several unexpected pitfalls have a negative influence on the model's performance; these mainly come from an imbalance among classes/labels, irregular phenomena, and potential ambiguity in the training data. This paper presents a data--driven approach that can deal with such hard--to--predict data instances by discovering and emphasizing rare--but--important associations of statistics hidden in the training data. Mined associations are then incorporated into these models to deal with difficult examples. Experimental results of English phrase chunking and named entity recognition using CRFs show a significant improvement in accuracy. In addition to the technical perspective, our approach also highlights a potential connection between association mining and statistical learning by offering an alternative strategy to enhance learning performance with interesting and useful patterns discovered from large dataset.

Algorithmic skeletons are abstractions from common patterns of parallel activity which offer a high degree of reusability for developers of parallel algorithms. Their close association with higher order functions (HOFs) makes functional languages, with their strong transformational properties, excellent vehicles for skeleton-based parallel program development. However, using HOFs in this way raises substantial problems of identification of useful HOFs within a given application and of resource allocation on target architectures. We present the design and implementation of a parallelising compiler for Standard ML which exploits parallelism in the familiar $map$ and $fold$ HOFs through skeletons for processor farms and processor trees, respectively. The compiler extracts parallelism automatically and is target architecture independant. HOF execution within a functional language can be nested in the sense that one HOF may be passed and evaluated during the execution of another HOF. We are able to exploit this by nesting our parallel skeletons in a processor topology which matches the structure of the Standard ML source. However, where HOF arguments result from partially applied functions, free variable bindings must be identified and communicated through the corresponding skeleton hierarchy to where those arguments are actually applied. We describe the analysis leading from input Standard ML through HOF instantiation and backend compilation to an executable parallel program. We also present an overview of the runtime system and the execution model. Finally, we give parallel performance figures for several example programs, of varying computational loads, on the Linux-based Beowulf, IBM SP/2, Fujitsu AP3000 and Sun StarCat 15000 MIMD parallel machines. These demonstrate good cross-platform consistency of parallel code behaviour.

The scheme of vertical stacking has caught much interest in the design of ultra high-speed communication switches for the past a few years. In particular, the scheme can greatly facilitate the effort of constructing all-optical photonic switches in the event that a banyan network structure is adopted. A vertically stacked photonic banyan (VSPB) network can preserve the good properties of the banyan network structures, such as the small depth and absolute loss uniformity; on the other hand, it introduces a significant increase in the hardware cost. Extensive research efforts have been addressed in determining the minimum number of stacked copies (planes) required for a nonblocking VSPB network. However, very few of them focused on the performance of the VSPB networks in terms of blocking probability. Therefore, in this paper, we study the blocking behavior of the VSPB networks and propose a corresponding analytical model under the random routing strategy. The proposed analytical model is designed to fully explore the property of symmetry in banyan network structures, and can calculate the blocking probability of a VSPB network stage by stage in a recursive manner such that the combinatorial explosion problem is avoided. To verify the proposed model, we conduct extensive simulations, in which the results indicate that our model can accurately describe the blocking behavior of VSPB networks under the random routing strategy and it agrees with the conditions of strictly nonblocking VSPB networks. We find that the proposed analytical model can deeply investigate into the inherent relationship between blocking probability and network hardware cost in terms of the number of planes; as a result, a quantitative guidance for initiating a graceful compromise between blocking probability and hardware cost can be developed based on the analytical model. Our analysis results also show that the hardware cost of a VSPB network can be dramatically reduced by simply allowing a negligible nonzero blocking probability in most of the practical cases. This fact will solidly contribute to the network switch architecture design and enable more practical applications of VSPB networks.

The paper proposes a novel distributed control architecture for shared protection with reduced complete routing information, which aims to initiate a graceful compromise between the amount of link-state dissemination and the performance impairment due to the incompleteness of routing information. We first give explicit and comprehensive descriptions on a number of reported routing information dissemination scenarios for shared protection. A novel framework of link-state dissemination for facilitating shared protection, called reduced complete routing scenario, is introduced, in which the singular value decomposition (SVD) transformation is adopted to deal with the information reduction. We show, through simulation, that the proposed scheme can achieve a higher throughput and a better estimation in reconstruction of the spare provision matrix than the other schemes taking the same complexity of link-state dissemination.

Text categorization is a problem of assigning a document into one or more predefined classes. One of the most interesting issues in text categorization is feature selection. This paper proposes a novel approach in feature selection based on multicriteria ranking of features. Based on a threshold value for each criterion, a new procedure for feature selection is proposed and applied to a text categorization. Experiments dealing with the Reuters-21578 benchmark data and the naive Bayes algorithm show that the proposed approach outperforms performances in compare to conventional feature selection methods.

Mining product descriptions (PDs) from e-commercial web sites is an important task in information extraction from the Web. In this paper, we propose an efficient technique for this task. The technique first discovers the set of PDs based on the measure of entropy at each internal node in the HTML tag tree. Afterwards, a set of association rules based on heuristic features is employed to filter the output and therefore enhance the precision. The experimental results of PEWeb system show that the proposed method outperforms existing automatic techniques remarkably.

Sentence reduction is the removal of redundant words or phrases from an input sentence by creating a new sentence in which the gist of the original meaning of the sentence remains unchanged. All previous methods required a syntax parser before sentences could be reduced; hence it was difficult to apply them to a language with no reliable parser. In this article we propose two new sentence-reduction algorithms that do not use syntactic parsing for the input sentence. The first algorithm, based on the template-translation learning algorithm, one of example-based machine-translation methods, works quite well in reducing sentences, but its computational complexity can be exponential in certain cases. The second algorithm, an extension of the template--translation algorithm via innovative employment of the Hidden Markov model, which uses the set of template rules learned from examples, can overcome this computation problem. Experiments show that the proposed algorithms achieve acceptable results in comparison to sentence reduction done by humans.

Vertical stacking of optical banyan networks is an attractive scheme for building nonblocking (crosstalk-free) optical switching networks. The resulting networks, namely vertically stacked optical banyan (VSOB) networks, preserve all the good properties of banyan networks, but increase the hardware cost significantly. In this paper, we study the blocking probabilities of VSOB networks under random routing strategy, and develop a model to compute the blocking probabilities with respect to the number of planes in the networks. Our model calculates the blocking probabilities stage by stage recursively, and it depicts accurately the blocking behaviors of VSOB networks under random routing. The proposed model is significant because it reveals the inherent relationships between blocking probability and network hardware cost in terms of the number of planes, and provides network developers a quantitative guidance to find a desirable tradeoff between blocking probability and hardware cost. An important conclusion drawn from our work that has practical applications is that the hardware cost of a VSOB network can be reduced dramatically if a predictable and almost negligible non-zero blocking probability is allowed.

Banyan networks are attractive for constructing directional coupler (DC)-based optical switching networks for their small depth and self-routing capability. Crosstalk between optical signals passing through the same DC is an intrinsic drawback in DC-based optical networks. Vertical stacking of multiple copies of an optical banyan network is a novel scheme for building nonblocking (crosstalk-free) optical switching networks. The resulting network, namely vertically stacked optical banyan (VSOB) network, preserves all the properties of the banyan network, but increases the hardware cost significantly. Though much work has been done for determining the minimum number of stacked copies (planes) required for a nonblocking VSOB network, little is known on analyzing the blocking probabilities of VSOB networks that do not meet the nonblocking condition (i.e., with fewer stacked copies than required by the nonblocking condition). In this paper, we analyze the blocking probabilities of VSOB networks and develop their upper and lower bounds with respect to the number of planes in the networks. These bounds depict accurately the overall blocking behaviors of VSOB networks and agree with the conditions of strictly nonblocking and rearrangeably nonblocking VSOB networks respectively. Extensive simulation on a network simulator with both random routing and packing strategy has shown that the blocking probabilities of both strategies fall nicely within our bounds, and the blocking probability of packing strategy actually matches the lower bound. The proposed bounds are significant because they reveal the inherent relationships between blocking probability and network hardware cost in terms of the number of planes, and provide network developers a quantitative guidance to trade blocking probability for hardware cost. In particular, our bounds provide network designers an effective tool to estimate the minimum and maximum blocking probabilities of VSOB networks in which different routing strategies may be applied. An interesting conclusion drawn from our work that has practical applications is that the hardware cost of a VSOB network can be reduced dramatically if a predictable and almost negligible nonzero blocking probability is allowed.

Crosstalk in optical switching elements (SEs) is one of the major shortcomings in optical switching networks, and avoiding crosstalk is an important issue for proper optical network operation. We propose a new class of optical multistage interconnection networks (MINs)-vertically stacked Benes networks VSB(N, K) that have N inputs (outputs) and consist of K vertically stacked Benes networks. The VSB(N, K) network can support any permutation of an N-element set {0, 1, ..., N-1}. Complete algorithms to realize crosstalk-free permutation in a VSB(N, K) network are the main contributions of this paper.

Recently, many defect compensation methods have been proposed for feedforward neural networks implemented in hardware devices. However, there are few accurate quantitative comparisons with the performance of these defect compensation methods. In this paper, we compare the following three defect compensation methods; partial retraining (PR) scheme, whole network backpropagation (BP) retraining and FT (fault-tolerant) BP method. The BP algorithm and PR scheme retrain the neural network after defects have occurred. The FTBP method tries to obtain the weights those are robust for the defects. We can say that both the BP algorithm and PR scheme are cure-type compensation methods and the FTBP method is a precaution-type compensation method. We compare the average recognition rate, average training time and the generalization ability among these three methods in detail. The experiments show that the whole network retraining by the BP algorithm has the highest reliability on the XOR problem and face image recognition problem on the neural networks with a single broken link defect and two broken link defects.

Clock skew modeling is important in the performance evaluation and prediction of clock distribution networks. This paper addresses the problem of statistical skew modeling for general clock distribution networks in the presence of process variations. The only available statistical skew model is not suitable for modeling the clock skews of general clock distribution networks in which clock paths are not identical. The old model is also too conservative for estimating the clock skew of a well-balanced clock network that has identical but strongly correlated clock paths (for instance, a well-balanced H-tree). In order to provide a more accurate and more general statistical skew model for general clock distributions, we propose a new approach to estimating the mean values and variances of both clock skews and the maximal clock delay of general clock distribution networks. Based on the new approach, a closed-form model is also obtained for well-balanced H-tree clock distribution networks. The paths delay correlation caused by the overlapped parts of path lengths is considered in the new approach, so the mean values and the variances of both clock skews and the maximal clock delay are accurately estimated for general clock distribution networks. This enables an accurate estimate of yields of both clock skew and maximal clock delay to be made for a general clock distribution network.

This paper addresses a dynamic load balancing method of domain decomposition for 3-dimensional molecular dynamics on parallel computers. In order to reduce interprocessor communication overhead, we are introducing a concept of permanent cells to the dynamic load balancing method. Molecular dynamics simulations on a parallel computer T3E prove that the proposed method using load balancing much improves the execution time. Furthermore, we analyze theoretical effective ranges of the dynamic load balancing method, and compare them with experimental effective ranges obtained by parallel molecular dynamics simulations. As a result, the theoretical upper bounds predict experimental effective ranges and are also valid on commercial parallel computers.

This paper presents new results for diagnosing (detection and location) multistage interconnection networks (MINs) in the presence of multiple faults. Initially, it is proved that the lower bound in the number of tests for multiple fault diagnosis (independent of the assumed fault model for the MIN) is 2/spl times/log/sub 2/N, where N is the number of inputs/outputs of the network. A new fault model is introduced; this fault model is applicable to interconnection networks implemented using CMOS technology. The characterization for diagnosing stuck-open faults is presented.

Models for synchronized parallel computation are described, in which processors are interconnected by networks. These models are used to solve the problem of finding the maximum value, the minimum value, or both values in parallel. The proposed algorithm is based on the binary tree routing scheme. The time complexities are investigated by taking account of the communication overhead. The optimal number of processors for a fixed number of data is analytically obtained. This number depends significantly on the types of interconnection networks. Results are presented for linear, mesh, three-dimensional, and cube-connected arrays. Execution times are investigated and are measured using a cluster multiprocessor system.>