Theory and Algorithms Commons^™

Interacting With Web Hierarchies, Saverio Perugini, Naren Ramakrishnan

Computer Science Faculty Publications

Web site interfaces are a particularly good fit for hierarchies in the broadest sense of that idea, i.e. a classification with multiple attributes, not necessarily a tree structure. Several adaptive interface designs are emerging that support flexible navigation orders, exposing and exploring dependencies, and procedural information-seeking tasks. This paper provides a context and vocabulary for thinking about hierarchical Web sites and their design. The paper identifies three features that interface to information hierarchies. These are flexible navigation orders, the ability to expose and explore dependencies, and support for procedural tasks. A few examples of these features are also provided

Adaptive Interpolation Algorithms For Temporal-Oriented Datasets, Jun Gao

School of Computing: Dissertations, Theses, and Student Research

Spatiotemporal datasets can be classified into two categories: temporal-oriented and spatial-oriented datasets depending on whether missing spatiotemporal values are closer to the values of its temporal or spatial neighbors. We present an adaptive spatiotemporal interpolation model that can estimate the missing values in both categories of spatiotemporal datasets. The key parameters of the adaptive spatiotemporal interpolation model can be adjusted based on experience.

Strategies For Encoding Xml Documents In Relational Databases: Comparisons And Contrasts., Jonathan Lee Leonard

Electronic Theses and Dissertations

The rise of XML as a de facto standard for document and data exchange has created a need to store and query XML documents in relational databases, today's de facto standard for data storage. Two common strategies for storing XML documents in relational databases, a process known as document shredding, are Interval encoding and ORDPATH Encoding. Interval encoding, which uses a fixed mapping for shredding XML documents, tends to favor selection queries, at a potential cost of O(N) for supporting insertion queries. ORDPATH Encoding, which uses a looser mapping for shredding XML, supports fixed-cost insertions, at a potential cost of …

Gestalt-Based Feature Similarity Measure In Trademark Database, Hui Jiang, Chong-Wah Ngo, Hung-Khoon Tan

Research Collection School Of Computing and Information Systems

Motivated by the studies in Gestalt principle, this paper describes a novel approach on the adaptive selection of visual features for trademark retrieval. We consider five kinds of visual saliencies: symmetry, continuity, proximity, parallelism and closure property. The first saliency is based on Zernike moments, while the others are modeled by geometric elements extracted illusively as a whole from a trademark. Given a query trademark, we adaptively determine the features appropriate for retrieval by investigating its visual saliencies. We show that in most cases, either geometric or symmetric features can give us good enough accuracy. To measure the similarity of …

Mining Rdf Metadata For Generalized Association Rules: Knowledge Discovery In The Semantic Web Era, Tao Jiang, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

In this paper, we present a novel frequent generalized pattern mining algorithm, called GP-Close, for mining generalized associations from RDF metadata. To solve the over-generalization problem encountered by existing methods, GP-Close employs the notion of emphgeneralization closure for systematic over-generalization reduction.

Mobius: An Omnidirectional Robotic Platform And Software Architecture For Network Teleoperation, Samuel Aaron Miller

Electrical & Computer Engineering Theses & Dissertations

The following thesis presents the results of a project to develop and test an omnidirectional robotic system (hardware and software) at NASA Langley Research Center's Robotics and Intelligent Machines Lab. The impetus for the project was the unique capabilities of omnidirectional systems. Some of the many potential benefits these systems have include improved material-handling capabilities in constrained environments (such as might be found in extraterrestrial manned habitats), efficient camera-based vehicle teleoperation, and simplified route planning for autonomous robot operations.

The project's focus was to design, build, and test a system that used Mecanum wheels to achieve omnidirectional motion. In addition …

A Non-Linear Technique For The Enhancement Of Extremely Non-Uniform Lighting Images, Ender Oguslu

Electrical & Computer Engineering Theses & Dissertations

At night scenes, either the low intensity areas that are under poor light or the high intensity areas that are overexposed cannot be clearly seen. Various image processing techniques have been developed to recover the meaningful information under extremely low lighting conditions. Among these, the algorithms based on integrated neighborhood dependency of pixel characteristics and based on the illuminance reflectance model perform well for improving the visual quality of digital images captured under nonuniform and extremely low lighting conditions. Although these techniques perform well in low lighting conditions, they cannot perform well in overexposed regions under dark environments such as …

The Reliability Of The Computer Communication Networks Including Mobile Nodes, Sahin Yasar

Electrical & Computer Engineering Theses & Dissertations

