Theory and Algorithms Commons^™

Exploiting Information Theory For Adaptive Mobility And Resource Management In Future Cellular Networks, Abhishek Roy, Sajal K. Das, Archan Misra

Research Collection School Of Computing and Information Systems

We utilize tools from information theory to develop adaptive algorithms for two key problems in cellular networks: location tracking and resource management. The use of information theory is motivated by the fundamental observation that overheads in many aspects of mobile computing can be traced to the randomness or uncertainty in an individual user's movement behavior. We present a model-independent information-theoretic approach for estimating and managing this uncertainty, and relate it to the entropy or information content of the user's movement process. Information-theoretic mobility management algorithms are very simple, yet reduce overhead by ∼80 percent in simulated scenarios by optimally adapting …

Global Incremental Garbage Collection In Distributed Systems, Soha Safwat Labib

Archived Theses and Dissertations

No abstract provided.

Toward A Sound Integration Of Isabelle With A Combined Decision Procedure, Tom Harke

Computer Science Faculty Publications and Presentations

I present work on a project to integrate Isabelle, an extremely versatile interactive proof assistant, with a combined decision procedure, the Cooperating Validity Checker (CVC). Isabelle is sound and flexible, however it is often tedious to use. CVC is fully automatic, but only handles decision problems expressible over a relatively weak set of theories including linear arithmetic, uninterpreted functions, data types, and firstorder quantifier-free logic. My goal is to increase the amount of automation in Isabelle, by making it use CVC as an oracle for such problems, but without compromising Isabelle’s soundness.

In this paper I report on the progress …

A Subgroup Algorithm To Identify Cross-Rotation Peaks Consistent With Non-Crystallographic Symmetry, Ryan H. Lilien, Chris Bailey-Kellogg, Amy C. Anderson, Bruce R. Donald

Dartmouth Scholarship

Molecular replacement (MR) often plays a prominent role in determining initial phase angles for structure determination by X-ray crystallography. In this paper, an efficient quaternion-based algorithm is presented for analyzing peaks from a cross-rotation function in order to identify model orientations consistent with proper non-crystallographic symmetry (NCS) and to generate proper NCS-consistent orientations missing from the list of cross-rotation peaks. The algorithm, CRANS, analyzes the rotation differences between each pair of cross-rotation peaks to identify finite subgroups. Sets of rotation differences satisfying the subgroup axioms correspond to orientations compatible with the correct proper NCS. The CRANS algorithm was first …

Reconstructability Analysis With Fourier Transforms, Martin Zwick

Complex Systems Faculty Publications and Presentations

Fourier methods used in two‐ and three‐dimensional image reconstruction can be used also in reconstructability analysis (RA). These methods maximize a variance‐type measure instead of information‐theoretic uncertainty, but the two measures are roughly collinear and the Fourier approach yields results close to that of standard RA. The Fourier method, however, does not require iterative calculations for models with loops. Moreover, the error in Fourier RA models can be assessed without actually generating the full probability distributions of the models; calculations scale with the size of the data rather than the state space. State‐based modeling using the Fourier approach is also …

A Fast And Simple Algorithm For Computing M-Shortest Paths In State Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

Staging Transformations For Multimodal Web Interaction Management, Michael Narayan, Christopher Williams, Saverio Perugini, Naren Ramakrishnan

Computer Science Faculty Publications

Multimodal interfaces are becoming increasingly ubiquitous with the advent of mobile devices, accessibility considerations, and novel software technologies that combine diverse interaction media. In addition to improving access and delivery capabilities, such interfaces enable flexible and personalized dialogs with websites, much like a conversation between humans. In this paper, we present a software framework for multimodal web interaction management that supports mixed-initiative dialogs between users and websites. A mixed-initiative dialog is one where the user and the website take turns changing the flow of interaction. The framework supports the functional specification and realization of such dialogs using staging transformations – …

Program Transformations For Information Personalization, Saverio Perugini

Computer Science Faculty Publications

Personalization constitutes the mechanisms and technologies necessary to customize information access to the end-user. It can be defined as the automatic adjustment of information content, structure, and presentation. The central thesis of this dissertation is that modeling interaction explicitly in a representation, and studying how partial information can be harnessed in it by program transformations to direct the flow of the interaction, can provide insight into, reveal opportunities for, and define a model for personalized interaction. To evaluate this thesis, a formal modeling methodology is developed for personalizing interactions with information systems, especially hierarchical hypermedia, based on program transformations. The …

