Computer Sciences Commons^™

Representation Invariant Genetic Operators, Jonathan E. Rowe, Michael D. Vose, Alden H. Wright

Computer Science Faculty Publications

A genetic algorithm is invariant with respect to a set of representations if it runs the same no matter which of the representations is used. We formalize this concept mathematically, showing that the representations generate a group that acts upon the search space. Invariant genetic operators are those that commute with this group action. We then consider the problem of characterizing crossover and mutation operators that have such invariance properties. In the case where the corresponding group action acts transitively on the search space, we provide a complete characterization, including high-level representation-independent algorithms implementing these operators.

Results From The Ice-Sheet Model Intercomparison Project-Heinrich Event Intercomparison (Ismip Heino), Reinhard Calov, Ralf Greve, Ayako Abe-Ouchi, Ed Bueler, Philippe Huybrechts, Jesse V. Johnson, Rank Pattyn, David Pollard, Catherine Ritz, Fuyuki Saito, Lev Tarasov

Computer Science Faculty Publications

Results from the Heinrich Event INtercOmparison (HEINO) topic of the Ice-Sheet Model Intercomparison Project (ISMIP) are presented. ISMIP HEINO was designed to explore internal largescale ice-sheet instabilities in different contemporary ice-sheet models. These instabilities are of interest because they are a possible cause of Heinrich events. A simplified geometry experiment reproduces the main characteristics of the Laurentide ice sheet, including the sedimented region over Hudson Bay and Hudson Strait. The model experiments include a standard run plus seven variations. Nine dynamic/thermodynamic ice-sheet models were investigated; one of these models contains a combination of the shallow-shelf (SSA) and shallow-ice approximation (SIA), …

A Quadratic Lower Bound For Rocchio’S Similarity-Based Relevance Feedback Algorithm With A Fixed Query Updating Factor, Zhixiang Chen, Bin Fu, John P. Abraham

Computer Science Faculty Publications

Rocchio’s similarity-based relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio’s algorithm often uses a fixed query updating factor. When this is the case, we strengthen the linear Ω(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61–86, 2002) and prove that Rocchio’s algorithm makes Ω(k(n−k)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1}n, …

Supporting Multiple Paths To Objects In Information Hierarchies: Faceted Classification, Faceted Search, And Symbolic Links, Saverio Perugini

Computer Science Faculty Publications

We present three fundamental, interrelated approaches to support multiple access paths to each terminal object in information hierarchies: faceted classification, faceted search, and web directories with embedded symbolic links. This survey aims to demonstrate how each approach supports users who seek information from multiple perspectives. We achieve this by exploring each approach, the relationships between these approaches, including tradeoffs, and how they can be used in concert, while focusing on a core set of hypermedia elements common to all. This approach provides a foundation from which to study, understand, and synthesize applications which employ these techniques. This survey does not …

A Metric For Routing In Delay-Sensitive Wireless Sensor Networks, Zhen Jiang, Jie Wu, Risa Ito

Computer Science Faculty Publications

No abstract provided.

Cr: Capability Information For Routing Of Wireless Ad Hoc Networks In The Real Environment, Zhen Jiang, Zhigang Li, Nong Xiao, Jie Wu

Computer Science Faculty Publications

No abstract provided.

Structure Prediction For The Helical Skeletons Detected From The Low Resolution Protein Density Map, Kamal Al Nasr, Weitao Sun, Jing He

Computer Science Faculty Publications

Background: The current advances in electron cryo-microscopy technique have made it possible to obtain protein density maps at about 6-10 Å resolution. Although it is hard to derive the protein chain directly from such a low resolution map, the location of the secondary structures such as helices and strands can be computationally detected. It has been demonstrated that such low-resolution map can be used during the protein structure prediction process to enhance the structure prediction.

Results: We have developed an approach to predict the 3-dimensional structure for the helical skeletons that can be detected from the low resolution protein density …

Improving Predicted Protein Loop Structure Ranking Using A Pareto-Optimality Consensus Method, Yaohang Li, Ionel Rata, See-Wing Chiu, Erik Jakobsson

Computer Science Faculty Publications

Background

Accurate protein loop structure models are important to understand functions of many proteins. Identifying the native or near-native models by distinguishing them from the misfolded ones is a critical step in protein loop structure prediction.

Results

We have developed a Pareto Optimal Consensus (POC) method, which is a consensus model ranking approach to integrate multiple knowledge- or physics-based scoring functions. The procedure of identifying the models of best quality in a model set includes: 1) identifying the models at the Pareto optimal front with respect to a set of scoring functions, and 2) ranking them based on the fuzzy …

