Computer Sciences Commons^™

Computational Complexity Of Approximate And Precise Data With Constraint Automaton, Dipty Singh

School of Computing: Dissertations, Theses, and Student Research

The DNA molecules packaged in structures called chromosomes within the cells of living organisms encode hereditary information that is passed on to their offspring. Using transcription and translation, the genes within these DNA molecules help in protein synthesis. Thus chromosomal DNA serves as a blueprint for the chemical processes of life.

In order to analyze a DNA sequence by currently available technology, we have to cut it into small fragments, e.g. by using restriction enzymes. The application of different restriction enzymes to the multiple copies of the same DNA sequence generates many overlapping fragments. In order to construct the original …

Propeller: A Scalable Metadata Organization For A Versatile Searchable File System, Lei Xu, Hong Jiang, Xue Liu, Lei Tian, Yu Hua, Jian Hu

School of Computing: Technical Reports

The exponentially increasing amount of data in file systems has made it increasingly important for users, administrators and applications to be able to fast retrieve files using file-search services, instead of replying on the standard file system API to traverse the hierarchical namespaces.  The quality of the file-search services  is significantly affected by the file-indexing overhead, the file-search performance and the accuracy of search results.  Unfortunately, the existing file-search solutions either are so poorly scalable that their performance degrades unacceptably when the systems scale up, or incur so much crawling delays that they produce acceptably inaccurate results.  We believe that …

Identifying Horizontal Gene Transfer Using Anomalies In Protein Structures And Sequences, Venkat Ram B. Santosh

School of Computing: Dissertations, Theses, and Student Research

Genetics has traditionally focused on vertical gene transfer, which is the passing of the genetic material of an organism to its offspring. However, recent studies in genetics increased the awareness that horizontal gene transfer, which is the passing of the genetic material of an organism to another organism that is not its offspring, is also a significant phenomenon. Horizontal gene transfer is thought to play a major role in the natural evolution of bacteria, such as, when several different types of bacteria all suddenly develop the same drug resistance genes. Artificial horizontal gene transfer occurs in genetic engineering.

This thesis …

Lessons Learned From Comprehensive Deployments Of Multiagent Cscl Applications I-Minds And Classroomwiki, Nobel Khandaker, Leen-Kiat Soh, L.D. Miller, Adam D. Eck, Hong Jiang

School of Computing: Faculty Publications

Recent years have seen a surge in the use of intelligent computer-supported collaborative learning (CSCL) tools for improving student learning in traditional classrooms. However, adopting such a CSCL tool in a classroom still requires the teacher to develop (or decide on which to adopt) the CSCL tool and the CSCL script, design the relevant pedagogical aspects (i.e., the learning objectives, assessment method, etc.) to overcome the associated challenges (e.g., free riding, student assessment, forming student groups that improve student learning, etc). We have used a multiagent-based system to develop a CSCL application and multiagent frameworks to form student groups that …

Cost And Reliability Considerations In Designing The Next-Generation Ip Over Wdm Backbone Networks, Byrav Ramamurthy, K. K. Ramakrishnan, Rakesh K. Sinha

School of Computing: Conference and Workshop Papers

To accommodate the increasing demands for bandwidth, Internet Service Providers (ISPs) have deployed higher speed links and reconfigurable optical add drop multiplexers (ROADMs) in their backbone networks. To address the reliability challenges due to failures and planned outages, ISPs typically use two backbone routers at each central office in a dual home configuration. Thus at the IP layer, redundant backbone routers as well as redundant transport equipment to interconnect them are deployed to provide reliability through node and path diversity. However, adding such redundant resources increases the overall cost of the network. Hence, a fundamental redesign of the backbone network …

A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Robert J. Woodward, Eugene C. Freuder

School of Computing: Conference and Workshop Papers

•General reformulation strategy for CSPs

–Multidimensional CSPs (MD-CSPs)

–Problem reformulation by value interchangeability

–A general reformulation strategy for MD-CSPs

•Game of Set: A new toy problem

–Game, CSP model

–Problem reformulation

–Algorithms & Results

•Conclusions

A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder

School of Computing: Conference and Workshop Papers

•General reformulation strategy for CSPs

–Multidimensional CSPs (MD-CSPs)

–Problem reformulation by value interchangeability

–A general reformulation strategy for MD-CSPs

•Game of Set: A new toy problem

–Game, CSP model

–Problem reformulation

–Algorithms & Results

•Conclusions

Solving Difficult Csps With Relational Neighborhood Inverse Consistency, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

School of Computing: Conference and Workshop Papers

•Introduction

•Relational Neighborhood Inverse Consistency

–Property, Algorithm, Improvements

