With the rapid development of quantitative trading, stock selection is an ongoing task that requires consideration of the characteristics of stocks and investment strategies. Fuzzy set theory is excellent for modeling and describing abstract characteristics to establish the link between stocks and strategies. In this article, we present our idea for a stock selection system called TripleS. It is based on the suitability index (SI) derived from fuzzy-set theory. The TripleS relies on the position size to extract the stock characteristics SI that describes not only the characteristics of each stock but also the extent to which they are suitable for certain strategies. Then, the SI undergoes a transformation process in the hands of the developed fuzzy-set modules for stock selection and investment. There are some other proposed methods for stock selection respectively called TripleS-T1, TripleS-T2, TripleS-T2U, TripleS-EF, and TripleS-EFT. Experimental results show that the proposed TripleS has minor improvement in precision but significant improvement in investment performance. The TripleS-EFT has outstanding profitability, the highest annual return in all strategies, and the highest Sharpe ratio in two of the four strategies, and achieves an annual return of 10.01% and a Sharpe ratio of 1.032, which significantly outperform the benchmark system. The TripleS-EFT also significantly outperforms the state-of-the-art fuzzy-based system in measuring annual return and even has double the annual return in several strategies.

With the rapid development of quantitative trading, stock selection is an enduring task, that requires consideration of the characteristic of stocks and investment strategies. Fuzzy-set theory is outstanding in modeling abstract characteristics, which is suitable for building the connection between stocks and strategies. In this paper, we propose a stock selection system (SSS) based on the suitability index (SI) and fuzzy-set theory. SSS utilizes position sizing to extract stock characteristics, SI, which expresses not only the characteristics of stocks but also the suitability for strategies. The SI is then transformed by the designed fuzzy-set modules for stock selection and investment. Several stock selection mechanisms are proposed, denoted as SSS-T1, SSS-T2, SSS-WT1, and SSS-WT2. Experimental results show that SSS has a slight improvement in precision, but leads to a significant improvement in investment. The proposed SSS-WT1 and SSS-WT2 systems achieve the highest annual returns of 6.2% and the highest Sharpe ratios of 0.924, outperforming the benchmark with the annual return of 1.9% and the Sharpe ratio of 0.201.

Trading strategies can be divided into two categories, i.e., those with momentum characteristic and those that appear contrarian. The characteristics of trading strategies have been widely studied; however, there has been relatively little work on the characteristics of stocks. Furthermore, there is no standard approach to the classification of stocks in terms of momentum and contrarian. This article presents a fuzzy momentum contrarian uncertain characteristic system for the classification and quantification of stock characteristics. Random trading, stop-loss, and take-profit mechanisms are first used to identify characteristics, and then, a novel profitability index with a type-2 fuzzy set module is used to quantify them. In the experiments, 41 stocks on the Taiwan 50 index were deemed suitable for momentum strategies, whereas nine stocks were deemed suitable for contrarian strategies. An uphill relationship between profitability index and trading performance is observed, which produced correlation coefficients of 0.148–0.539 and a classification accuracy of 52.0–60.0%. However, the proposed system greatly improved classification performance, resulting in correlation coefficients of 0.572–0.722 with an accuracy of 63.6–84.5%. In the real-world application, the proposed system outperforms the benchmark among all datasets and increases the profitability by 1.5 times on the Taiwan 50 dataset. These results clearly demonstrate the efficiency of the proposed system in the quantification and classification of stocks suited to momentum- and contrarian-type trading strategies and also in the real-world applications.

Although conventional machine learning algorithms have been widely adopted for stock-price predictions in recent years, the massive volume of specific labeled data required are not always available. In contrast, meta-learning technology uses relatively small amounts of training data, called fast learners. Such methods are beneficial under conditions of limited data availability, which often obtain for trend prediction based on time-series data limited by sparse information. In this study, we consider short-term stock price prediction using a meta-learning framework with several convolutional neural networks, including the temporal convolution network, fully convolutional network, and residual neural network. We propose a sliding time horizon to label stocks according to their predicted price trends, referred to as called slope-detection labeling, using prediction labels including "rise plus," "rise," "fall," and "fall plus". The effectiveness of the proposed meta-learning framework was evaluated by application to the S&P500. The experimental results show that the inclusion of the proposed meta-learning framework significantly improved both regular and balanced prediction accuracy and profitability.

Abstract Portfolio management involves position sizing and resource allocation. Traditional and generic portfolio strategies require forecasting of future stock prices as model inputs, which is not a trivial task since those values are difficult to obtain in the real-world applications. To overcome the above limitations and provide a better solution for portfolio management, we developed a Portfolio Management System (PMS) using reinforcement learning with two neural networks (CNN and RNN). A novel reward function involving Sharpe ratios is also proposed to evaluate the performance of the developed systems. Experimental results indicate that the PMS with the Sharpe ratio reward function exhibits outstanding performance, increasing return by 39.0% and decreasing drawdown by 13.7% on average compared to the reward function of trading return. In addition, the proposed model is more suitable for the construction of a reinforcement learning portfolio, but has 1.98 times more drawdown risk than the . Among the conducted datasets, the PMS outperforms the benchmark strategies in TW50 and traditional stocks, but is inferior to a benchmark strategy in the financial dataset. The PMS is profitable, effective, and offers lower investment risk among almost all datasets. The novel reward function involving the Sharpe ratio enhances performance, and well supports resource-allocation for empirical stock trading.

Opening range breakout (ORB) is a well-known intraday trading strategy via technical analysis. ORB lacks robustness against market uncertainties (e.g., information from contradictory sources), and does not consider all relevant market characteristics. Furthermore, the closing strategies in generic ORB are not well defined. In this study, we developed an evolutionary ORB-based model, which utilized historical data to optimize thresholds in order to enhance profitability, and developed protective closing strategies aimed at to prevent unacceptable losses. Selecting appropriate thresholds and parameters for ORB is a non-trivial task, due to the fact that the search space exceeds sixty-five thousand options. We used evolutionary computation to derive rational strategies and parameters for ORB. The proposed framework based on a genetic algorithm optimizes the parameters related to threshold selection and protective closing strategies. In experiments, this resulted in annual returns of 9.3% (representing a 2.8% improvement over the original strategy) and Sharpe ratio of 2.5 (an improvement of 1.0), while reducing the maximum drawdown by half. The proposed scheme also reduced computational overhead by 89% compared to a grid search.

Opening range breakout (ORB) is a well-known intraday trading strategy that generates trading signals through technical analysis; however, ORB does not make full use of market characteristics and does not define closing strategy. These problems make the ORB strategy not stable or robust enough. In this paper, we adjust thresholds through historical data to enhance profitability, and design protective closing strategy to prevent unacceptable losses. However, there are numerous parameters combinations, and the solution space is approximately 214. Therefore, we implement genetic algorithm to improve the efficiency and rationality of parameter selection. We found that the performance of the GAORB_Sharpe with stop-loss mechanism is outstanding. The strategy we proposed can generate 9.303% annual return and 15.716% Sharpe ratio, which is 2.5% and 5% more than the original strategy, and cut the maximum drawdown by half. Further, it can save 90% of the computation by genetic algorithm. In summary, we recommend adjusting the threshold and implementing stop-loss mechanism to the ORB strategy, and selecting parameters through genetic algorithms to improve overall performance.

Opening Range Breakout (ORB) is a renowned technical analysis strategy in which two pre-determined thresholds are set up in the early stage after market opening to determine the direction of investment for the day. In the literature, ORB has been shown to produce significant profits on several stock markets. In this paper, we present novel ORB algorithms based on deep learning which take into account historical trends and price movement during the early market interval. The proposed scheme uses a multi-label classification framework with multi-layer perceptron neural models and convolutional neural network models to predict the most profitable thresholds. To generate ground truth values for evaluation, we compared two labeling methods (one-hot encoding and distributed encoding). In experiments based on an empirical dataset, the proposed strategy earned profits of 8126, annual returns of 14.003%, and a Sharpe ratio of 1.376. The proposed scheme outperformed the original ORB strategy by nearly 2 times on metrics mentioned above and decreased maximum drawdown by more than 60%. Experiment results revealed that the uppermost and lowermost classes of thresholds accounted for the majority of the predicted results. In other words, taking a long position at a lower boundary and a short position at a higher boundary increased the likelihood of generating higher profits, while reducing exposure to risk.