Fully Generalized Two-Dimensional Constrained Delaunay Mesh Refinement, Panagiotis A. Foteinos, Andrey N. Chernikov, Nikos P. Chrisochoides

Computer Science Faculty Publications

Traditional refinement algorithms insert a Steiner point from a few possible choices at each step. Our algorithm, on the contrary, defines regions from where a Steiner point can be selected and thus inserts a Steiner point among an infinite number of choices. Our algorithm significantly extends existing generalized algorithms by increasing the number and the size of these regions. The lower bound for newly created angles can be arbitrarily close to $30^{\circ}$. Both termination and good grading are guaranteed. It is the first Delaunay refinement algorithm with a $30^{\circ}$ angle bound and with grading guarantees. Experimental evaluation of our algorithm …

Mining Data From Multiple Software Development Projects, Huanjing Wang, Taghi M. Khoshgoftaar, Kehan Gao, Naeem Seliya

Computer Science Faculty Publications

A large system often goes through multiple software project development cycles, in part due to changes in operation and development environments. For example, rapid turnover of the development team between releases can influence software quality, making it important to mine software project data over multiple system releases when building defect predictors. Data collection of software attributes are often conducted independent of the quality improvement goals, leading to the availability of a large number of attributes for analysis. Given the problems associated with variations in development process, data collection, and quality goals from one release to another emphasizes the importance of …

High-Dimensional Software Engineering Data And Feature Selection, Huanjing Wang, Taghi M. Khoshgoftaar, Kehan Gao

Computer Science Faculty Publications

Software metrics collected during project development play a critical role in software quality assurance. A software practitioner is very keen on learning which software metrics to focus on for software quality prediction. While a concise set of software metrics is often desired, a typical project collects a very large number of metrics. Minimal attention has been devoted to finding the minimum set of software metrics that have the same predictive capability as a larger set of metrics – we strive to answer that question in this paper. We present a comprehensive comparison between seven commonly-used filter-based feature ranking techniques (FRT) …

A Coherent Measurement Of Web-Search Relevance, William Mahoney, Peter Hospodka, William Sousan, Ryan Nickell, Qiuming Zhu

Computer Science Faculty Publications

We present a metric for quantitatively assessing the quality of Web searches. The relevance-of-searching-on-target index measures how relevant a search result is with respect to the searcher's interest and intention. The measurement is established on the basis of the cognitive characteristics of common user's online Web-browsing behavior and processes. We evaluated the accuracy of the index function with respect to a set of surveys conducted on several groups of our college students. While the index is primarily intended to be used to compare the Web-search results and tell which is more relevant, it can be extended to other applications. For …

Stochastic Stability In Internet Router Congestion Games, Christine Chung, Evangelia Pyrga

Computer Science Faculty Publications

No abstract provided.

On The Price Of Stability For Undirected Network Design, Giorgos Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga, Rob Van Stee

Computer Science Faculty Publications

No abstract provided.

Robust Lifetime Measurement In Large-Scale P2p Systems With Non-Stationary Arrivals, Xiaoming Wang, Zhongmei Yao, Yueping Zhang, Dmitri Loguinov

Computer Science Faculty Publications

Characterizing user churn has become an important topic in studying P2P networks, both in theoretical analysis and system design. Recent work has shown that direct sampling of user lifetimes may lead to certain bias (arising from missed peers and round-off inconsistencies) and proposed a technique that estimates lifetimes based on sampled residuals. In this paper, however, we show that under non-stationary arrivals, which are often present in real systems, residual-based sampling does not correctly reconstruct user lifetimes and suffers a varying degree of bias, which in some cases makes estimation completely impossible. We overcome this problem using two contributions: a …

An Empirical Investigation Of Filter Attribute Selection Techniques For Software Quality Classification, Kehan Gao, Taghi M. Khoshgoftaar, Huanjing Wang

Computer Science Faculty Publications

Attribute selection is an important activity in data preprocessing for software quality modeling and other data mining problems. The software quality models have been used to improve the fault detection process. Finding faulty components in a software system during early stages of software development process can lead to a more reliable final product and can reduce development and maintenance costs. It has been shown in some studies that prediction accuracy of the models improves when irrelevant and redundant features are removed from the original data set. In this study, we investigated four filter attribute selection techniques, Automatic Hybrid Search (AHS), …