The wireless computer networks have an uncertainty in their structures aside from their big advantages for the users. The environmental conditions, changing locations of the mobile hosts and the changing components in the system can easily affect their reliability. In order to know a system capability performing its functions, keep the reliability at a certain level and/or detect the deficiency of the system, it is necessary to analyze the reliability of a computer communication network including the wired and wireless parts. But the above reasons also make the analysis and a unique solution difficult so a set of algorithms is …

Intelligent System Applications Based On Genetic Algorithms, Yasin Volkan Pehlivanoglu

Mechanical & Aerospace Engineering Theses & Dissertations

As a stochastic search method, evolutionary algorithm (EA) is an emergent optimization algorithm mimicking the natural evolution, where a "biological population" evolves over generations to adapt to an environment by selection, recombination, and mutation. When EA is applied to optimization problems, fitness, individual, and genes usually correspond to an objective function value, a design candidate, and design variables, respectively.

One of the key features of EA is that they search from multiple points in design space, instead of moving from a single point as in gradient-based methods. Furthermore, EA works on function evaluations alone and does not require derivatives or …

Reversing Ticket Based Probing (Rtbp) Routing For Manet, Turgut Yucel

Electrical & Computer Engineering Theses & Dissertations

The delay-constrained maximum-bandwidth routing problem in MANET (Mobile Ad hoc Networks) is to find the maximum bandwidth path which satisfies a given delay constraint. The research challenge for this problem is that the networking information used for routing may be imprecise. The Ticket-Based Probing (TBP) routing algorithm provides a heuristic approach by using two types of ticket. In this thesis a Reversing Ticket-based Probing (RTBP) routing algorithm is proposed. The RTBP has two novel features compared to the original ticket based probing algorithms. The first feature is using just one type ticket, instead of two types of ticket. RTBP generates …

A Unified Log-Based Relevance Feedback Scheme For Image Retrieval, Steven Hoi, Michael R. Lyu, Rong Jin

Research Collection School Of Computing and Information Systems

Relevance feedback has emerged as a powerful tool to boost the retrieval performance in content-based image retrieval (CBIR). In the past, most research efforts in this field have focused on designing effective algorithms for traditional relevance feedback. Given that a CBIR system can collect and store users' relevance feedback information in a history log, an image retrieval system should be able to take advantage of the log data of users' feedback to enhance its retrieval performance. In this paper, we propose a unified framework for log-based relevance feedback that integrates the log of feedback data into the traditional relevance feedback …

A Multilane Pipelined Architecture For Real Time Enhancement Of Color Video Streams, Adam Redd Livingston

Electrical & Computer Engineering Theses & Dissertations

Video stream enhancement is a key fixture in a wide variety of applications from video surveillance, automatic navigation, medical imagery, to facial/object recognition systems. When a video stream contains non-uniform lighting it can be difficult to obtain what is in the darker regions without over enhancing brighter regions. The Adaptive and Integrated Neighborhood Dependant Approach for Nonlinear Enhancement (AINDANE) algorithm combines a tunable nonlinear transfer function, convolution by a multi-scale Gaussian kernel, and tunable contrast enhancement to address this problem for a single image. Luminance values are tuned based on the global cumulative distribution function (CDF) of an image. Contrast …

Type Ii Quantum Computing Algorithm For Computational Fluid Dynamics, James A. Scoville

Theses and Dissertations

An algorithm is presented to simulate fluid dynamics on a three qubit type II quantum computer: a lattice of small quantum computers that communicate classical information. The algorithm presented is called a three qubit factorized quantum lattice gas algorithm. It is modeled after classical lattice gas algorithms which move virtual particles along an imaginary lattice and change the particles’ momentums using collision rules when they meet at a lattice node. Instead of moving particles, the quantum algorithm presented here moves probabilities, which interact via a unitary collision operator. Probabilities are determined using ensemble measurement and are moved with classical communications …

An Estimation Theory Approach To Detection And Ranging Of Obscured Targets In 3-D Ladar Data, Charles R. Burris

Theses and Dissertations

The purpose of this research is to develop an algorithm to detect obscured images in 3-D LADAR data. The real data used for this research was gathered using a FLASH LADAR system under development at AFRL/SNJM. The system transmits light with a wavelength of 1.55 micrometers and produces 20 128 X 128 temporally resolved images from the return pulse separated by less than 2 nanoseconds in time. New algorithms for estimating the range to a target in 3-D FLASH LADAR data were developed. Results from processing real data are presented and compared to the traditional correlation receiver for extracting ranges …

Multiframe Shift Estimation, Stephen A. Bruckart