Portfolio management is a critical issue which should be skilled by position sizing and resource allocation. Traditional and generic portfolio strategies require to forecast the future stocks prices as the model inputs, which is not a trivial task in the real-world applications. To solve the above limitations and provide a better solution for the portfolio management to the inventors, we then develop a portfolio management system (PMS) with equity market neutral strategy in reinforcement learning. A novel reward function involving Sharpe ratio is also designed to evaluate the performance of the developed systems. Experimental results indicate that the PMS with Sharpe ratio reward function has the outstanding performance, and increase the return 39.0% and decrease the drawdown of 13.7% on average than that with reward function of trading return. In addition, the developed PMS_CNN model is more suitable and profitable to construct RL portfolio, but has a 1.98 times more drawdown risk than the PMS_RNN. Overall, the proposed PMS outperforms the benchmark strategies in the measurements of total return and Sharpe ratio. The PMS is profitable and effective with lower investment risk, and the novel reward function by involving Sharpe ratio really enhances the performance, and well support the resource-allocation in the empirical stock trading.

TeraSort [7] is a standard MapReduce sort which is applied as a benchmark to measure the time to sort terabytes of randomly distributed data. TeraSuffix [5] adopts TeraSort to construct suffix array for NGS (Next-Generation Sequencing). When using TeraSuffix to construct suffix array for NGS, as the intermediate data of the MapReduce framework contains multiple copies of suffixes, the shuffle of the intermediate data between map and reduce become a bottleneck. For a suffix can be represented by its index to the NGS Reads data, it's no need to record suffix as the intermediate data and thus reduce the shuffle time. Disk-based Indexed TeraSuffix [6] adopts this index structure to represent a suffix and stores the NGS Reads data on disk. However, when constructing the suffix array, reduce tasks still need lots of random access from disk to retrieve suffixes for further processing. The massive disk I/O operations become a bottleneck. To increase the efficiency of the Disk-based Indexed TeraSuffix, in-memory lookup cloud (MLC) is proposed in this paper to store the NGS Reads data on the memory of remote servers in a cloud. When a map/reduce task needs to retrieve a suffix, it can access the suffix from the memory of MLC through the network. Experimental tests were performed to show that the access of suffix through network is outperformed than from disk. Experiments were also performed on Amazon Elastic MapReduce with the sequence of 20Gbp-Grouper (about 20Gbytes). It showed that the proposed architecture reduces the pre-processing time of data replication and the processing time of reduce tasks by 58% and 8%, respectively. It improves both the time and the space efficiency of TeraSort for constructing suffix array.

Portfolio management and money management have always been important issues for investors and researchers in the financial field. The Kelly criterion is a theoretical approach of money management, and is a mathematical method for optimizing long-term expected return. Kelly criterion requires the future outcomes distribution as input, which can be predicted through the techniques of machine learning (ML). With the revolutionary growth of the amount of information, big data is the key to boost ML prediction, therefore, we introduce a general Kelly framework, including the strength of Kelly, ML, and big data. In addition, we propose the Kelly stationary index (KSI) to quantify the stationarity of the stock's outcomes distribution, which will affect the trading period and forecasting frequency. We calculate the KSI of each constituent stock of Taiwan's 50, and apply the Kelly criterion strategy to verify the effectiveness of KSI. The experimental results show that there is a moderate downhill relationship between the strategy performance and KSI with the -0.591 of correlation coefficient. It also indicates that the closer the estimated distribution is to the actual distribution, the higher the expected profit. In the future, we will use KSI for money management, strategy development, and apply KSI into the general Kelly framework.

Opening Range Breakout (ORB) is a fairly intraday trading strategy. We set the resistance and the support levels by the price in opening interval to follow the trend in the futures market. However, such kind of strategies is not profitable for most commodities in recent years in the changing market. In this paper, we attempt to improve the original ORB strategy by considering the effect of trends continuity on the event. We adjust the predetermined threshold for upper bound and lower bound. This strategy is called Threshold Adjusting ORB or TA_ORB. We implement this modified ORB strategy on the Taiwan Index Futures from 2008 to 2012. Compared with the original ORB strategy, we got 145.98% return in 2008 (bear market), 81.86% return in 2009 (bull market) and 32.25% annual return in 2008-2012 (five-year period) which are 4.0 times, 1.4 times, and 2.6 times more than original ORB, respectively. TA_ORB performs outstanding in large fluctuation, especially in the bear market. Performance can verify that the observations of TA_ORB improve the stability of the breakthrough signal, enhance the return, and reduce strategic risk. Further, we plan to use neural network to make more precise predictions and implement these strategies in different commodities.

This paper proposes a new investment strategy with deep-learning market prediction for mutual fund portfolio optimization. Our strategy uses the capital asset pricing model (CAPM) that applies macroeconomic factors to predict whether the market is bull or bear. Then, we develop a robo-advisor (RA) to predict future market, optimize portfolio and automate investment. Experiments use 22 years' data of S&P500 and mutual funds of U.S. to validate our strategy. Results show that the accuracy of our market prediction method can reach 84.3% and the rate-of-return of our RA is 13.S7%. Our model is more accurate and profitable than other algorithms.

Due to advancement in next-generation sequencing (NGS) technology, ultra-large datasets have been generated for further studies. These datasets contain a large amount of erroneous data. It is a computational problem to detect and correct the errors to improve performance of future applications, e.g., de novo assembly. In this article, we present a MapReduce-based algorithm, CloudEC, to correct sequencing errors in NGS data. We use five datasets and GAGE benchmark to compare efficiency and efficacy of CloudEC with CloudRS and error correction module of ALLPATHS-LG. Experiments show that CloudEC is 1.6 times faster than CloudRS. The corrected reads are then assembled by Velvet assembler, and the assembled results are examined by GAGE benchmark for correctness of assembly. It is shown that the correct N50 of the assembled contigs with CloudEC as the error corrector is larger than that with CloudRS as the error corrector, and is comparable to that with ALLPATHS-LG as the error corrector.

Framing is a phenomenon that is studied and debated widely in sociology and political science. It refers to the manner in which audiences interpret information and justify their claims or activities. The subconscious influence of framing might lead to opinion changes and social movements. However, multi-frame classification on microblogging data has not yet been investigated. In this study, we aim to classify a large number of posts into frames. We describe in detail the implementation of a new algorithm for multi-frame classification tasks called Frame Dispatcher, which aims to classify microblogging data into frames. In our experiments, we extracted over 15,000 posts from approximately 200 Facebook fan pages concerning an anti-curriculum student movement. The experimental results show that Frame Dispatcher can classify microblogging data into frames efficiently and effectively.

Big-data computing is a new critical challenge for the ICT industry. Engineers and researchers are dealing with data sets of petabyte scale in the cloud computing paradigm. Thus, the demand for building a service stack to distribute, manage, and process massive data sets has risen drastically. In this paper, we investigate the Big Data Broadcasting problem for a single source node to broadcast a big chunk of data to a set of nodes with the objective of minimizing the maximum completion time. These nodes may locate in the same datacenter or across geo-distributed datacenters. This problem is one of the fundamental problems in distributed computing and is known to be NP-hard in heterogeneous environments. We model the Big-data broadcasting problem into a LockStep Broadcast Tree (LSBT) problem. The main idea of the LSBT model is to define a basic unit of upload bandwidth, r, such that a node with capacity c broadcasts data to a set of [c/r] children at the rater. Note that r is a parameter to be optimized as part of the LSBT problem. We further divide the broadcast data into m chunks. These data chunks can then be broadcast down the LSBT in a pipeline manner. In a homogeneous network environment in which each node has the same upload capacity c, we show that the optimal uplink rate r* of LSBT is either c/2 or c/3, whichever gives the smaller maximum completion time. For heterogeneous environments, we present an O(nlog2n) algorithm to select an optimal uplink rater* and to construct an optimal LSBT. Numerical results show that our approach performs well with less maximum completion time and lower computational complexity than other efficient solutions in literature.

Since a complete Chinese font has typically several thousand or more Chinese characters and symbols, and most of them are much more complicated than English alphabets, it takes a lot of time and efforts for even professional font engineers to create a Chinese font. Although several attempts had been made to synthesize Chinese characters from strokes and components, it is still not easy to synthesize so many Chinese characters at one time. In this paper, we present an easy and fast solution for an ordinary user to create a Chinese font of his or her handwriting style. We adopt the approach: to synthesize Chinese characters using components extracted from the user's handwritings. In the preprocessing phase, we built a Web interface for crowds to label the positions and sizes of components of every Chinese character in the target character set. The standard Kai font was selected as a reference. We also devised an algorithm to find a small subset of Chinese characters having all required components to synthesize other Chinese characters. To create a personal handwriting font, with commonly-used 3,914 traditional Chinese characters, a user only has to handwrite 400 or so Chinese characters on a pad. One character by one character, our system can track every stroke, recognize and extract components from the user's handwritings. Then, every target Chinese character is synthesized from the extracted components, by placing them properly according to their position and size information. The experiment results show that although manually fine-tune is still required for few synthesized Chinese characters, users can create a Chinese font of their personal handwriting styles more easily and quickly.