Automatically Generating Interfaces For Personalized Interaction With Digital Libraries, Saverio Perugini, Naren Ramakrishnan, Edward A. Fox

Computer Science Faculty Publications

We present an approach to automatically generate interfaces supporting personalized interaction with digital libraries; these interfaces augment the user-DL dialog by empowering the user to (optionally) supply out-of-turn information during an interaction, flatten or restructure the dialog, and inquire about dialog options. Interfaces generated using this approach for CITIDEL are described.

An Overview Of Reconstructability Analysis, Martin Zwick

Complex Systems Faculty Publications and Presentations

This paper is an overview of reconstructability analysis (RA), a discrete multivariate modeling methodology developed in the systems literature; an earlier version of this tutorial is Zwick (2001). RA was derived from Ashby (1964), and was developed by Broekstra, Cavallo, Cellier Conant, Jones, Klir, Krippendorff, and others (Klir, 1986, 1996). RA resembles and partially overlaps log‐line (LL) statistical methods used in the social sciences (Bishop et al., 1978; Knoke and Burke, 1980). RA also resembles and overlaps methods used in logic design and machine learning (LDL) in electrical and computer engineering (e.g. Perkowski et al., 1997). Applications of RA, like …

Qos Routing Optimization Strategy Using Genetic Algorithm In Optical Fiber Communication Networks, Zhaoxia Wang, Zengqiang Chen, Zhuzhi Yuan

Research Collection School Of Computing and Information Systems

This paper describes the routing problems in optical fiber networks, defines five constraints, induces and simplifies the evaluation function and fitness function, and proposes a routing approach based on the genetic algorithm, which includes an operator [OMO] to solve the QoS routing problem in optical fiber communication networks. The simulation results show that the proposed routing method by using this optimal maintain operator genetic algorithm (OMOGA) is superior to the common genetic algorithms (CGA). It not only is robust and efficient but also converges quickly and can be carried out simply, that makes it better than other complicated GA.

Directed Extended Dependency Analysis For Data Mining, Thaddeus T. Shannon, Martin Zwick

Complex Systems Faculty Publications and Presentations

Extended dependency analysis (EDA) is a heuristic search technique for finding significant relationships between nominal variables in large data sets. The directed version of EDA searches for maximally predictive sets of independent variables with respect to a target dependent variable. The original implementation of EDA was an extension of reconstructability analysis. Our new implementation adds a variety of statistical significance tests at each decision point that allow the user to tailor the algorithm to a particular objective. It also utilizes data structures appropriate for the sparse data sets customary in contemporary data mining problems. Two examples that illustrate different approaches …

Reconstructability Analysis Detection Of Optimal Gene Order In Genetic Algorithms, Martin Zwick, Stephen Shervais

Complex Systems Faculty Publications and Presentations

The building block hypothesis implies that genetic algorithm efficiency will be improved if sets of genes that improve fitness through epistatic interaction are near to one another on the chromosome. We demonstrate this effect with a simple problem, and show that information-theoretic reconstructability analysis can be used to decide on optimal gene ordering.

Optimal Design Of Engineering Systems Using Mpi-Enabled Genetic Algorithm, S. D. Rajan, D. T. Nguyen, M. D. Deshpande, L. Harrell

Civil & Environmental Engineering Faculty Publications

The focus of this paper is on the development and implementation of a genetic algorithm (GA)-based software system using message passing interface (MPI) protocol and library. A customized form of simple GA used in previous research [1-4] is parallelized. This MPI-enabled version is used to find the solution to finite element based design optimization problems. Results show that an almost linear speedup is obtained on homogenous hardware cluster and, with proper reworking of the software, on heterogeneous hardware cluster.

A Similarity Based Concordance Approach To Word Sense Disambiguation, Ramakrishnan B. Guru

Masters Theses

This study attempts to solve the problem of Word Sense Disambiguation using a combination of statistical, probabilistic and word matching algorithms. These algorithms consider that words and sentences have some hidden similarities and that the polysemous words in any context should be assigned to a sense after each execution of the algorithm. The algorithm was tested with sufficient sample data and the efficiency of the disambiguation performance has proven to increase significantly after the inclusion of the concordance methodology.

A Robust Dissolve Detector By Support Vector Machine, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

In this paper, we propose a novel approach for the robust detection and classification of dissolve sequences in videos. Our approach is based on the multi-resolution representation of temporal slices extracted from 3D image volume. At the low-resolution (LR) scale, the problem of dissolve detection is reduced as cut transition detection. At the highresolution (HR) space, Gabor wavelet features are computed for regions that surround the cuts located at LR scale. The computed features are then input to support vector machines for pattern classification. Encouraging results have been obtained through experiments.