Theses and Dissertations

The purpose of this research was to develop a fundamental framework for a new approach to multiframe translational shift estimation in image processing. This thesis sought to create a new multiframe shift estimator, to theoretically prove and experimentally test key properties of it, and to quantify its performance according to several metrics. The new estimator was modeled successfully and was proven to be an unbiased estimator under certain common image noise conditions. Furthermore its performance was shown to be superior to the cross correlation shift estimator, a robust estimator widely used in similar image processing cases, according to several criteria. …

Verification Of A Decision Level Fusion Algorithm Using A Proven Atr System And Measured Sar Data, James Douglas Thompson

Theses and Dissertations

Decision level fusion (DLF) algorithms combine outputs of multiple single sensors to make one confident declaration of a target. This research compares performance results of a DLF algorithm using measured data and a proven ATR system with results from simulated data and a modeled ATR system. This comparison indicates that DLF offers significant performance improvements over single sensor looks. However, results based on simulated data and a modeled ATR are slightly optimistic and overestimate results from measured data and a proven ATR system by nearly 10% over all targets tested.

A Hybrid Scatter Search/Electromagnetism Meta-Heuristic For Project Scheduling, Dieter Debels, Bert De Reyck, Roel Leus, Mario Vanhoucke

Research Collection Lee Kong Chian School Of Business

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational …

The Pseudosquares Prime Sieve, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

We present the pseudosquares prime sieve, which finds all primes up to n.

Realtime Query Expansion And Procedural Interfaces For Information Hierarchies, Saverio Perugini

Computer Science Faculty Publications

We demonstrate the use of two user interfaces for interacting with web hierarchies. One uses the dependencies underlying a hierarchy to perform real-time query expansion and, in this way, acts as an in situ feedback mechanism. The other enables the user to cascade the output from one interaction to the input of another, and so on, and, in this way, supports procedural information-seeking tasks without disrupting the flow of interaction.

Information Assurance Through Binary Vulnerability Auditing, William B. Kimball, Saverio Perugini

Computer Science Faculty Publications

The goal of this research is to develop improved methods of discovering vulnerabilities in software. A large volume of software, from the most frequently used programs on a desktop computer, such as web browsers, e-mail programs, and word processing applications, to mission-critical services for the space shuttle, is unintentionally vulnerable to attacks and thus insecure. By seeking to improve the identification of vulnerabilities in software, the security community can save the time and money necessary to restore compromised computer systems. In addition, this research is imperative to activities of national security such as counterterrorism. The current approach involves a systematic …

Classical And Quantum Algorithms For Finding Cycles, Jill Cirasella

Publications and Research

Quantum computing—so weird, so wonderful—inspires much speculation about the line between the possible and the impossible. (Of course, there is still unclarity about how “impossible” intractable problems are and about how “possible” quantum computers are.) This thesis takes a slightly different tack: instead of focusing on how to make the impossible possible, it focuses on how to make the possible easier.

More specifically, this paper discusses quantum algorithms for finding cycles in graphs, a problem for which polynomial-time classical algorithms already exist. It explains and compares the classical and quantum algorithms, and it introduces a few new algorithms and observations. …

Handling The Subclassing Anomaly With Object Teams, Jeff Furlong, Atanas Radenski

Mathematics, Physics, and Computer Science Faculty Articles and Research

Existing Java software or libraries can evolve via subclassing. Unfortunately, subclassing may not properly support code adaptation when there are dependencies between classes. More precisely, subclassing in collections of related classes may require reimplementation of otherwise valid classes. This problem is defined as the subclassing anomaly, which is an issue when software evolution or code reuse is a goal of the programmer who is using existing classes. Object Teams offers an implicit fix to this problem and is largely compatible with the existing JVM’s. In this paper, we evaluate how well Object Teams succeeds in providing a solution for a …

Efficient Scheduling For Sdmg Cioq Switches, Mei Yang, S. Q. Zheng

Electrical & Computer Engineering Faculty Research

Combined input and output queuing (CIOQ) switches are being considered as high-performance switch architectures due to their ability to achieve 100% throughput and perfectly emulate output queuing (OQ) switch performance with a small speedup factor S. To realize a speedup factor S, a conventional CIOQ switch requires the switching fabric and memories to operate S times faster than the line rate. In this paper, we propose to use a CIOQ switch with space-division multiplexing expansion and grouped input/output ports (SDMG CIOQ switch for short) to realize speedup while only requiring the switching fabric and memories to operate at the line …