Next-generation sequencing (NGS) data are a rapidly growing example of big data and a source of new knowledge in science. However, sequencing errors remain unavoidable and reduce the quality of NGS data. Error correction, therefore, is a critical step in the successful utilization of NGS data, including de novo genome assembly and DNA resequencing. Since NGS throughput doubles approximately every five months and the length of NGS records (i.e., reads) is increasing, improvements in efficiency and effectiveness of computational strategies are needed. In this study, we aim to improve the performance of CloudRS, an open-source MapReduce application designed to correct sequencing errors in NGS data. We introduce the readmessage (RM) diagram to represent the set of messages, i.e., the key-value pairs generated on each read. We also present the Gradient-number Votes (GNV) scheme in order to trim off portions of the RM diagram, thereby reducing the total size of messages associated with each read. Experimental results show that the GNV scheme successfully reduce execution time and improve the quality of the de novo genome assembly.

Next-generation sequencing (NGS) technologies produce huge amounts of data. These sequencing data unavoidably are accompanied by the occurrence of sequencing errors which constitutes one of the major problems of further analyses. Error correction is indeed one of the critical steps to the success of NGS applications such as de novo genome assembly and DNA resequencing as illustrated in literature. However, it requires computing time and memory space heavily. To design an algorithm to improve data quality by efficiently utilizing on-demand computing resources in the cloud is a challenge for biologists and computer scientists. In this study, we present an error-correction algorithm, called the CloudRS algorithm, for correcting errors in NGS data. The CloudRS algorithm aims at emulating the notion of error correction algorithm of ALLPATHS-LG on the Hadoop/ MapReduce framework. It is conservative in correcting sequencing errors to avoid introducing false decisions, e.g., when dealing with reads from repetitive regions. We also illustrate several probabilistic measures we introduce into CloudRS to make the algorithm more efficient without sacrificing its effectiveness. Running time of using up to 80 instances each with 8 computing units shows satisfactory speedup. Experiments of comparing with other error correction programs show that CloudRS algorithm performs lower false positive rate for most evaluation benchmarks and higher sensitivity on genome S. cerevisiae. We demonstrate that CloudRS algorithm provides significant improvements in the quality of the resulting contigs on benchmarks of NGS de novo assembly.

The MapReduce framework has become the de facto choice for big data analysis in a variety of applications. In MapReduce programming model, computation is distributed to a cluster of computing nodes that runs in parallel. The performance of a MapReduce application is thus affected by system and middleware, characteristics of data, and design and implementation of the algorithms. In this study, we focus on performance optimization of a MapReduce application, i.e., CloudRS, which tackles on the problem of detecting and removing errors in the next-generation sequencing de novo genomic data. We present three strategies, i.e., contentexchange, content-grouping, and index-only strategies, of communication between the Map() and Reduce() functions. The three strategies differ in the way messages are exchanged between the two functions. We also present experimental results to compare performance of the three strategies.

This paper presents an efficient algorithm for finding the optimal k-cuts of a nondecreasing array of size n that produces the maximum area under the points. The naïve approach uses a dynamic programming algorithm which requires O(kn2) time, where n is the size of the array. This algorithm is time consuming for large n or k and thus inappropriate. We design faster algorithms by discovering and proving some nice properties of the nondecreasing arrays, finding convex hull, and by continuous-to-discrete transformation. We believe that an O(kn) time algorithm exists and show a heuristic algorithm.

The purpose of this paper is to develop a method to recommend products to customer via mobile devices. Collaborative recommendation is known as an effective way to recommend products. In this paper, we use the concept of collaborative recommendation to develop Mobile-Oriented Catalog (MOC). The proposed method is made from aggregating similar purchasing records to optimize combination of goods on mobile devices. This paper illustrates how to design attractive and collaborative catalog to recommend items by using Latent Dirichlet Allocation (LDA) based self-adaptive genetic algorithm (LDA-SAGA). LDA-SAGA is consisted of topic modeling concept and self-adaptive genetic algorithm. We use LDA as our topic modeling algorithm to construct MOC as a result that it is the simplest topic model. Our experimental evaluation on synthetic and real data shows that using preference as topic concept is effective. LDA-SAGA is especially outstanding with large number of customers and products. Finally, we compare the MOC which is used on mobile application (APP) of Amazon with the one used on Taobao and discuss the characteristics of their design. Different design of user interface on APP can lead to different scope of fitness value which is capable of explaining different market strategies of Taobao and Amazon.

Social network applications are becoming increasingly popular on mobile devices. A mobile presence service is an essential component of a social network application because it maintains each mobile user's presence information, such as the current status (online/offline), GPS location and network address, and also updates the user's online friends with the information continually. If presence updates occur frequently, the enormous number of messages distributed by presence servers may lead to a scalability problem in a large-scale mobile presence service. To address the problem, we propose an efficient and scalable server architecture, called PresenceCloud, which enables mobile presence services to support large-scale social network applications. When a mobile user joins a network, PresenceCloud searches for the presence of his/her friends and notifies them of his/her arrival. PresenceCloud organizes presence servers into a quorum-based server-to-server architecture for efficient presence searching. It also leverages a directed search algorithm and a one-hop caching strategy to achieve small constant search latency. We analyze the performance of PresenceCloud in terms of the search cost and search satisfaction level. The search cost is defined as the total number of messages generated by the presence server when a user arrives; and search satisfaction level is defined as the time it takes to search for the arriving user's friend list. The results of simulations demonstrate that PresenceCloud achieves performance gains in the search cost without compromising search satisfaction.

The next-generation sequencing technologies dramatically accelerate the throughput of DNA sequencing in a much faster rate than the growth rate of computer speed as predicted by the "Moore's Law." It is a problem even to load and run these sequencing data in memory. There is an urgent need for de novo assemblers to efficiently handle the huge amount of sequencing data using scalable commodity servers in the clouds. In this paper, we present CloudBrush, a parallel algorithm that runs on the MapReduce framework of cloud computing for de novo assembly of high-throughput sequencing data. The algorithm uses Myers's bi-directed string graphs as its basis and consists of two main stages: graph construction and graph simplification. First, a vertex is defined for each non-redundant sequence read. We present a prefix-and-extend algorithm to identify overlaps between a pair of reads and to reduce transitive edges. The graph is further simplified by using conventional operations including path compression, tip removal and bubble removal. We also present a new operation, Similar Neighbour Edge Adjustment, to remove error topology structures in string graphs. Besides, we also disconnect repeat regions by revised A-statistics. The goal is to partition the string graph so that all paths in each connected subgraph correspond to similar subsequences of the underlying genome. We then traverse each connected subgraph to find a long path supported by a sufficient amount of reads to represent the subgraph. Preliminary results show that the CloudBrush assembler, compared with Contrail and Edena on the sequencing data of E. coli genomes, may yield longer contigs.

Asian barrier options are barrier options whose trigger is based on an average underlying price. They provide the advantages of both Asian options and barrier options. This paper introduces the first quadratic-time lattice algorithm to price European-style Asian barrier options. It is by far the most efficient lattice algorithm with convergence guarantees. The algorithm relies on the Lagrange multipliers to optimally distribute the number of states for each node of the multinomial lattice. We also show experiment results to demonstrate effectiveness and efficiency of our algorithm by comparing with Monte Carlo simulations.

Financial derivative valuation is the key of the adoption of the International Financial Reporting Standards (IFRS), which are based on fair value accounting. When the derivatives do not have an active market, the inputs and methods for estimating their fair value will be more subjective and, the derivative valuation will be less reliable. The goal of this research is to design a derivative valuation service to aid the accounting professionals to meet the reliability requirement of the IFRS which, in the derivative setting, requires derivative valuation be objective and free from errors. First, we incorporate the various valuation models and their risk factors into the service as the basis for providing an objective valuation result. Second, we provide a user interface to simplified management of parameters and provisions of term sheets of derivatives to avoid users' errors in parsing the term sheets. Third, when the users hold a large number of derivatives, the derivative valuation meets real-time constraints in financial reporting. We thus developed the service in parallel computing environment to reduce computational time of the valuation process. Experiment cal results of derivative valuation are also presented.