Evolutionary Solutions And Internet Applications For Algorithmic Game Theory, Christine Chung

Computer Science Faculty Publications

The growing pervasiveness of the internet has created a new class of algorithmic problems: those in which the strategic interaction of autonomous, self-interested entities must be accounted for. So motivated, we seek to (1) use game theoretic models and techniques to study practical problems in load balancing, data streams and internet traffic congestion, and (2) demonstrate the usefulness of evolutionary game theory’s adaptive model as an analytical and evaluative tool.

First we consider the evolutionary game theory concept of stochastic stability, and propose the price of stochastic anarchy as an alternative to the price of anarchy for quantifying the cost …

Residual-Based Estimation Of Peer And Link Lifetimes In P2p Networks, Xiaoming Wang, Zhongmei Yao, Dmitri Loguinov

Computer Science Faculty Publications

Existing methods of measuring lifetimes in P2P systems usually rely on the so-called Create-BasedMethod (CBM), which divides a given observation window into two halves and samples users ldquocreatedrdquo in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we first derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent …

Adding Escience Assets To The Data Web, Herbert H. Van De Sompel, Carl Lagoze, Michael L. Nelson, Simeon Warner, Robert Sanderson, Pete Johnston

Computer Science Faculty Publications

Aggregations of Web resources are increasingly important in scholarship as it adopts new methods that are data-centric, collaborative, and networked-based. The same notion of aggregations of resources is common to the mashed-up, socially networked information environment of Web 2.0. We present a mechanism to identify and describe aggregations of Web resources that has resulted from the Open Archives Initiative - Object Reuse and Exchange (OAI-ORE) project. The OAI-ORE specifications are based on the principles of the Architecture of the World Wide Web, the Semantic Web, and the Linked Data effort. Therefore, their incorporation into the cyberinfrastructure that supports eScholarship will …

3d Medical Collaboration Technology To Enhance Emergency Healthcare, Greg Welch, Diane H. Sonnenwald, Henry Fuchs, Bruce Cairns, Ketan Mayer-Patel, Hanna M. Söderholm, Ruigang Yang, Andrei State, Herman Towles, Adrian Ilie, Manoj Ampalam, Srinivas Krishnan, Vincent Noel, Michael Noland, James E. Manning

Computer Science Faculty Publications

Two-dimensional (2D) videoconferencing has been explored widely in the past 15–20 years to support collaboration in healthcare. Two issues that arise in most evaluations of 2D videoconferencing in telemedicine are the difficulty obtaining optimal camera views and poor depth perception. To address these problems, we are exploring the use of a small array of cameras to reconstruct dynamic three-dimensional (3D) views of a remote environment and of events taking place within. The 3D views could be sent across wired or wireless networks to remote healthcare professionals equipped with fixed displays or with mobile devices such as personal digital assistants (PDAs). …

Extensive Phylogenetic Analysis Of A Soil Bacterial Community Illustrates Extreme Taxon Evenness And The Effects Of Amplicon Length, Degree Of Coverage, And Dna Fractionation On Classification And Ecological Parameters, Sergio E. Morales, Theodore F. Cosart, Jesse Johnson, William Holben

Computer Science Faculty Publications