•Reformulating the Dual Graph by

1.Redundancy removal ⟿ property wRNIC

2.Triangulation ⟿ property triRNIC

•Selection strategy: four alternative dual graphs

•Experimental Results

•Conclusion

A Real-Time Rfid Localization Experiment Using Propagation Models, Jason L. Brchan, Lianlin Zhao, Jiaqing Wu

School of Computing: Conference and Workshop Papers

This paper introduces a real-time localization system (RTLS) using efficient multiple propagation models to compensate for the drawback of the received signal strength technique. The RTLS is implemented on an active RFID system and uses received signal strength measurements and reference tags for ranging. The RTLS is implemented purely in software that post processes the received signal strength data from the reader and does not require any additional hardware or any modifications to the RFID reader or tags. The proposed algorithm using multiple propagation models improves the performance of the RTLS. Two-dimensional localization results are given for a four-reader system …

Refactoring Pipe-Like Mashups For End-User Programmers, Kathryn T. Stolee, Sebastian Elbaum

School of Computing: Conference and Workshop Papers

Mashups are becoming increasingly popular as end users are able to easily access, manipulate, and compose data from many web sources. We have observed, however, that mashups tend to suffer from deficiencies that propagate as mashups are reused. To address these deficiencies, we would like to bring some of the benefits of software engineering techniques to the end users creating these programs. In this work, we focus on identifying code smells indicative of the deficiencies we observed in web mashups programmed in the popular Yahoo! Pipes environment. Through an empirical study, we explore the impact of those smells on end-user …

Multi-Dimensional Models Facilitate Automatic Reformulation: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder

School of Computing: Conference and Workshop Papers

In this paper we describe a reformulation strategy for solving multidimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the uni-dimensional constraints in the problem, and exploits the approximate symmetries induced by the selected constraint on the domains in order to enforce this constraint on the simplified problem. We use the game of SET, a combinatorial card game, as a toy problem to motivate our strategy and to explain and illustrate its operation. However, we believe that our approach is applicable to more complex domains of scientific and industrial importance, and deserves more …

A Channel Model For Wireless Underground Sensor Networks Using Lateral Waves, Xin Dong, Mehmet C. Vuran

School of Computing: Conference and Workshop Papers

Wireless Underground Sensor Networks (WUSNs) are an emerging type of wireless sensor networks (WSNs), where sensor nodes are located under the ground and communicate through soil. The major challenge in the development of efficient communication protocols for WUSNs is the characterization of the underground channel. So far, none of the existing models fully capture all the components of electromagnetic signal propagation in the soil medium. In this paper, three major components that influence underground communication are identified: direct, reflected, and lateral waves, where the latter has not been analyzed for WUSNs so far. Accordingly, a closed-form three-wave (3W) channel model …

Seventh International Workshop On Software Engineering For Secure Systems (Sess 2011), Seok-Won Lee, Mattia Monga, Jan Jürjens

School of Computing: Conference and Workshop Papers

The 7th edition of the SESS workshop aims at providing a venue for software engineers and security researchers to exchange ideas and techniques. In fact, software is at core of most of the business transactions and its smart integration in an industrial setting may be the competitive advantage even when the core competence is outside the ICT field. As a result, the revenues of a firm depend directly on several complex software-based systems. Thus, stakeholders and users should be able to trust these systems to provide data and elaborations with a degree of confidentiality, integrity, and availability compatible with their …

Rightsizing Bundle Link Capacities For Energy Savings In The Core Network, Lin Liu, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Current core networks are composed of high-end routers which are connected by high-speed fibers. These optical connections are commonly over provisioned and in low utilization. Many of them are combined together to form bundle links or composite links and the component links are referred to as sublinks. These physical sublinks could be SONET connections, Ethernet circuits, wavelengths on a fiber, etc and they could be shut down or brought up independently. Selectively shutting down sublinks during low traffic periods could save a large amount of energy while keeping the network topology unchanged. Based on this concept, we propose a local …

Shhc: A Scalable Hybrid Hash Cluster For Cloud Backup Services In Data Centers, Lei Xu, Jian Hu, Stephen Mkandawire, Hong Jiang

School of Computing: Conference and Workshop Papers

Data deduplication techniques are ideal solutions for reducing both bandwidth and storage space requirements for cloud backup services in data centers. Current data deduplication solutions rely on comparing fingerprints (hash values) of data chunks to identify redundant data and store the fingerprints on a centralized server. This approach limits the overall throughput and concurrency performance in large scale systems. Furthermore, the slow seek time associated with hard disks degrades the performance of hash look up operations which are mainly random I/Os.

In this paper we present a scalable hybrid hash cluster (SHHC) to maintain a low-latency distributed hash table for …