This study considers all the possible actions a borrower may have, i.e., to default, to prepay, and to maintain the mortgage, during mortgage horizon. Then, we provide an effective and accurate pricing formula, which not only considers the effect that default might affect the mortgage value, but also more accurately explores the impact due to prepayment risk. In our model, we define prepayment value of the mortgage as the amount of outstanding principle. In contrast, previous literature defines prepayment value as a constant proportion of maintaining value of the mortgage. Finally, based on closed-form pricing formula, we analyze the yield, duration and convexity of risky mortgage loan, providing a better framework for risk management.

In network applications with security constraints, it is usually desirable to disseminate a file from a server through trusted network channels to a set of peers. This is a problem seldom studied in the literature though the problems of data integrity and security have been studied by many. In this paper, we study the file dissemination problem with trust relation modeled as a rooted full binary tree. We present the OOFD algorithm to schedule dissemination of the file iteratively from each peer holding a replica of the file to one of its descendants on the binary tree. We show that, in a homogeneous network, OOFD algorithm is optimum in the sense that time it takes to disseminate the file to all nodes is minimized.

A publication record denotes a list of semi-structured citation string of publications of a research institute or an individual researcher. Publication records are integrated into a digital library to become an important knowledge base which in turn enables a variety of applications. A publication record is usually found among other information on a publication Web page (or publication page for short). It is thus an interesting problem to extract publication record from these Web pages. The problem is difficult due to several reasons including the flexibility in formatting the metadata of a publication into a semi-structured citation string and expressing the citation string into its visual presentation in HTML. Furthermore, two citation strings with similar visual presentation on the same Web page may have different HTML constructs. In this paper, we present a content analysis approach based on Conditional Random Fields and data region boundary analysis to automatically extract citation record on a publication page. Experimental results show that our method performs well on a benchmark containing manually crafted publication Web pages. The precision, recall, and F-measure are 82.5%, 87.6%, and 85.0% respectively. This is an improvement over previous results.

Dramatic increase in the number of academic publications has led to growing demand for efficient organization of the resources to meet researchers' needs. As a result, a number of network services have compiled databases from the public resources scattered over the Internet. However, publications by different conferences and journals adopt different citation styles. It is an interesting problem to accurately extract metadata from a citation string which is formatted in one of thousands of different styles. It has attracted a great deal of attention in research in recent years. In this paper, based on the notion of sequence alignment, we present a citation parser called BibPro that extracts components of a citation string. To demonstrate the efficacy of BibPro, we conducted experiments on three benchmark data sets. The results show that BibPro achieved over 90 percent accuracy on each benchmark. Even with citations and associated metadata retrieved from the web as training data, our experiments show that BibPro still achieves a reasonable performance.

Scholars usually spend great deal of time on searching and reading papers of key researchers. However, to objectively determine key researcher of a topic relies on several measurements, such as publication, citation, recent academic activities. In this paper, a prototype of scholars searching and recommendation system based on a web mining approach in expert finding system is proposed. The system gives and recommends the ranking of scholars and turns out top-k scholars. A new ranking measure is designed, namely p-index, to reveal the scholar ranking of a certain field. We use a real-world dataset to test the robustness, the experiment results show our approach outperforms other existing approaches and users are highly interested in using the system again.

Researchers usually present their publication records (we call citation records in this paper) on publication lists on the Web, which could be an important data source for many applications to collect more publication records than from some digital libraries, such as DBLP. However, it is still not easy to design an algorithm to extract citation records from publication lists because of the diversity of page layouts and citation formats. In this paper, we propose an automatic approach to extract citation records from publication list pages by utilizing two properties. First, citation records are usually represented as nodes at the same level in the DOM tree. Second, citation records in the same page are presented by similar HTML tags. Extensive experiments are conducted to measure the effects of all parameters and system performance. Experiment results show that our approach performs stable and well (with 86.2% of F-measure on average).

How to rapidly disseminate a large-sized file to many recipients is a fundamental problem in many applications, such as updating software patches and distributing large scientific data sets. In this paper, we present the Bee protocol, which is a cooperative peer-to-peer data dissemination protocol aiming at minimizing the maximum dissemination time for all peers to obtain time-critical data, such as critical patch updates. Bee is a decentralized protocol that organizes peers into a randomized mesh-based overlay and each peer only works with local knowledge. We devise a slowest peer first strategy to boost the speed of dissemination, and a topology adaptation algorithm that provides the most efficient utilization of the network capacity. Bee is designed to support network heterogeneity and deal with the flash crowd arrival pattern without sacrificing the dissemination speed. We present experimental results on the performance of Bee in terms of dissemination time and show that its performance can approach lower bound of the maximum dissemination time.

In this paper, expert-finding problem is transformed to a classification issue. We build a knowledge database to represent the expertise characteristic of domain from web information constructed by collaborative intelligence, and an incremental learning method is proposed to update the database. Furthermore, results are ranked by measuring the correlation in the concept network from online encyclopedia. In our experiments, we use the real world dataset which comprise 2,701 experts who are categorized into 8 expertise domains. Our experimental results show that the expertise knowledge extracted from collaborative intelligence can improve efficiency and effect of classification and increase the precision of ranking expert at least 20%.

Building an expert finding system is very important for many applications especially in the academic environment. Previous work uses e-mails or Web pages as corpus to analyze the expertise for each expert. In this paper, we present an Expert Finding System, abbreviated as EFS to build experts' profiles by using their journal publications. For a given proposal, the EFS first looks up the Wikipedia Web site to get relative link information, and then list and rank all associated experts by using those information. In our experiments, we use a real-world dataset which comprises of 882 people and 13,654 papers, and are categorized into 9 expertise domains. Our experimental results show that the EFS works well on several expertise domains like ldquoArtificial Intelligencerdquo and ldquoImage & Pattern Recognitionrdquo etc.

Many efforts in past years have been made to lower the linguistic barriers for non-native English speakers to access the Internet. Internet standard RFC 3490, referred to as IDNA (Internationalizing Domain Names in Applications), focuses on access to IDNs (Internationalized Domain Names) in a range of scripts that is broader in scope than the original ASCII. However, the use of character variants that have similar appearances and/or interpretations could create confusion. A variant IDL (Internationalized Domain Label), derived from an IDL by replacing some characters with their variants, should match the original IDL; and thus a variant IDN does. In RFC 3743, referred to as JET (Joint Engineering Team) Guidelines, it is suggested that zone administrators model this concept of equivalence as an atomic IDL package. When an IDL is registered, an IDL package is created that contains its variant IDLs generated according to the zone-specific Language Variant Tables (LVTs). In addition to the registered IDL, the name holder can request the domain registry to activate some of the variant IDLs, free or by an extra fee. The activated variant IDLs are stored in the zone files, and thus become resolvable. However, an issue of scalability arises when there is a large number of variant IDLs to be activated. In this article, the authors present a resolution protocol that resolves the variant IDLs into the registered IDL, specifically for Han character variants. Two Han characters are said to be variants of each other if they have the same meaning and are pronounced the same. Furthermore, Han character variants usually have similar appearances. It is not uncommon that a Chinese IDL has a large number of variant IDLs. The proposed protocol introduces a new RR (resource record) type, denoted as VarIdx RR, to associate a variant expression of the variant IDLs with the registered IDL. The label of the VarIdx RR, denoted as the variant index, is assigned by an indexing function that is designed to give the same value to all of the variant IDLs enumerated by the variant expression. When one of the variant IDLs is accessed, Internet applications can compute the variant index, look up the VarIdx RRs, and resolve the variant IDL into the registered IDL. The authors examine two sets of Chinese IDLs registered in TWNIC and CNNIC, respectively. The results show that for a registered Chinese IDL, a very small number of VarIdx RRs, usually one or two, are sufficient to activate all of its variant IDLs. The authors also represent a Web redirection service that employs the proposed resolution protocol to redirect a URL addressed by a variant IDN to the URL addressed by the registered IDN. The experiment results show that the proposed protocol successfully resolves the variant IDNs into the registered IDNs.