A Tabu Search Algorithm To Minimize The Makespan For The Unrelated Parallel Machines Scheduling Problem With Setup Times, Magdy Helal, Ghaith Rabadi, Ameer Al-Salem

Engineering Management & Systems Engineering Faculty Publications

In this paper we propose a tabu search implementation to solve the unrelated parallel machines scheduling problem with sequence- and machine- dependent setup times to minimize the schedules makespan. The problem is NP-hard and finding an optimal solution efficiently is unlikely. Therefore, heuristic techniques are more appropriate to find near-optimal solutions. The proposed tabu search algorithm uses two phases of perturbation schemes: the intra-machine perturbation, which optimizes the sequence of jobs on the machines, and the inter-machine perturbation, which balances the assignment of the jobs to the machines. We compare the proposed algorithm to an existing one that addressed the …

Group Key Management In Wireless Ad-Hoc And Sensor Networks, Mohammed A. Moharrum

Computer Science Theses & Dissertations

A growing number of secure group applications in both civilian and military domains is being deployed in WAHNs. A Wireless Ad-hoc Network (WARN) is a collection of autonomous nodes or terminals that communicate with each other by forming a multi-hop radio network and maintaining connectivity in a decentralized manner. A Mobile Ad-hoc Network (MANET) is a special type of WARN with mobile users. MANET nodes have limited communication, computational capabilities, and power. Wireless Sensor Networks (WSNs) are sensor networks with massive numbers of small, inexpensive devices pervasive throughout electrical and mechanical systems and ubiquitous throughout the environment that monitor and …

Unsymmetrical And Symmetrical Sparse Iterative Algorithm With Multiple Right-Hand-Sides Strategies, D. T. Nguyen, A. P. Honrao, G. Hou, O. Akan, O. Baysal

Civil & Environmental Engineering Faculty Publications

Unified unsymmetrical and symmetrical iterative solvers for handling multiple right-hand-side vectors are examined in this work. Efficient computer implementation strategies (to reduce computational time and in-core memory requirements) are proposed. In-core, out-of-core, linear, multiple right hand side (RHS) vectors, non-linear, symmetrical, and unsymmetrical capabilities of the developed software are demonstrated by solving variety of problems selected form different engineering disciplines. Results indicate that the developed algorithm and software is reliable and efficient.

Hybrid Committee Classifier For A Computerized Colonic Polyp Detection System, Jiang Li, Jianhua Yao, Nicholas Petrick, Ronald M. Summers, Amy K. Hara, Joseph M. Reinhardt (Ed.), Josien P.W. Pluim (Ed.)

Electrical & Computer Engineering Faculty Publications

We present a hybrid committee classifier for computer-aided detection (CAD) of colonic polyps in CT colonography (CTC). The classifier involved an ensemble of support vector machines (SVM) and neural networks (NN) for classification, a progressive search algorithm for selecting a set of features used by the SVMs and a floating search algorithm for selecting features used by the NNs. A total of 102 quantitative features were calculated for each polyp candidate found by a prototype CAD system. 3 features were selected for each of 7 SVM classifiers which were then combined to form a committee of SVMs classifier. Similarly, features …

Fast Bounds On The Distribution Of Smooth Numbers, Scott T. Parsell, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

In this paper we present improvements to Bernstein’s algorithm, which finds rigorous upper and lower bounds for (x, y).

Robust And Efficient Localization Techniques For Cellular And Wireless Sensor Networks, Haseebulla M. Khan

Computer Science Theses & Dissertations

Localization in wireless networks refers to a collection of tasks that, collectively, determines the location of a mobile user, striving to hide the effects of mobility from the user and/or application. Localization has become an important issue and has drawn considerable attention, as many applications including E-911, cargo tracking, locating patients, location-sensitive billing, etc., require knowledge of the location of user/objects. It was realized, quite a while back, that extending emergency 911-like services (E-911) to continually growing mobile population is one of the extremely important localization applications. The bulk of the proposed solutions to emergency location management in wireless environments …

On Static And Dynamic Partitioning Behavior Of Large-Scale Networks, Derek Leonard, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov

Computer Science Faculty Publications

In this paper, we analyze the problem of network disconnection in the context of large-scale P2P networks and understand how both static and dynamic patterns of node failure affect the resilience of such graphs. We start by applying classical results from random graph theory to show that a large variety of deterministic and random P2P graphs almost surely (i.e., with probability 1-o(1)) remain connected under random failure if and only if they have no isolated nodes. This simple, yet powerful, result subsequently allows us to derive in closed-form the probability that a P2P network develops isolated nodes, and therefore partitions, …