In this thesis, we study the power and limit of algorithms on various models, aiming at applications in distributed networks and databases. In distributed networks, graph algorithms are fundamental to many applications. We focus on computing random walks which are an important primitive employed in a wide range of applications but has always been computed naively. We show that a faster solution exists and subsequently develop faster algorithms by exploiting random walk properties leading to two immediate applications. We also show that this algorithm is optimal. Our technique in proving a lower bound show the first non-trivial connection between communication complexity and lower bounds of distributed graph algorithms. We show that this technique has a wide range of applications by proving new lower bounds of many problems. Some of these lower bounds show that the existing algorithms are tight. In database searching, we think of the database as a large set of multi-dimensional points stored in a disk and want to help the users to quickly find the most desired point. In this thesis, we develop an algorithm that is significantly faster than previous algorithms both theoretically and experimentally. The insight is to solve the problem on the streaming model which helps emphasize the benefits of sequential access over random disk access. We also introduced the randomization technique to the area. The results were complemented with a lower bound. We also initiat a new direction as an attempt to get a better query. We are the first to quantify the output quality using "user satisfaction" which is made possible by borrowing the idea of modeling users by utility functions from game theory and justify our approach through a geometric analysis.

Fluid mechanics of blood can be well approximated by a mixture model of a Newtonian fluid and deformable particles representing the red blood cells. Experimental and theoretical evidence suggests that the deformation and rheology of red blood cells is similar to that of phospholipid vesicles. Vesicles and red blood cells are both area preserving closed membranes that resist bending. Beyond red blood cells, vesicles can be used to investigate the behavior of cell membranes, intracellular organelles, and viral particles. Given the importance of vesicle flows, in this thesis we focus in efficient numerical methods for such problems: we present computationally scalable algorithms for the simulation of dilute suspension of deformable vesicles in two and three dimensions. Our method is based on the boundary integral formulation of Stokes flow. We present new schemes for simulating the three-dimensional hydrodynamic interactions of large number of vesicles with viscosity contrast. The algorithms incorporate a stable time-stepping scheme, high-order spatiotemporal discretizations, spectral preconditioners, and a reparametrization scheme capable of resolving extreme mesh distortions in dynamic simulations. The associated linear systems are solved in optimal time using spectral preconditioners. The highlights of our numerical scheme are that (i) the physics of vesicles is faithfully represented by using nonlinear solid mechanics to capture the deformations of each cell, (ii) the long-range, N-body, hydrodynamic interactions between vesicles are accurately resolved using the fast multipole method (FMM), and (iii) our time stepping scheme is unconditionally stable for the flow of single and multiple vesicles with viscosity contrast and its computational cost-per-simulation-unit-time is comparable to or less than that of an explicit scheme. We report scaling of our algorithms to simulations with millions of vesicles on thousands of computational cores.

Title from PDF of title page. / Document formatted into pages; contains 62 pages. / Thesis (M.S.E.E.)--University of South Florida, 2003. / Includes bibliographical references. / Text (Electronic thesis) in PDF format. / ABSTRACT: The rapid growth of the Internet, in the last few years, has generated a need to enhance the existing IP networks in the areas of availability, dependability and scalability in order to provide a mission critical networking environment. In contemporary IP networks, data packets are routed as a function of the destination address and a single metric such as hop-count or delay. This approach tends to cause message traffic to converge onto the same link, which significantly increases congestion and leads to unbalanced network resource utilization. One solution to this problem is provided by Traffic Engineering (TE), which uses, bandwidth guaranteed, Explicitly Routed Label Switched Paths (ER-LSPs). Due to the dramatic increase in the backbone speeds, current research focuses more on traffic engineering with LSPs for clear control over the traffic distribution in the network. / ABSTRACT: However, the growing popularity of the Internet is driving the Internet Service Providers to adapt new technologies in order to support multiple classes of applications with different characteristics and performance requirements. Multi-Protocol Label Switching (MPLS), which was proposed by the IETF provides essential facilities for traffic engineering and reliable QoS services for the Internet. MPLS networks provide the required flexibility for operators to manage their traffic with ER-LSPs. Even though conventional routing algorithms support the ER-LSP setup in MPLS networks, they are not efficient in link residual capacity information updates and limit resource utilization, which eventually leads to LSP failures and unbalanced network resource utilization. This thesis proposes a new architecture with a cluster based distributed routing algorithm to setup bandwidth guaranteed ER-LSPs in MPLS backbone networks. / ABSTRACT: The proposed routing algorithm confines the route discovery region in order to reduce the routing overhead and computes all possible routes from ingress node to egress node. Based on LSP requirements and network load conditions, the egress node selects the most suitable path from the available paths in order to setup the LSP. This routing scheme optimizes network resource utilization by evenly distributing traffic throughout the network. The Resource Reservation Protocol (RSVP) works in conjunction with the routing protocol for resource reservation and label distribution along the LSP. / System requirements: World Wide Web browser and PDF reader. / Mode of access: World Wide Web.