The content distribution techniques have recently started embracing peer-to-peer system as an alternative to the client-server architecture, such as BitTorrent system. BitTorrent system offers a scale mechanism for distributing a large volume of data to a set of peers over the Internet, but it is not designed for minimizing the time taken for all peers to receive the file. As a result, the peers of BitTorrent system may suffer a long download time, specifically the narrow-band peers. In this paper, in order to reduce the download time of BitTorrent, we propose a weighty piece selection strategy instead of the local rarest first strategy in BitTorrent. The proposed strategy is based on the greedy concept that a peer assigns each missing piece a weight according to total number of neighbor's downloaded pieces. The peer selects the missing piece with the highest priority for next download. This strategy can speed up the cooperation between heterogeneous peers while making the BitTorrent more efficient in terms of the average download time and the total elapsed time. The simulation results show that weighty piece selection strategy can improve more than 15% average download time and reduce in average 60% total elapsed time than the BitTorrent system.

Finding and keeping track of other researchers' publication lists is an essential activity for every researcher, because they often contain citations not found elsewhere and may provide access to information, such as slides and talks, which can help other researchers keep abreast of state-of- the-art knowledge and technology. There are many different ways to generate publication list web pages, and a researcher may have several different versions of a publication list on the Web because he holds different positions. So it is difficult to find the correct publication list web page from the top results retrieved from search engines, especially when we only know the name of the researcher. Very few works have addressed the problem. In this paper, we propose a system called the "publication list Web page finder" (PLF), which can automatically find the publication list Web pages for a given researcher's name. The PLF system is an automatic and language-independent system, and its main idea is that publication list Web pages often contain many citations about a specific researcher, so the system uses those citations as clues to find out publication list web pages. Our experimental results show that the PLF system outperforms other approaches, especially when a researcher has multiple publication list Web pages.

The vast number of expressed sequence tags (ESTs) in public databases provides an important resource for comparative and functional genomics. A variety of methods based on homology search or domain profile search have been developed to functionally annotate protein domains in ESTs. However, these methods either ignore potentially valuable information from the homologues beyond the top N hits, or they are extremely time consuming. We provide an efficient and novel tool, called E2D (EST to Domain), which functionally annotates anonymous ESTs by recognizing potential domains from the enlarged hit proteins. Comparison with InterProScan shows that E2D is more efficient and effective for domain recognition. Additionally, we achieve 87.5% agreement with existing GO function annotations in TIGR through domain-GO mapping, which demonstrates the efficacy of our approach

The most prevalent peer-to-peer (P2P) application till today is file sharing, and unstructured P2P networks can support inherent heterogeneity of peers, are highly resilient to peers’ failures, and incur low overhead at peer arrivals and departures. Dynamic querying (DQ) is a new flooding technique which could estimate a proper time-to-live (TTL) value for a query flooding by estimating the popularity of the searched files, and retrieve sufficient results under controlled flooding range for reducing network traffic. Recent researches show that a large amount of peers in the P2P file sharing system are the free-riders, and queries are seldom hit by those peers. The free-riders problem causes a large amount of redundant messages in the DQ-like search algorithm. In this paper, we proposed a new search algorithm, called "AntSearch", to solve the problem. In AntSearch, each peer maintains its hit rate of previous queries, and records a list of pheromone values of its immediate neighbors. Based on the pheromone values, a query is only flooded to those peers which are not likely to be the free-riders. Our simulation results show that, compared with DQ and its enhanced algorithm DQ+, the AntSearch algorithm averagely reduces 50% network traffic at almost the same search latency as DQ+, while retrieving sufficient results for a query with a given required number of results.

Searching for information about a particular person is a common activity on search engines. However, current search engines do not provide any special function for search a person. Previous research has solved the problem by using additional background knowledge, such as a friend list, to cluster the searched Web pages. However, it is still difficult to retrieve and choose suitable background knowledge. In this paper, we propose a Web appearance disambiguation (WAD) system to solve the problem by only using the hyperlink structures between Web pages. The key idea of the WAD system is to find out smaller node motifs as evidences of close relationship between pages for clustering searched Web pages. Our experimental results show that, under no background knowledge, the performance of the WAD system achieves 70% for the F-measure

In this paper we focus on building a large scale keyword search service over structured peer-to-peer (P2P) networks. Current state-of-the-art keyword search approaches for structured P2P systems are based on inverted list intersection. However, the biggest challenge in those approaches is that when the indices are distributed over peers, a simple query may cause a large amount of data to be transmitted over the network. We propose a new P2P keyword search scheme, called "Proof", to reduce network traffic for queries. The key idea is storing a content summary for each Web page in the inverted list, so that a query can be processed by only transmitting a small size of candidate results. Our simulation results showed that, compared with previous DHT-based P2P systems, Proof can dramatically reduce network traffic and computation time. It provides 100% precision and 90.09% recall of search results, at an acceptable cost of storage overhead, even when the number of peers and documents increases continually

UNLABELLED: In this article, we combined EST information from the UniGene database and orthologous relationships from the Ensembl database to construct a ZooDDD database. The primary function of ZooDDD is to mine evolutionary conserved, highly expressed, tissue-specific orthologues in model animals. The candidate genes of interest derived from the ZooDDD database will provide biologists with a good step for comparing the expression, functions and evolution of animal genomes. AVAILABILITY: http://bio301.iis.sinica.edu.tw/~ZooDDDNew/main.php.

Traffic smoothing is an efficient means to reduce the bandwidth requirement for transmitting a variable-bit-rate video stream. Several traffic-smoothing algorithms have been presented to offline compute the transmission schedule for a prerecorded video. For live video applications, Sen present a sliding-window algorithm, referred to as SLWIN(k), to online compute the transmission schedule on the fly. SLWIN(k) looks ahead W video frames to compute the transmission schedule for the next k frametimes, where klesw. Note that W is upper bounded by the initial delay of the transmission. The time complexity of SLWIN(k) is O(W*N/k) for an N frame live video. In this paper, we present an O(N) online traffic-smoothing algorithm and two variants, denoted as FOS, FOS1 and FOS2, respectively. Note that O(N) is a trivial lower bound of the time complexity of the traffic-smoothing problem. Thus, the proposed algorithm is optimal. We compare the performance of our algorithms with SLWIN(k) based on several benchmark video clips. Experiment results show that FOS2, which adopts the aggressive workahead heuristic, further reduces the bandwidth requirement and better utilizes the client buffer for real-time interactive applications in which the initial delays are small

The composition of traditional domain names are restricted to ASCII letters, digits, and hyphens (abbreviated as LDH). This makes it difficult for many to use their native language to name and access their Internet hosts. The IETF IDN (Internationalized Domain Name) Working Group proposes a mechanism, IDNA (Internationalizing Domain Names in Applications), for internationalized access to multilingual domain names. The proposal uses a preparation process that converts a Unicode IDN into an ACE (ASCII Compatible Encoding) string that uses only LDH. Thus, applications can look up the ACE string by using the existing DNS infrastructure. However, some of the domain name strings embedded in multilingual content do not have any charset tag so they cannot appropriately be converted into ACE strings. We noticed that many Internet applications allow users to use non-ASCII domain names. We were motivated to design an architecture for IDN resolution as well as to minimize the cost of modifying legacy Internet applications. We specifically focus on designing an IDN server proxy, which is located on the domain name server side, to handle domain names in multiple encodings. In this article, we study several architecture design issues including detection of charset encoding, routing of non-ACE IDN lookup requests, and so on.With respect to these design issues, we present an IDN server proxy architecture which stores ACE IDNs in domain name servers. Note that traditional domain name servers can be used without modification. An IDN server proxy, called Octopus, is employed on the domain name server side. Octopus converts a non-ACE IDN string into ACE upon receiving an IDN lookup request from remote users or autonomous systems. The ACE string is then forwarded to backend domain name servers (where the traditional domain names and ACE IDNs are stored) for further processing. This allows Internet users to access IDNs without having to upgrade their software.Based on the design and implementation of Octopus, we deployed a CDN (Chinese domain name) trial in July 2002. In this article, we present the results of testing Octopus IDN lookup functions as well as our experiences in providing CDN Web services. Several types of errors can occur if applications are unable to handle IDNs adequately. For example, a Web browser may erroneously parse an IDN within a URL. Many legacy Web servers are unable to process the IDN of a virtual host. Web application servers may have trouble completing some actions such as redirecting Web pages to alternative Web pages. Our studies help service providers understand potential problems when non-ASCII domain names are used and the best common practice at this stage. As well, the experiences give some guidance for software developers to develop IDNA-compliant Internet applications.