A Survey Of Deployment Information Of Delay-Based Tcp Congestion Avoidance Algorithm For Transmitting Multimedia Data, Peng Yang, Lisong Xu

School of Computing: Conference and Workshop Papers

Multimedia traffic comprises a significant part of the total Internet traffic. Due to the real-time nature of the multimedia traffic, low queuing delay is critical to many multimedia applications. This requirement makes delay-based TCP congestion avoidance algorithms (or delay-based TCP algorithms for short) a good choice to transmit multimedia data, since they can help keep a low queuing delay in the Internet. However, the Internet traffic is controlled by heterogeneous TCP algorithms and many of them are non-delay-based. Thus, the effort made by the delay-based TCP algorithms to reduce the queuing delay is often offset by the non-delay-based TCP algorithms. …

Unifying Testing And Analysis Through Behavioral Coverage, Matthew B. Dwyer

School of Computing: Conference and Workshop Papers

The past decades have produced a wide-variety of automated techniques for assessing the correctness of software systems. In practice, when applied to large modern software systems all existing automated program analysis and verification techniques come up short. They might produce false error reports, exhaust available human or computational resources, or be incapable of reasoning about some set of important properties. Whatever their shortcoming, the goal of proving a system correct remains elusive.

Many people believe that, after an initial period of development, software systems are "mostly" correct — systems have much more correct behavior than incorrect behavior. Following this line …

End-User Programmers And Their Communities: An Artifact-Based Analysis, Kathryn T. Stolee, Sebastian Elbaum, Anita Sarma

School of Computing: Conference and Workshop Papers

End-user programmers outnumber professionals programmers, write software that matters to an increasingly large number of users, and face software engineering challenges that are similar to their professionals counterparts. Yet, we know little about how these end-user programmers create and share artifacts as part of a community. To gain a better understanding of these issues, we perform an artifact-based community analysis of 32,000 mashups from the Yahoo! Pipes repository. We observed that, like with other online communities, there is great deal of attrition but authors that persevere tend to improve over time, creating pipes that are more configurable, diverse, complex, and …

Adaptive Neighborhood Inverse Consistency As Lookahead For Non-Binary Csps, Robert J. Woodward, Shant K. Karakashian, Berthe Y. Choueiry, Christian Bessiere

School of Computing: Conference and Workshop Papers

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) for binary CSPs. In this paper, we introduce RNIC, the extension of NIC to nonbinary CSPs, and describe a practical algorithm for enforcing it. We propose an adaptive strategy to weaken or strengthen this property based on the connectivity of the network. We demonstrate the effectiveness of RNIC as a full lookahead strategy during search for solving difficult benchmark problems.

Diagnosis Of Multiple Scan-Chain Faults In The Presence Of System Logic Defects, Zhen Chen, Sharad C. Seth, Dong Xiang, Bhargab B. Bhattacharya

School of Computing: Conference and Workshop Papers

We present a combined hardware-software based approach to scan-chain diagnosis, when the outcome of a test may be affected by system faults occurring in the logic outside of the scan chain. For the hardware component we adopt the double-tree scan (DTS) chain architecture, which has previously been shown to be effective in reducing power, volume, and application time of tests for stuck-at and delay faults. We develop a version of flush test which can resolve a multiple fault in a DTS chain to a small number of suspect candidates. Further resolution to a unique multiple fault is enabled by the …

A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder

School of Computing: Conference and Workshop Papers

In this paper we describe a reformulation strategy for solving multi-dimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the uni-dimensional constraints in the problem. It exploits the approximate symmetries identified on the domain values in order to enforce the selected constraint on the simplified problem. This paper uses the game of SET, a combinatorial card game, to motivate and illustrate our strategy. We propose a multi-dimensional constraint model for SET, and describe a basic constraint solver for finding all solutions of an instance of the game. Then, we introduce an algorithm that …

Solving Difficult Csps With Relational Neighborhood Inverse Consistency, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

School of Computing: Conference and Workshop Papers

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a strong local consistency property for binary CSPs. While enforcing NIC can significantly filter the variables domains, the proposed algorithm is too costly to be used on dense graphs or for lookahead during search. In this paper, we introduce and characterize Relational Neighborhood Inverse Consistency (RNIC) as a local consistency property that operates on the dual graph of a non-binary CSP. We describe and characterize a practical algorithm for enforcing it. We argue that defining RNIC on the dual graph unveils unsuspected opportunities to reduce the computational cost of our …

Reformulating The Dual Graphs Of Csps To Improve The Performance Of Relational Neighborhood Inverse Consistency, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