Stochastic and data-distributed optimization algorithms have received lots of attention from the machine learning community due to the tremendous demand from the large-scale learning and the big-data related optimization. A lot of stochastic and deterministic learning algorithms are proposed recently under various application scenarios. Nevertheless, many of these algorithms are based on heuristics and their optimality in terms of the generalization error is not sufficiently justified. In this talk, I will explain the concept of an optimal learning algorithm, and show that given a time budget and proper hypothesis space, only those achieving the lower bounds of the estimation error and the optimization error are optimal. Guided by this concept, we investigated the stochastic minimization of nonsmooth convex loss functions, a central problem in machine learning. We proposed a novel algorithm named Accelerated Nonsmooth Stochastic Gradient Descent, which exploits the structure of common nonsmooth loss functions to achieve optimal convergence rates for a class of problems including SVMs. It is the first stochastic algorithm that can achieve the optimal O(1/t) rate for minimizing nonsmooth loss functions. The fast rates are confirmed by empirical comparisons with state-of-the-art algorithms including the averaged SGD. The Alternating Direction Method of Multipliers (ADMM) is another flexible method to explore function structures. In the second part we proposed stochastic ADMM that can be applied to a general class of convex and nonsmooth functions, beyond the smooth and separable least squares loss used in lasso. We also demonstrate the rates of convergence for our algorithm under various structural assumptions of the stochastic function: O(1/sqrt{t}) for convex functions and O(log t/t) for strongly convex functions. A novel application named Graph-Guided SVM is proposed to demonstrate the usefulness of our algorithm. We also extend the scalability of stochastic algorithms to nonlinear kernel machines, where the problem is formulated as a constrained dual quadratic optimization. The simplex constraint can be handled by the classic Frank-Wolfe method. The proposed stochastic Frank-Wolfe methods achieve comparable or even better accuracies than state-of-the-art batch and online kernel SVM solvers, and are significantly faster. The last part investigates the problem of data-distributed learning. We formulate it as a consensus-constrained optimization problem and solve it with ADMM. It turns out that the underlying communication topology is a key factor in achieving a balance between a fast learning rate and computation resource consumption. We analyze the linear convergence behavior of consensus ADMM so as to characterize the interplay between the communication topology and the penalty parameters used in ADMM. We observe that given optimal parameters, the complete bipartite and the master-slave graphs exhibit the fastest convergence, followed by bi-regular graphs.

HIV drug resistance (HIVDR) has emerged as a major clinical and public health challenge in many resource poor countries especially in Africa. HIVDR testing has become increasingly important and is of significant value in the management of HIV. The use of low cost technologies and procedures in testing HIVDR is being recommended. HIVDR computer interpretation algorithms make use of artificial intelligence and other computer technologies to predict HIVDR, and are recommended for use in resource poor countries. However, there is little known about the knowledge, attitude and perception of HIVDR computer algorithms by doctors in developing countries who are supposed to use computer algorithms. This study aimed to determine the knowledge, attitude and perception regarding computer interpretation algorithms of the 4th and 5th year medical students at Nelson R. Mandela School of Medicine, University of KwaZulu Natal in South Africa. Primary data collection was done using a questionnaire administered to a convenience sample of 216 4th and 5th year medical students. The study revealed that 90% of the respondents were aware of HIV drug resistance testing in South Africa but only 4% had knowledge of the computer interpretation algorithms. The study revealed that although the UKZN medical students are not aware of computer interpretation algorithms, majority are willing to use them in the future. / Thesis (M.Med.Sc.)-University of KwaZulu-Natal, Durban, 2013.