Synchronization Of Lecture Videos And Electronic Slides By Video Text Analysis, Feng Wang, Chong-Wah Ngo, Ting-Chuen Pong

Research Collection School Of Computing and Information Systems

An essential goal of structuring lecture videos captured in live presentation is to provide a synchronized view of video clips and electronic slides. This paper presents an automatic approach to match video clips and slides based on the analysis of text embedded in lecture videos. We describe a method to reconstruct high-resolution video texts from multiple keyframes for robust OCRrecognition. A two-stage matching algorithm based on the title and content similarity measures between video clips and slides is also proposed.

Unidirectional Cordic For Efficient Computation Of Trigonometric And Hyperbolic Functions, Satish Ravichandran

Electrical & Computer Engineering Theses & Dissertations

CORDIC (Coordinate Rotation Digital Computer) is an iterative algorithm to compute values of trigonometric, logarithmic and transcendental functions by performing vector rotations, which can be implemented with only shift and add operations in a digital system. CORDIC algorithms are extensively used in the areas of digital signal processing, digital image processing and artificial neural networks. A new technique, named unidirectional CORDIC, for efficient computation of trigonometric and hyperbolic functions is presented in this thesis. In the conventional CORDIC algorithm, the vector rotations are performed in both clockwise and counterclockwise directions, but in the unidirectional CORDIC the vectors are rotated only …

Adaptive Parallel Framework Algorithm (Apfa) For Environmental Engineering Applications, Lianghua Zhou

Civil & Environmental Engineering Theses & Dissertations

This research proposes a new framework methodology for integrating environmental computer applications in flexible, open and adaptively and reusable manners so that the resulting application framework could be used to effectively, flexibly and rapidly handle various environmental problems and issues. Research also demonstrates the framework algorithm with a case study. The proposed algorithm is referred as Adaptive Parallel Framework Algorithm (APF A). Core concept of the APF A is based on a parallelism, "many-to-one" mode to communicate among environmental applications, and takes advantages of a loosely coupled technology that helps archiving the required flexibility, extensibility and usability of integrated systems. …

Fast And Space-Efficient Location Of Heavy Or Dense Segments In Run-Length Encoded Sequences, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This paper considers several variations of an optimization problem with potential applications in such areas as biomolecular sequence analysis and image processing. Given a sequence of items, each with a weight and a length, the goal is to find a subsequence of consecutive items of optimal value, where value is either total weight or total weight divided by total length. There may also be a specified lower and/or upper bound on the acceptable length of subsequences. This paper shows that all the variations of the problem are solvable in linear time and space even with non-uniform item lengths and divisible …

A New Message-Based Protocol For Building A Platform And Language Independent Distributed Object Model, Hazem S. El Ashmawi

Archived Theses and Dissertations

Standardization of messaging topologies for communication in recent distributed object computing architectures is becoming more and more inevitable. The emergence of a structured and flexible document model as XML has made an entry point towards this goal. In this thesis, we are utilizing the flexibility of XML and the simplicity of low -level socket communication to build a generalized messaging model that provides a basis for standardization and supports interoperability among existing distributed object computing architectures. The proposed system is composed of the basic components of a distributed architecture constituting a number of broker components acting as naming services and …

The Online Median Problem, Ramgopal R. Mettu, C. Greg Plaxton

Dartmouth Scholarship

We introduce a natural variant of the (metric uncapacitated) k-median problem that we call the online median problem. Whereas the k-median problem involves optimizing the simultaneous placement of k facilities, the online median problem imposes the following additional constraints: the facilities are placed one at a time, a facility cannot be moved once it is placed, and the total number of facilities to be placed, k, is not known in advance. The objective of an online median algorithm is to minimize the competitive ratio, that is, the worst-case ratio of the cost of an online placement to …

Automatic Speaker Identification Using Reusable And Retrainable Binary-Pair Partitioned Neural Networks, Ashutosh Mishra

Electrical & Computer Engineering Theses & Dissertations

This thesis presents an extension of the work previously done on speaker identification using Binary Pair Partitioned (BPP) neural networks. In the previous work, a separate network was used for each pair of speakers in the speaker population. Although the basic BPP approach did perform well and had a simple underlying algorithm, it had the obvious disadvantage of requiring an extremely large number of networks for speaker identification with large speaker populations. It also requires training of networks proportional to the square of the number of speakers under consideration, leading to a very large number of networks to be trained …

