36787117
Parallelizing Support Vector Machines on Distributed Computers
Support Vector Machines (SVMs) suffer from a widely recognized scalability problem in both memory use and computational time. To improve scalability, we have developed a parallel SVM algorithm (PSVM), which reduces memory use through performing a row-based, approximate matrix factorization, and which loads only essential data to each machine to perform parallel computation. Let n denote the number of training instances, p the reduced matrix dimension after factorization (p is significantly smaller than n), and m the number of machines. PSVM reduces the memory requirement from O(n2) to O(np/m), and improves computation time to O(np2/m). Empirical study shows PSVM to be effective. PSVM Open Source is available for download at http://code.google.com/p/psvm/.
4409694
On route selection for interdomain traffic engineering
In this article we investigate a model of route selection for interdomain traffic engineering where routing to multiple destinations can be coordinated. We identify potential routing instability and inefficiency problems, and derive a set of practical guidelines to guarantee stability without global coordination. Using a realistic Internet topology, we show that route oscillations can happen even when a small number of ASes coordinate route selection for just a small number of destinations if the coordination does not follow our guidelines. Wc further extend our model so that ASes can adopt any route selection algorithms in a class of algorithms we call rational route selection algorithms; and the local ranking of routes of an AS can depend on ingress traffic patterns. We show that persistent route oscillations can happen in certain network settings even if the ASes strictly follow the constraints imposed by business considerations, and adopt any rational route selection algorithms.
4427518
On the stability of rational, heterogeneous interdomain route selection
The recent discovery of instability caused by the interaction of local routing policies of multiple ASes has led to extensive research on the subject. However, previous studies analyze stability under a specific route selection algorithm. In this paper, instead of studying a specific route selection algorithm, we study a general class of route selection algorithms which we call rational route selection algorithms. We present a sufficient condition to guarantee routing convergence in a heterogeneous network where each AS runs any rational route selection algorithm. Applying our general results, we study the potential instability of a network where the preference of an AS depends on not only its egress routes to the destinations but also its inbound traffic patterns (i.e., the distribution of incoming traffic from its neighbors). We show that there exist networks which will have persistent route oscillations even when the ASes strictly follow the constraints imposed by business considerations, and adopt any rational route selection algorithms.
49376
Pipelined van Emde Boas Tree: Algorithms, Analysis, and Applications
Priority queues are essential for various network processing applications, including per-flow queueing with quality-of-service (QoS) guarantees, management of large fast packet buffers, and management of statistics counters. In this paper, we propose a new data structure for implementing high-performance priority queues based on a pipelined version of the van Emde Boas tree. We show that we can achieve O(1) amortized time operations using our architecture, but we can achieve this algorithmic efficiency using only O (log log u) number of pipelined stages, where u is the size of the universe used to represent the priority keys.
4407504
Optimal ISP subscription for Internet multihoming: algorithm design and implication analysis
Multihoming is a popular method used by large enterprises and stub ISPs to connect to the Internet to reduce cost and improve performance. Recently researchers have studied the potential benefits of multihoming and proposed protocols and algorithms to realize these benefits. They focus on how to dynamically select which ISPs to use for forwarding and receiving packets, and assume that the set of subscribed ISPs is given a priori. In practice, a user often has the freedom to choose which subset of ISPs among all available ISPs to subscribe to. We call the problem of how to choose the optimal set of ISPs the ISP subscription problem. In this paper, We design a dynamic programming algorithm to solve the ISP subscription problem optimally. We also design a more efficient algorithm for a large class of common pricing functions. Using real traffic traces and realistic pricing data, we show that our algorithm reduces users' cost. Next we study how ISPs respond to users' optimal ISP subscription by adjusting their pricing strategies. We call this problem the ISP pricing problem. Using a realistic charging model, we formulate the problem as a non-cooperative game. We first prove that if cost is the only criterion used by a user to determine which subset of ISPs to subscribe to, at any equilibrium all ISPs receive zero revenue. We then study a more practical formulation in which different ISPs provide different levels of reliability and users choose ISPs to both improve reliability and reduce cost. We analyze this problem and show that at any equilibrium an ISP's revenue is positive and determined by its reliability.
9852672
NXG06-6: On the Efficient Implementation of Pipelined Heaps for Network Processing
Priority queues are often used in many network processing applications. Applications include sophisticated per-flow scheduling for providing advanced quality-of-service (QoS) guarantees, fast packet buffer memory management, and exact maintenance of statistics counters for real-time network measurements. In all these applications, the priority queues used must operate at very high-speeds, e.g. at 40 Gbps rates and beyond. One widely used data structure for implementing priority queues is the heap data structure. However, the logarithmic time complexity of heap operations is often too slow for increasingly fast line rates. To achieve constant time complexity, the pipelined heap structure has been proposed. In this paper, we describe new architecture techniques for the efficient implementation of pipelined heaps. In particular, we focus on aggressive memory management and pipelining techniques.
15500084
Understanding the Prediction of Transmembrane Proteins by Support Vector Machine using Association Rule Mining
With the efforts to understand protein structure, many computational approaches have been made recently. Among them, the support vector machine (SVM) methods have been recently applied and showed successful performance compared with other machine learning schemes. However, despite the high performance, the SVM approaches suffer from the problem of understandability since it is a black-box model. To overcome this limitation, this study attempted to combine the SVM with the association rule based classifier which can present the meaningful explanation about the prediction. To perform this task, a new association rule based classifier (PCPAR) was devised based on the existing classifier, CPAR, to handle the sequential data. PCPAR creates the patterns by merging the generated rules and then classifies the sequential data based on the pattern match. The experimental result presents the following: with sequential data, the PCPAR scheme shows better performance with respect to the accuracy and the number of generated patterns than CPAR method whether applied alone or combined with SVM. The combined scheme of SVMPCPAR generates more compact patterns than the combined scheme of SVM with decision tree, SVM DT, with similar performance. These patterns are easily understandable and biologically meaningful
4594972
New Fair Payment Protocols
Fair payment protocol is designed to guarantee fairness in electronic purchasing, that is, no party can falsely deny involvement in the transaction or having sent/received the specific items/payment. In this paper we first present an efficient fair payment protocol providing invisibility of TTP, timeliness, and standard RSA signatures as the final non-repudiation evidences. Then we present a second payment protocol which is the first one to provide abuse-freeness. Our protocols can be easily integrated into the existing electronic payment systems.
1947084
Fair Payment Protocols for E-Commerce
It has been widely accepted that fairness is a critical property for electronic commerce. Fair payment protocol is designed to guarantee fairness in a payment process over asynchronous network. Fairness means that when the protocol terminates, either both parties get their expected items, or neither does. In this paper we first present a new generic offline fair payment protocol with fairness, timeliness and invisibility of TTP. Then we introduce the property of abuse-freeness into electronic payment and implement a fair abuse-free payment protocol.
32406655
A Parallel Algorithm for Learning Bayesian Networks
Computing the expected statistics is the main bottleneck in learning Bayesian networks in large-scale problem domains. This paper presents a parallel learning algorithm, PL-SEM, for learning Bayesian networks, based on an existing structural EM algorithm (SEM). Since the computation of the expected statistics is in the parametric learning part of the SEM algorithm, PLSEM exploits a parallel EM algorithm to compute the expected statistics. The parallel EM algorithm parallelizes the E-step and M-step. At the E-step, PLSEM parallel computes the expected statistics of each sample; and at the M-step, with the conditional independence of Bayesian networks and the expected statistics computed at the E-step, PL-SEM exploits the decomposition property of the likelihood function under the completed data to parallel estimate each local likelihood function. PL-SEM effectively computes the expected statistics, and greatly reduces the time complexity of learning Bayesian networks.
16268564
FreeRank: implementing independent ranking service for multiplayer online games
Ranking is necessary for multiplayer online games to provide players with self-complacence and reference for choosing game counterparts. Most existing ranking solutions are tightly coupled with game applications of client-server architectures. In this paper, a novel scheme named FreeRank is proposed as a ranking service independent to specific architecture and detailed implementation of each individual game application. Based on a certificate-based framework and a reputation-based score-computing algorithm. FreeRank resolves the challenge of cheating prevention. Preliminary analysis and simulation results show that FreeRank is feasible and effective.