M.Sc. University of KwaZulu-Natal, Durban 2013.

The objective of the proposed research is to develop structural changes to the design and application of electromagnetic (EM) sensing models to more efficiently and accurately invert EM measurements to extract parameters for applications such as landmine detection. Two different acquisition modalities are addressed in this research: ground-penetrating radar (GPR) and electromagnetic induction (EMI) sensors. The models needed for practical three-dimensional (3D) spatial imaging typically become impractically large, with up to seven dimensions of parameters that need to be extracted. These parameters include, but are not limited to target type, 3D location, and 3D orientation. The new special structures for these models exploit properties such as shift invariance and tensor representation, which can be combined with strategic inversion techniques, including the Fast Fourier Transform and semidefinite programming. The structures dramatically reduce the amount of computation and can eliminate the need to store up to five dimensions of parameters while still accurately estimating them.

The report presents an implemention of a classification algorithm for the Institutional Analysis Project. The algorithm used in this project is the decision tree classification algorithm which uses a gain ratio attribute selectionmethod. The algorithm discovers the hidden rules from the student records, which are used to predict whether or not other students are at risk of dropping out. It is shown that special rules exist in different data sets, each with their natural hidden knowledge. In other words, the rules that are obtained depend on the data that is used for classification. In our preliminary experiments, we show that between 55-78 percent of data with unknown class lables can be correctly classified, using the rules obtained from data whose class labels are known. We feel this is acceptable, given the large number of records, attributes, and attribute values that are used in the experiments. The project results are useful for large data set analysis. / viii, 38 leaves ; 29 cm. --

Analyzing massive-data sets and streams is computationally very challenging. Data sets in systems biology, network analysis and security use network abstraction to construct large-scale graphs. Graph algorithms such as traversal and search are memory-intensive and typically require very little computation, with access patterns that are irregular and fine-grained. The increasing streaming data rates in various domains such as security, mining, and finance leaves algorithm designers with only a handful of clock cycles (with current general purpose computing technology) to process every incoming byte of data in-core at real-time. This along with increasing complexity of mining patterns and other analytics puts further pressure on already high computational requirement. Processing streaming data in finance comes with an additional constraint to process at low latency, that restricts the algorithm to use common techniques such as batching to obtain high throughput. The primary contributions of this dissertation are the design of novel parallel data analysis algorithms for graph traversal on large-scale graphs, pattern recognition and keyword scanning on massive streaming data, financial market data feed processing and analytics, and data transformation, that capture the machine-independent aspects, to guarantee portability with performance to future processors, with high performance implementations on multicore processors that embed processorspecific optimizations. Our breadth first search graph traversal algorithm demonstrates a capability to process massive graphs with billions of vertices and edges on commodity multicore processors at rates that are competitive with supercomputing results in the recent literature. We also present high performance scalable keyword scanning on streaming data using novel automata compression algorithm, a model of computation based on small software content addressable memories (CAMs) and a unique data layout that forces data re-use and minimizes memory traffic. Using a high-level algorithmic approach to process financial feeds we present a solution that decodes and normalizes option market data at rates an order of magnitude more than the current needs of the market, yet portable and flexible to other feeds in this domain. In this dissertation we discuss in detail algorithm design challenges to process massive-data and present solutions and techniques that we believe can be used and extended to solve future research problems in this domain.

The electrocardiograph (ECG) is a common clinical and biomedical research tool used for both diagnostic and prognostic purposes. In recent years computer aided analysis of the ECG has enabled cardiographic patterns to be found which were hitherto not apparent. Many of these analyses rely upon the segmentation of the ECG into separate time delimited waveforms. The instants delimiting these segments are called the