Active queue management (AQM) schemes have motivated many researchers to investigate more effective methods to control network congestion. Most AQM schemes are evaluated by their designers on the basis of router-centric metrics, such as queuing delay, link utilization and packet drop ratio. These metrics are important to network operators but they may not reflect the quality of service delivered to end-users. In this paper we propose a method aimed to provide users with better services in terms of end-to-end delay and packet loss ratio. The method captures a significant traffic increase at an early stage and signals TCP sources to slow down. In this way, TCP can quickly adjust the transmission rate, and thereby prevent overloading the network. In addition to RED, another two prominent AQM schemes, namely, random early marking (REM) and adaptive RED (ARED), are compared with the proposed method. Simulation results show that under various network loads and a range of network propagation delays, our method can achieve lower end-to-end delay and packet loss ratio, compared with all aforementioned schemes.

We address the issue of providing highly informative annotations using information revealed by the structured vocabularies of gene ontology (GO). For a target, a set of candidate terms used to infer the target's property is collected and forms a unique distribution on the GO directed acyclic graph (DAG). We propose a generic and adaptive algorithm - GOMIT, which bases on term distributions and GO hierarchical characteristics to assign correct annotations for a target. We establish a quantitative model with parameters that can be framed for optimal performance for different applications. We propose several criteria for evaluating GOMIT's performance, and conducted three experiments involving a) automated functional annotations, b) biological annotations of microarray data clusters and c) protein family GO assignments. In these experiments, we used our proposed criteria to compare GOMIT with other algorithms. Results not only reflect GOMIT's generality and adaptability, but also suggest that GOMIT is better or comparable to other works for assigning correct annotations.

We address the issue of providing highly informative and comprehensive annotations using information revealed by the structured vocabularies of gene ontology (GO). For a target, a set of candidate terms for inferring target properties is collected and form a unique distribution on the GO directed acyclic graph (DAG). We propose a novel ontology-based clustering algorithm $CLUGO, which considers GO hierarchical characteristics and the clustering of term distributions. By identifying significant groups in the distributions, CLUGO assigns comprehensive and correct annotations for a target. According to the results of experiments with automated sequence functional annotations, CLUGO represents a considerable improvement over our previous work - GOMIT in terms of recall while maintaining a similar level of precision. We conclude that given a GO candidate term distribution, CLUGO is an efficient ontology-based clustering algorithm for selecting comprehensive and correct annotations.

To increase the commercial value and accessibility of pages, most content sites tend to publish their pages with intrasite redundant information, such as navigation panels, advertisements, and copyright announcements. Such redundant information increases the index size of general search engines and causes page topics to drift. In this paper, we study the problem of mining intrapage informative structure in news Web sites in order to find and eliminate redundant information. Note that intrapage informative structure is a subset of the original Web page and is composed of a set of fine-grained and informative blocks. The intrapage informative structures of pages in a news Web site contain only anchors linking to news pages or bodies of news articles. We propose an intrapage informative structure mining system called WISDOM (Web intrapage informative structure mining based on the document object model) which applies Information Theory to DOM tree knowledge in order to build the structure. WISDOM splits a DOM tree into many small subtrees and applies a top-down informative block searching algorithm to select a set of candidate informative blocks. The structure is built by expanding the set using proposed merging methods. Experiments on several real news Web sites show high precision and recall rates which validates WISDOM'S practical applicability.

Fragment assembly is attracting intense research interest as a means of predicting protein structure from sequences. Success requires a good library of local structures (i.e. fragments) to serve as building blocks for whole protein reconstruction. Here, we describe a novel two-stage clustering scheme for identifying recurrent local structures and deriving fragment libraries. Parameters that represent cluster compactness, distinctiveness, and coverage were used for evaluating library quality. According to test results, our system was capable of approximating protein structures with smaller library sets at a level of accuracy comparable to or better than methods previously reported by others.

Due to the growth of dynamic page generation techniques, the amount and the complexity of Web pages has been increasing explosively, as has the information contained within Web pages. Redundant and irrelevant information is distributed and mixed throughout a page, making it difficult to automatically identify the useful information in that page. Consequently, we propose an information hierarchy in this paper, and, from that hierarchy, we can extract the significance and the relationship value of information contained within a Web page. We can then use this hierarchical structure to create a new browsing process. Our DOM-based Information Space Adsorption (DOMISA) system applies information theory to map information in a page into an information space, and our gradient tree adsorption (GTA) process uses the document object model (DOM) trees of pages to build information hierarchies. Experiments on several commercial news Web sites show high precision and recall rates achieved by DOMISA in determining information clusters of pages which validates its practical applicability to Web sites.

Abstract Motivation: Synteny mapping, or detecting regions that are orthologous between two genomes, is a key step in studies of comparative genomics. For completely sequenced genomes, this is increasingly accomplished by whole-genome sequence alignment. However, such methods are computationally expensive, especially for large genomes, and require rather complicated post-processing procedures to filter out non-orthologous sequence matches. Results: We have developed a novel method that does not require sequence alignment for synteny mapping of two large genomes, such as the human and mouse. In this method, the occurrence spectra of genome-wide unique 16mer sequences present in both the human and mouse genome are used to directly detect orthologous genomic segments. Being sequence alignment-free, the method is very fast and able to map the two mammalian genomes in one day of computing time on a single Pentium IV personal computer. The resulting human–mouse synteny map was shown to be in excellent agreement with those produced by the Mouse Genome Sequencing Consortium (MGSC) and by the Ensembl team; furthermore, the syntenic relationship of segments found only by our method was supported by BLASTZ sequence alignment. Availability: The source code of our method and the resulting human–mouse synteny maps have been placed at http://synteny.ibms.sinica.edu.tw/ for free access. Supplementary information: Seven supplementary figures can be found at the same website.

Travel time is a fundamental measure in transportation. Accurate travel-time prediction also is crucial to the development of intelligent transportation systems and advanced traveler information systems. We apply support vector regression (SVR) for travel-time prediction and compare its results to other baseline travel-time prediction methods using real highway traffic data. Since support vector machines have greater generalization ability and guarantee global minima for given training data, it is believed that SVR will perform well for time series analysis. Compared to other baseline predictors, our results show that the SVR predictor can significantly reduce both relative mean errors and root-mean-squared errors of predicted travel times. We demonstrate the feasibility of applying SVR in travel-time prediction and prove that SVR is applicable and performs well for traffic data analysis.

We study the problem of mining the informative structure of a news Web site that consists of thousands of hyperlinked documents. We define the informative structure of a news Web site as a set of index pages (or referred to as TOC, i.e., table of contents, pages) and a set of article pages linked by these TOC pages. Based on the Hyperlink Induced Topics Search (HITS) algorithm, we propose an entropy-based analysis (LAMIS) mechanism for analyzing the entropy of anchor texts and links to eliminate the redundancy of the hyperlinked structure so that the complex structure of a Web site can be distilled. However, to increase the value and the accessibility of pages, most of the content sites tend to publish their pages with intrasite redundant information, such as navigation panels, advertisements, copy announcements, etc. To further eliminate such redundancy, we propose another mechanism, called InfoDiscoverer, which applies the distilled structure to identify sets of article pages. InfoDiscoverer also employs the entropy information to analyze the information measures of article sets and to extract informative content blocks from these sets. Our result is useful for search engines, information agents, and crawlers to index, extract, and navigate significant information from a Web site. Experiments on several real news Web sites show that the precision and the recall of our approaches are much superior to those obtained by conventional methods in mining the informative structures of news Web sites. On the average, the augmented LAMIS leads to prominent performance improvement and increases the precision by a factor ranging from 122 to 257 percent when the desired recall falls between 0.5 and 1. In comparison with manual heuristics, the precision and the recall of InfoDiscoverer are greater than 0.956.

In this paper, we study the problem of designing an efficient ARQ algorithm for supporting real-time video streaming applications. This problem differs from traditional non-real-time error control problem in which a late arrival packet can seriously degrade the video playback quality. It is interesting to notice that if a lost packet is detected while the client buffer is running at a high position, then the probability to recover the lost packet is also high. In this paper, we present a new error control algorithm, called BREC (buffer-controlled retransmission-based error control), to dynamically control the buffer running at a specific level. By the experiments on a true VOD system in which we implement the BREC scheme, the packet loss rate can be reduced by an order of magnitude. We also show that the performance can be further improved by detecting the rate of changes in running buffer positions and use it to enhance the ability of buffer position control. Both analytical model and experimental results show that our mechanism significantly decrease packet loss and improves QoS even if a client, such as set-top box, PDA (personal data assistant) or cellular phone, preserves only a limited amount of playback buffer (200K bytes of memory is used in our experiments).