School of Computing: Conference and Workshop Papers

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a new local consistency property for binary Constraint Satisfaction Problems (CSPs). Two advantages of the algorithm for enforcing NIC is that it automatically adapts its filtering power to the local connectivity of the network and has insignificant space overhead. However, studies on binary CSPs have shown that enforcing NIC is not effective on sparse graphs and too costly on dense graphs. In (Woodward et al. 2011), we introduced an algorithm for enforcing Relational Neighborhood Inverse Consistency (RNIC), which is an extension of NIC to non-binary CSPs. In this paper, we …

Reformulating The Dual Graphs Of Csps To Improve The Performance Of Rnic, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

School of Computing: Conference and Workshop Papers

•Introduction

•Relational Neighborhood Inverse Consistency

–Property & algorithm

•Reformulating the Dual Graph by

1.Removing redundant edges, yields property wRNIC

2.Triangulation, yields property triRNIC

•Selection strategy: four alternative dual graphs

•Experimental Results

•Conclusion

Reformulating R(*;M)C With Tree Decomposition, Shant Karakashian, Robert J. Woodward, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

Local consistency properties and algorithms for enforcing them are central to the success of Constraint Processing. Recently, we have demonstrated the importance of higher levels of consistency and the effectiveness of their algorithms for solving difficult problems (Karakashian et al. 2010; Woodward et al. 2011). In this paper, we introduce two reformulation techniques for improving the effectiveness of our algorithm for the relational consistency property R(*;m)C (Karakashian et al. 2010). Both techniques exploit a tree decomposition of the constraint network of a Constraint Satisfaction Problem (CSP), which is a tree embedding of the network. Our first reformulation technique …

Reformulating R(*,M)C With Tree Decomposition, Shant Karakashian, Robert J. Woodward, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

•Introduction

•R(*,m)C Property & Algorithm

•Exploit Tree Decomposition to

–Avoid useless update & reduce propagation effort

↪ Update queue: PROCESSQ ⟿ PROCESSMQ

↪ The two algorithms yield the same filtering

–Synthesize & add new constraints to improve propagation

↪ Property enforced: R(*,m)C ⟿ T-R(*,m,z)C

↪ The same algorithm yields stronger filtering

•Experimental Results

•Conclusion

Feature Interaction Faults Revisited: An Exploratory Study, Brady J. Garvin, Myra B. Cohen

School of Computing: Conference and Workshop Papers

While a large body of research is dedicated to testing for feature interactions in configurable software, there has been little work that examines what constitutes such a fault at the code level. In consequence, we do not know how prevalent real interaction faults are in practice, what a typical interaction fault looks like in code, how to seed interaction faults, or whether current interaction testing techniques are effective at finding the faults they aim to detect.

We make a first step in this direction, by deriving a white box criterion for an interaction fault. Armed with this criterion, we perform …

A Dynamic Local Method For Bandwidth Adaptation In Bundle Links To Conserve Energy In Core Networks, Lin Liu, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Energy savings in bundle links of the core network has been investigated recently. The bundle link technique is widely used in current core networks to provide higher bandwidth and more resilience. Basically a bundle link is composed of several high-speed physical sublinks which could be SONET connections, Ethernet circuits, etc. in order to make them work together as a virtual connection. In current network operations, all of the sublinks are activated if the bundle link is powered on although the sublinks could be shut down or brought up independently. Smartly and dynamically shutting down and bringing up sublinks and their …

Minimizing Resource Blocking Rate In Goobs, Shivashis Saha, Jitender S. Deogun, Lisong Xu

School of Computing: Conference and Workshop Papers

The state of the resources at a destination in Grid computing over OBS architecture (GoOBS) may change between a task’s selection of a destination and its arrival at the destination. These changes in the availability of the resources requested at the destination may lead to blocking of tasks, and thus increase the resource blocking rate.

In this paper, we investigate the resource scheduling problem in GoOBS. Our objective is to minimize the resource blocking rate by containing the impact of the changes in the availability of the resources at a destination. We propose a non-selfish destination selection paradigm to minimize …

Refactoring Pipe-Like Mashups For End-User Programmers, Kathryn T. Stolee, Sebastian Elbaum

School of Computing: Conference and Workshop Papers

Mashups are becoming increasingly popular as end users are able to easily access, manipulate, and compose data from many web sources. We have observed, however, that mashups tend to suffer from deficiencies that propagate as mashups are reused. To address these deficiencies, we would like to bring some of the benefits of software engineering techniques to the end users creating these programs. In this work, we focus on identifying code smells indicative of the deficiencies we observed in web mashups programmed in the popular Yahoo! Pipes environment. Through an empirical study, we explore the impact of those smells on end-user …