Explicit Building-Block Multiobjective Genetic Algorithms: Theory, Analysis, And Developing, Jesse B. Zydallis

Theses and Dissertations

This dissertation research emphasizes explicit Building Block (BB) based MO EAs performance and detailed symbolic representation. An explicit BB-based MOEA for solving constrained and real-world MOPs is developed the Multiobjective Messy Genetic Algorithm II (MOMGA-II) which is designed to validate symbolic BB concepts. The MOMGA-II demonstrates that explicit BB-based MOEAs provide insight into solving difficult MOPs that is generally not realized through the use of implicit BB-based MOEA approaches. This insight is necessary to increase the effectiveness of all MOEA approaches. In order to increase MOEA computational efficiency parallelization of MOEAs is addressed. Communications between processors in a parallel MOEA …

A Parallel Algorithm To Solve The Mathematical Problem "Double Coset Enumeration Of S₂₄ Over M₂₄", Elena Yavorska Harris

Theses Digitization Project

This thesis presents and evaluates a new parallel algorithm that computes all single cosets in the double coset M₂₄ P M₂₄, where P is a permutation on n points of a certain cycle structure, and M₂₄ is the Mathieu group related to a Steiner system S(5, 8, 24) as its automorphism group. The purpose of this work is not to replace the existing algorithms, but rather to explore a possibility to extend calculations of single cosets beyond the limits encountered when using currently available methods.

The Window Least Mean Square Error Algorithm, Anna Semenovna Degtyarena

Theses Digitization Project

In order to improve the performance of LMS (least mean square) algorithm by decreasing the amount of calculations this research proposes to make an update on each step only for those elements from the input data set, that fall within a small window W near the separating hyperplane surface. This work aims to describe in detail the results that can be achieved by using the proposed LMS with window learning algorithm in information systems that employ the methodology of neural network for the purposes of classification.

The Staging Transformation Approach To Mixing Initiative, Robert Capra, Michael Narayan, Saverio Perugini, Naren Ramakrishnan, Manuel A. Pérez-Quiñones

Computer Science Faculty Publications

Mixed-initiative interaction is an important facet of many conversational interfaces, flexible planning architectures, intelligent tutoring systems, and interactive information retrieval systems. Software systems for mixed-initiative interaction must enable us to both operationalize the mixing of initiative (i.e., support the creation of practical dialogs) and to reason in real-time about how a flexible mode of interaction can be supported (e.g., from a meta-dialog standpoint). In this paper, we present the staging transformation approach to mixing initiative, where a dialog script captures the structure of the dialog and dialog control processes are realized through generous use of program transformation techniques (e.g., partial …

Personalizing Interactions With Information Systems, Saverio Perugini, Naren Ramakrishnan

Computer Science Faculty Publications

Personalization constitutes the mechanisms and technologies necessary to customize information access to the end-user. It can be defined as the automatic adjustment of information content, structure, and presentation tailored to the individual. In this chapter, we study personalization from the viewpoint of personalizing interaction. The survey covers mechanisms for information-finding on the web, advanced information retrieval systems, dialog-based applications, and mobile access paradigms. Specific emphasis is placed on studying how users interact with an information system and how the system can encourage and foster interaction. This helps bring out the role of the personalization system as a facilitator which reconciles …

Interpolation Techniques For Overset Grids, Paul S. Sherman, Nathan B. Edgar

Journal of the Arkansas Academy of Science

The use of finite difference schemes in computational aeroacoustics requires the use of structured grids incomputational space. Complex geometries in the physical space can be modeled using multiple overlapping grids that are transformed into computational space. In this work, finite difference schemes are used that necessitate the addition of psuedo- or ghost-points in the overlap region of the grids for closure of the difference stencil. The functional values at these ghost points must be approximated from the values at the original grid points. This paper investigates interpolation techniques for these overset grids. An n th order interpolation scheme using Lagrange …

Ordering Genetic Algorithm Genomes With Reconstructability Analysis, Stephen Shervais, Martin Zwick

Complex Systems Faculty Publications and Presentations

The building block hypothesis implies that genetic algorithm effectiveness is influenced by the relative location of epistatic genes on the chromosome. We find that this influence exists, but depends on the generation in which it is measured. Early in the search process it may be more effective to have epistatic genes widely separated. Late in the search process, effectiveness is improved when they are close together. The early search effect is weak but still statistically significant; the late search effect is much stronger and plainly visible. We demonstrate both effects with a set of simple problems, and show that infonnation-theoretic …