Benefiting from the growth of techniques of dynamic page generation, the amount and the complexity of Web pages increase explosively. The structures of Web pages which are dynamically generated by the same templates are thus similar to one another and are usually assembled by a set of fundamental information clusters These neighboring information clusters usually represent the similar semantics and form a larger cluster with the more generalized information. The hierarchical structure generated by information clusters in a bottom-up manner is called the information hierarchy of a page. We study the problem of mining the information hierarchies of pages in Web sites to recognize the information distribution of pages within the multilevel, multigranularity configurations. Explicitly, we propose an information clustering system that applies a top-down information centroid searching algorithm and a multigranularity centroid converging process on the document object model (DOM) trees of pages to build the information hierarchies of pages. Experiments on several real news Web sites show the high precision and recall rates of the proposed method on determining information clusters of pages and also validate its practical applicability to real Web sites.

In this paper, we study the problem of mining the informative structure of a news Web site which consists of thousands of hyperlinked documents. We define the informative structure of a news Web site as a set of index pages (or referred to as TOC, i.e., table of contents, pages) and a set of article pages linked by TOC pages through informative links. It is noted that the Hyperlink Induced Topics Search (HITS) algorithm has been employed to provide a solution to analyzing authorities and hubs of pages. However, most of the content sites tend to contain some extra hyperlinks, such as navigation panels, advertisements and banners, so as to increase the add-on values of their Web pages. Therefore, due to the structure induced by these extra hyperlinks, HITS is found to be insufficient to provide a good precision in solving the problem. To remedy this, we develop an algorithm to utilize entropy-based Link Analysis on Mining Web Informative Structures. This algorithm is referred to as LAMIS. The key idea of LAMIS is to utilize information entropy for representing the knowledge that corresponds to the amount of information in a link or a page in the link analysis. Experiments on several real news Web sites show that the precision and the recall of LAMIS are much superior to those obtained by heuristic methods and conventional ink analysis methods.

Due to advances in network technologies, providing streaming services over the Internet has gained in popularity. Because a video stream is in compressed format, it is naturally with the variable bit rate (VBR) property and its traffic is highly burst. With the installation of a video proxy between access networks (e.g. local area networks, LAN) and backbone networks (e.g. wide area networks, WAN), video staging is proposed to cache part of the requested video into the video proxy close to clients. In this mechanism, the video can be streamed using a constant bit rate (CBR) network service across the backbone WAN and the WAN bandwidth requirement can be significantly reduced. In this paper, we propose a new approach, called "caching selected after smoothing" (CSAS), to handling video staging. The aim of the CSAS algorithm is to integrate our previous video caching and smoothing technique so as to reduce the required WAN bandwidth even more. Experiments on benchmark videos using different evaluation indices, including the proxy storage requirement, the WAN bandwidth requirement, and the WAN bandwidth utilization, show that our approach is more effective than the conventional "cut after smoothing" (CAS) algorithm.

In this paper, we propose a new approach to discover informative contents from a set of tabular documents (or Web pages) of a Web site. Our system, InfoDiscoverer, first partitions a page into several content blocks according to HTML tag in a Web page. Based on the occurrence of the features (terms) in the set of pages, it calculates entropy value of each feature. According to the entropy value of each feature in a content block, the entropy value of the block is defined. By analyzing the information measure, we propose a method to dynamically select the entropy-threshold that partitions blocks into either informative or redundant. Informative content blocks are distinguished parts of the page, whereas redundant content blocks are common parts. Based on the answer set generated from 13 manually tagged news Web sites with a total of 26,518 Web pages, experiments show that both recall and precision rates are greater than 0.956. That is, using the approach, informative blocks (news articles) of these sites can be automatically separated from semantically redundant contents such as advertisements, banners, navigation panels, news categories, etc. By adopting InfoDiscoverer as the preprocessor of information retrieval and extraction applications, the retrieval and extracting precision will be increased, and the indexing size and extracting complexity will also be reduced.

Personal communication service (PCS) networks offer mobile users multimedia applications with different quality-of-service (QoS) and bandwidth requirements. This paper proposes a distributed call admission algorithm to provide QoS guarantees for multimedia traffic carried in a heterogeneous PCS network, where the parameters (e.g., number of channels, new and hand-off call arrival rates) of cells can be varied. The algorithm is based on the moveable boundary scheme that dynamically adjusts the number of channels for different types of traffic. With the moveable boundary scheme, the bandwidth can be utilized efficiently while satisfying the QoS requirements for different types of traffic. In addition, by taking the effect of hand-off traffic into account, we develop an analytical model for the network using the proposed algorithm. Using our model, the impact of hot-spot traffic caused by hand-offs can be effectively analyzed. The analytical model is validated by simulation.

This paper presents an intelligent Internet information system, Automatic Classifier for the Internet Resource Discovery (ACIRD), which uses machine learning techniques to organize and retrieve Internet documents. ACIRD consists of a knowledge acquisition process, document classifier, and two-phase search engine. The knowledge acquisition process of ACIRD automatically learns classification knowledge from classified Internet documents. The document classifier applies learned classification knowledge to classify newly collected Internet documents into one or more classes. Experimental results indicate that ACIRD performs as well or better than human experts in both knowledge acquisition and document classification. By using the learned classification knowledge and the given class lattice, the ACIRD two-phase search engine responds to user queries with hierarchically structured navigable results (instead of a conventional flat ranked document list), which greatly aids users in locating information from numerous, diversified Internet documents.

The segmented channel-routing problem arises in the context of row-based field programmable gate arrays (FPGAs). Since the K -segment channel-routing problem is NP-complete for K ≥ 2, an efficient algorithm using the weighted bipartite-matching approach is developed for this problem. Connections that;form a maximum clique are chosen first to be routed to the segmented channel. Then, another maximum clique of the remained connections is routed until all connections have been processed. In addition, a powerful “unroutability check” algorithm is uniquely proposed to tell whether the horizontal switches in an interval of the segmented channel are sufficient for routing or not. Hence, we can precisely discriminate the routable and the unroutable ones from all the test cases. As shown in the experiments, average discrimination ratios of 98.8% and 99.4% are obtained for the 2-segmentation and 3-segmentation models, respectively. Moreover, when applying our routing algorithm to the analyzed nonunroutable cases, a routing failure ratio of 1.5% is reported for the 2-segmentation model, compared to Zhu and Wong's 5.9%; also, a routing failure ratio of 0.8% (less than their 4.7%) is obtained for the 3-segmentation model. In total, the routing failure ratio of our routing algorithm is less than 21% of Zhu and Wong's.

In this paper, a new two-level bipartitioning algorithm TLP, combining a hybrid clustering technique with an iterative improvement based partitioning process, is proposed. The hybrid clustering algorithm consisting of a local bottom-up clustering technique to merge modules and a global top-down ratio-cut technique for decomposition can be used to reduce the partitioning complexity and improve the performance. To generate a high-quality partitioning solution, a module migration based partitioning algorithm MMP is also proposed as the base partitioner for the TLP algorithm. The MMP algorithm implicitly promotes the move of clusters during the module migration processes by paying more attention to the neighbors of moved modules, relaxing the size constraints temporarily during the migration process, and controlling the module migration direction. Experimental results obtained show that the TLP algorithm generates stable and high-quality partitioning results. The TLP algorithm improves the unstable property of module migration based algorithms such as FM and STABLE in terms of the average net cut value. On the other hand, TLP outperforms MELO, GFM/sub t/ and CDIP/sub LA3/ by 23%, 7%, and 10%, respectively and is competitive with hMetis, ML/sub c/ and LSR/MFFS which have generated better results than many recent state-of-the-art partitioning algorithms.

Traffic smoothing for delivery of online VBR media streams is one of the most important problems in designing multimedia systems. Given available client buffer and a window-sliding size, conventional approaches try to reduce bandwidth allocated in each window. However, they can not lead to the minimization of bandwidth allocated for transmitting the entire stream. Although a window-sliding approach was introduced previously to further reduce the bandwidth allocated, it was computational costly. In this paper, an effective and efficient online traffic-smoothing scheme is proposed. Different from the conventional static window-sliding approaches, this approach dynamically decides the suitable window-sliding size to online smooth the bursty traffic. Then, an aggressive workahead scheme is applied in transmitting the entire stream. By examining different media streams, the approach has a small bandwidth, high bandwidth utilization and small computation cost. Considering the online transmission of a Star War movie, our approach result is 13% less for the bandwidth and 4% less for the network idle rate than SLWIN(1). Comparing the number of window sliding, our approach is 75% less than SLWIN(1). The relations between the characteristic of the input traffic and the behavior of obtained scheduling results are discussed. Finally, an extension of the proposed approach to resolve the latency and quality tolerance applications is also introduced.