To thoroughly investigate the bacterial community diversity present in a single composite sample from an agricultural soil and to examine potential biases resulting from data acquisition and analytical approaches, we examined the effects of percent G+C DNA fractionation, sequence length, and degree of coverage of bacterial diversity on several commonly used ecological parameters (species estimation, diversity indices, and evenness). We also examined variation in phylogenetic placement based on multiple commonly used approaches (ARB alignments and multiple RDP tools). The results demonstrate that this soil bacterial community is highly diverse, with 1,714 operational taxonomic units demonstrated and 3,555 estimated (based on …

Node Isolation Model And Age-Based Neighbor Selection In Unstructured P2p Networks, Zhongmei Yao, Derek Leonard, Dmitri Loguinov

Computer Science Faculty Publications

Previous analytical studies of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared with uniform selection of neighbors. In fact, the second strategy based on random walks on age-proportional graphs demonstrates that, for lifetimes with infinite variance, the system monotonically increases …

A Community Ice Sheet Model For Sea Level Prediction, William Lipscomb, Robert Bindschadler, Ed Bueler, David Holland, Jesse Johnson, Stephen Price

Computer Science Faculty Publications

Summary of a workshop that was held at Los Alamos National Laboratory, New Mexico, 18-20 August 2008, whose primary goal was to create a detailed plan for developing, testing, and implementing a Community Ice Sheet Model (CISM) to aid in predicting sea level rise.

Reinterpreting No Free Lunch, Jonathan E. Rowe, Michael D. Vose, Alden H. Wright

Computer Science Faculty Publications

Since it’s inception, the “No Free Lunch theorem” has concerned the application of symmetry results rather than the symmetries themselves. In our view, the conflation of result and application obscures the simplicity, generality, and power of the symmetries involved. This paper separates result from application, focusing on and clarifying the nature of underlying symmetries. The result is a general set-theoretic version of NFL which speaks to symmetries when arbitrary domains and co-domains are involved. Although our framework is deterministic, we note situations where our deterministic set-theoretic results speak nevertheless to stochastic algorithms.

"Your Cell Will Teach You Everything": Old Wisdom, Modern Science, And The Art Of Attention, Noreen L. Herzfeld

Computer Science Faculty Publications

Here is a brief excerpt of the content:

A brother came to Scetis to visit Abba Moses and asked him "Father, give me a word." The old man said to him "Go, sit in your cell, and your cell will teach you everything." ¹ Among the Desert Fathers, Christian monks of the fourth and fifth centuries, it was customary for a novice to go to an elder and ask for "a word," a word of advice, of counsel, a word to take home and reflect on. What does this word of advice say to us today?

A Multitasking World

"Your …

Probabilistic Analysis Of A Motif Discovery Algorithm For Multiple Sequences, Bin Fu, Ming-Yang Kao, Lusheng Wang

Computer Science Faculty Publications

We study a natural probabilistic model for motif discovery that has been used to experimentally test the quality of motif discovery programs. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet Σ. A motif G = g1g2 · · · gm is a string of m characters. Each background sequence is implanted into a probabilistically generated approximate copy of G. For an approximate copy b1b2 · · · bm of G, every character bi is probabilistically generated such that the probability for r $b_i\neq g_i$ is at …

The Informational Content Of Canonical Disjoint Np-Pairs, Christian Glaßer, Alan L. Selman, Liyu Zhang

Computer Science Faculty Publications

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between propositional proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: For which propositional proof systems f and g does the implication hold, and for which does it fail?

Q2: For which propositional proof systems of different strengths are the canonical pairs equivalent?

Q3: What do (non-)equivalent canonical pairs tell about the corresponding propositional proof systems?

Q4: Is every NP-pair (A, B), where A is NP-complete, strongly many-one equivalent to the …

User Interface Design, Moritz Stefaner, Sebastien Ferre, Saverio Perugini, Jonathan Koren, Yi Zhang

Computer Science Faculty Publications

As detailed in Chap. 1, system implementations for dynamic taxonomies and faceted search allow a wide range of query possibilities on the data. Only when these are made accessible by appropriate user interfaces, the resulting applications can support a variety of search, browsing and analysis tasks. User interface design in this area is confronted with specific challenges. This chapter presents an overview of both established and novel principles and solutions.

Exploring Out-Of-Turn Interactions With Websites, Saverio Perugini, Naren Ramakrishnan, Manuel A. Pérez-Quiñones, Mary E. Pinney, Mary Beth Rosson

Computer Science Faculty Publications

Hierarchies are ubiquitous on the web for structuring online catalogs and indexing multidimensional attributed data sets. They are a natural metaphor for information seeking if their levelwise structure mirrors the user's conception of the underlying domain. In other cases, they can be frustrating, especially if multiple drill‐downs are necessary to arrive at information of interest. To support a broad range of users, site designers often expose multiple faceted classifications or provide within‐page pruning mechanisms. We present a new technique, called out-of-turn interaction, that increases the richness of user interaction at hierarchical sites, without enumerating all possible completion paths in the …

A Secure Group Communication Architecture For Autonomous Unmanned Aerial Vehicle, Adrian N. Phillips, Barry Mullins, Richard Raines, Rusty O. Baldwin

Computer Science Faculty Publications

This paper investigates the application of a secure group communication architecture to a swarm of autonomous unmanned aerial vehicles (UAVs). A multicast secure group communication architecture for the low earth orbit (LEO) satellite environment is evaluated to determine if it can be effectively adapted to a swarm of UAVs and provide secure, scalable, and efficient communications. The performance of the proposed security architecture is evaluated with two other commonly used architectures using a discrete event computer simulation developed using MATLAB. Performance is evaluated in terms of the scalability and efficiency of the group key distribution and management scheme when the …