Given a pre-recorded VBR video, we have proposed an O(n) algorithm to smooth the transmission schedule with the minimum required resources. N is the number of video frames. As n is usually very large and varying for different videos, it is not suitable for online computation. To facilitate resource management and admission control for QoS (quality-of-service) guarantees, we need to explore the relations among the required resources. Thus, whenever a new request is presented, the admission control procedure can easily check the required resources against the available resources and decides to admit this new request or not. To compute these relations (such as rate-buffer and rate-delay), a native algorithm takes O(n/sup 3/) time complexity. An O(n log n) algorithm is proposed to characterize the low-bounds of resources allocated for transmitting a pre-recorded VBR video. Having these pre-computed functions, the admission control procedure is as simple as a chart look-up with O(1) time complexity to allocate the required resources.

In this paper, we present a system that extracts and generalizes terms from Internet documents to represent classification knowledge of a given class hierarchy.We propose a measurement to evaluate the importance of a term with respect to a class in the class hierarchy, and denote it as support.With a given threshold, terms with high supports are sifted as keywords of a class, and terms with low supports are filtered out.To further enhance the recall of this approach, Mining Association Rules technique is applied to mine the association between terms.An inference model is composed of these association relations and the previously computed supports of the terms in the class.To increase the recall rate of the keyword selection process.we then present a polynomialtime inference algorithm to promote a term, strongly associated to a known keyword, to a keyword.According to our experiment results on the collected Internet documents from Yam search engine, we show that the proposed methods In the paper contribute to refine the classification knowledge and increase the recall of keyword selection. 'In the paper, we use "term" as word or phrase, which is extracted from the Internet documents, rather than use "keyword"."Keyword" is representative to the concept, while "term" is probably nonrepresentatlve.

A fast and efficient algorithm for technology mapping of electrically programmable gate arrays (EPGAs) is proposed. This Hmap algorithm covers the Boolean network with programmed logic modules bottom-up. The covering operation is based on collapsing the fanins of a node to form a bigger supernode such that fewer clusters are needed to be detected. Then Boolean matching is used to detect whether the collapsed supernode can be mapped into a logic module by looking up an extended GBDD hash table. The use of this table look-up matching can shorten the matching time significantly. As shown in the experiments, the average running time of Hmap is 20 times faster than that of MIS-pga2.

Many real-time, multimedia applications (e.g., teleconferencing) have been successful deployed over the Internet and its overlayed multicast backbone network (MBONE). However poor, unpredictable transfer performance of the continuous media in Internet is common and inevitable due to the intrinsic "best-effort" transport techniques used. Before the full-blown ATM networks or any other networks with QoS offerings are in place, Ethernets are still the most popular networks in today's office environments. We investigate how application-level traffic shaping (spacing) can help to reduce the possibly drastic performance degradation of real-time multimedia conferencing applications on a heavily-loaded Ethernet. An experimental testbed is constructed and all the application software is implemented in our laboratory. Performance results measured from the testbed are presented to provide insights of how the performance degradations occur and to illustrate how a real-time application can lessen the situation.

An arbitrary single-layer detailed routine L of a set of two-terminal nets is considered. The necessary and sufficient condition for a layout to have minimum length under homotopic transformations (i.e. without changing the given global routing) is presented. Based on the proposed classification and the motion of line-segment visibility, an exact algorithm that minimizes the total wire length of L is given. The proposed algorithm runs in O(n/sup 2/) time, where n is the number of bends in L.>

The authors present a clock tree regeneration algorithm for improving both the wirability and performance of VLSI chip designs. After circuit placement, they modify the clock trees originally specified by logic designs utilizing the geometrical information derived from the placement. First, a bipartite bottleneck matching approach is applied to minimize the longest driver to clock pin length. Then a linear assignment approach is used to optimize the total driverpin length. The experimental results are extremely encouraging.>

The problem of finding a minimum diameter spanning tree (MDST) of a set of n points in the Euclidean space is considered. The diameter of a spanning tree is the maximum distance between any two points in the tree. A characterization of an MDST is given and a $\theta (n^3)$-time algorithm for solving the problem is presented. The authors also show that for a weighted undirected graph, the problem of determining if a spanning tree with total weight and diameter upper bounded, respectively, by two given parameters C and D exists is NP-complete. The geometric Steiner minimum diameter spanning tree problem, in which new points are allowed to be part of the spanning tree, is shown to be solvable in $O(n)$ time.

Consider a given single-layer detailed routing L of a set of two-terminal nets. The authors present necessary and sufficient conditions for a layout to have minimum length under homotopic transformations (i.e., without changing the given global routing). Based on the proposed classification and the notion of line-segment visibility, the authors present an exact algorithm that minimizes the total wire-length of L. The proposed algorithm runs in O(n/sup 2/) time, where n is the number of bends in L. For the class of x-monotone layouts (i.e., each vertical line crosses each wire once at most) an O(n log n) time algorithm is proposed.>

The problem of minimizing the number of power pads, in order to guarantee the existence of a planar routing of multiple power nets, is discussed. A general lower bound is derived, and a heuristic for the general problem is discussed. Several important special cases, including the case of three power nets, are examined, and optimal strategies for pad placement are presented. It is also shown that the general pad minimization problem is NP-complete.>

The layer assignment problem that arises in the design of a multichip module, a high-performance compact package for the interconnection of several hundred chips, is studied. The aim is to place each net in a x-y pair of layers, so as to minimize the number of such pairs. An approximation algorithm, running in O(nd) time is presented for minimizing the number of layers, where n is the number of nets and d is the (two-dimensional) density of the problem.>

An approach to constructing the rectilinear Steiner tree (RST) of a given set of points in the plane, starting from a minimum spanning tree (MST), is discussed. The main idea in this approach is to find layouts for the edges of the MST that maximize the overlaps between the layouts, thus minimizing the cost (i.e. wire length) of the resulting rectilinear Steiner tree. Two algorithms for constructing rectilinear Steiner trees from MSTs, which are optimal under the conditions that the layout of each edge of the MST is an L shape or any staircase, respectively, are described. The first algorithm has linear time complexity and the second algorithm has a higher polynomial time complexity. Steiner trees produced by the second algorithm have a property called stability, which allows the rerouting of any segment of the tree, while maintaining the cost of the tree, and without causing overlaps with the rest of the tree. Stability is a desirable property in VLSI global routing applications.>

We consider the problem of finding a minimum diameter spanning tree (MDST) of a set of n points in the Euclidean plane. The diameter of a spanning tree is the maximum distance between any two points in the tree. We give a characterization of an MDST and present a θ(n3 time algorithm for solving the problem. We also show that for a weighted undirected graph, the problem of determining if a spanning tree with total weight and diameter upper bounded, respectively, by two given parameters C and D exists is N P-complete. The geometrical minimum diameter Steiner tree problem, in which new points are allowed to be part of the spanning tree, is shown to be solvable in Ο(n) time.

We discuss a new approach to constructing the rectilinear Steiner tree (RST) of a given set of points in the plane, starting from a minimum spanning tree (MST). The main idea in our approach is to determine L-shaped layouts for the edges of the MST, so as to maximize the overlaps between the layouts, thus minimizing the cost (i.e., wire length) of the resulting RST. We describe a linear time algorithm for constructing a RST from a MST, such that the RST is optimal under the restriction that the layout of each edge of the MST is an L-shape. The RST's produced by this algorithm have 8-33% lower cost than the MST, with the average cost improvement, over a large number of random point sets, being about 9%. The running time of the algorithm on an IBM 3090 processor is under 0.01 seconds for point sets with cardinality 10. We also discuss a property of RST's called stability under rerouting, and show how to stabilize the RST's derived from our approach. Stability is a desirable property in VLSI global routing applications.

A polynomial time algorithm is given for constructing the minimum cost rectilinear Steiner tree (RST) that is derivable from a minimum spanning tree (MST) of a given point set, such that the MST edges have staircase layouts in the RST. RSTs produced by the algorithm have a property called stability, which enables the rerouting of any subset of the RST edges, while maintaining the cost of the RST, and not causing overlaps with each other or with the other RST edges.>