Computer Sciences Commons^™

Idea: An Infrastructure For Detection-Based Adaptive Consistency Control In Replicated Services, Yijun Lu, Ying Lu, Hong Jiang

School of Computing: Technical Reports

In Internet-scale distributed systems, replication-based scheme has been widely deployed to increase the availability and efficiency of services. Hence, consistency maintenance among replicas becomes an important research issue because poor consistency results in poor QoS or even monetary loss. Recent research in this area focuses on enforcing a certain consistency level, instead of perfect consistency, to strike a balance between consistency guarantee and system’s scalability.
In this paper, we argue that, besides balancing consistency and scalability, it is equally, if not more, important to achieve adaptability of consistency maintenance. I.e., the system adjusts its consistency level on the fly to …

Software Pattern Communities: Current Practices And Challenges, Scott Henninger, Victor Corrêa

School of Computing: Technical Reports

Software pattern users, software developers creating high-quality software systems, have few resources available to support pattern-based development practices. Patterns are currently disseminated in disjoint collections in various publishing mediums with little or no technology support. As the number of patterns and diversity of pattern types continue to proliferate, potential pattern users are faced with difficulties of understanding what patterns exist and when, where, and how to use them. This defeats the very purpose of patterns as a medium to encapsulate and disseminate recurring design experiences. In this paper, an initial study is done among a set of pattern collections in …

Spatial Clustering Using The Likelihood Function, April Kerby, David Marx, Ashok Samal, Viacheslav Adamchuk

School of Computing: Conference and Workshop Papers

Clustering has been widely used as a tool to group multivariate observations that have similar characteristics. However, there have been few attempts at formulating a method to group similar multivariate observations while taking into account their spatial location. This paper proposes a method to spatially cluster similar observations based on their likelihoods. The geographic or spatial location of the observations can be incorporated into the likelihood of the multivariate normal distribution through the variance-covariance matrix. The variance-covariance matrix can be computed using any specific spatial covariance structure. Therefore, observations within a cluster which are spatially close to one another will …

Sofya: Supporting Rapid Development Of Dynamic Program Analyses For Java, Alex Kinneer, Matthew B. Dwyer, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Dynamic analysis is an increasingly important means of supporting software validation and maintenance. To date, developers of dynamic analyses have used low-level instrumentation and debug interfaces to realize their analyses. Many dynamic analyses, however, share multiple common high-level requirements, e.g., capture of program data state as well as events, and efficient and accurate event capture in the presence of threading. We present SOFYA – an infra-structure designed to provide high-level, efficient, concurrency-aware support for building analyses that reason about rich observations of program data and events. It provides a layered, modular architecture, which has been successfully used to rapidly develop …

Helping End-User Programmers “Engineer” Software: An Opportunity For Empirical Researchers, Gregg Rothermel

School of Computing: Conference and Workshop Papers

While much of the software that people depend on is written by professional software engineers, increasingly, important applications are being created by non-professional (end-user) programmers. Using tools such as spreadsheet environments and web authoring tools, these programmers are creating software that is being used to support significant activities and inform decisions. Such software needs to work dependably and increase user productivity, but evidence shows that it frequently does not. For example, studies have shown that a large percentage of the spreadsheets created by end-users contain faults, and data suggests that time spent maintaining web macros may actually impede their users’ …

An Interactive Constraint-Based Approach To Sudoku, Christopher Reeson, Kai-Chen Huang, Ken Bayer, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

• To the public:

– Illustrate the power of CP

• For the research:

– Investigate the use of CP to interactively support & guide human players

• For education:

– Teach basic and advanced CP techniques

• For insight into human reasoning:

– Understand how it differs from algorithmic approaches

Experimenting With Software Testbeds For Evaluating New Technologies, Mikael Lindvall, Ioana Rus, Paolo Donzelli, Atif Memon, Marvin Zelkowitz, Aysu Betin-Can, Tevfik Bultan, Chris Ackermann, Bettina Anders, Sima Asgari, Victor Basili, Lorin Hochstein, Jörg Fellmann, Forrest Shull, Roseanne Tvedt, Daniel Pech, Daniel Hirschbach

School of Computing: Faculty Publications

The evolution of a new technology depends upon a good theoretical basis for developing the technology, as well as upon its experimental validation. In order to provide for this experimentation, we have investigated the creation of a software testbed and the feasibility of using the same testbed for experimenting with a broad set of technologies. The testbed is a set of programs, data, and supporting documentation that allows researchers to test their new technology on a standard software platform. An important component of this testbed is the Unified Model of Dependability (UMD), which was used to elicit dependability requirements for …

An Analysis Of Sexual Dimorphism In The Human Face, Ashok Samal, Vanitha Subramani, David B. Marx

School of Computing: Faculty Publications

Abstract Human beings can distinguish between a male and a female face without much difficulty. The science of recognizing and differentiating different faces by humans is not completely understood and is still under research. Sexual dimorphism is common in humans and indeed in other species of animals as well. Significant differences between males and females exist in many aspects like size, color, body shapes, and weight. In this research, we characterize and analyze the sexual dimorphism in the human face as a function of age and of face features. Features are grouped into six categories: head, eyes, orbits, nose, lips, …

A Content Based Pattern Analysis System For A Biological Specimen Collection, Joyita Mallik, Ashok K. Samal, Scott L. Gardner

School of Computing: Conference and Workshop Papers

Over the years many research collections of biological specimen have been developed for research in biological sciences. Number of specimens in some of these collections can be as high as several millions. There is a move to convert these physical specimens into digital images. This research is motivated by the need to develop techniques to mine useful information from these large collections of specimen images. Specific focus of this research is on the collection of parasites in the Harold W. Manter Laboratory (HWML) Parasite Collection, one of the top four parasite collections in the world. These parasites closely resemble in …

A Two-Phase Approach For Dynamic Lightpath Scheduling In Wdm Optical Networks, Lu Shen, Xi Yang, Ajay Todimala, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Lightpath scheduling is an important capability in next-generation wavelength-division multiplexing (WDM) optical networks to reserve resources in advance for a specified time period while provisioning end-to-end lightpaths. In a dynamic environment, the end user requests for dynamic scheduled lightpath demands (D-SLDs) need to be serviced without the knowledge of future requests. Even though the starting time of the request may be hours or days from the current time, the end-user however expects a quick response as to whether the request could be satisfied. We propose a two-phase approach to dynamically schedule and provision D-SLDs. In the first phase, termed the …

Network Architectures For Live Peer-To-Peer Media Streaming, Jagannath Ghoshal, Lisong Xu, Byrav Ramamurthy, Miao Wang

School of Computing: Technical Reports

Peer-to-Peer (P2P) media streaming networks, motivated by the huge success of P2P file downloading networks, have recently attracted a lot of research interest. However, it is challenging to design P2P media streaming networks because of the stringent time constraints on the delivered media streams, which require more efficient and resilient overlay architectures. In this paper, we focus on live P2P media streaming networks, a promising application flourishing in the Internet and which requires the distribution of live (not stored) multimedia content to subscribers. We review the architectures for live P2P media streaming networks, and consider both overlay topologies and their …

Layered Clustering Communication Protocol For Wireless Sensor Networks, Yong Wang, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

In this paper, we propose a Layered Clustering Hierarchy (LCH) communication protocol for Wireless Sensor Networks (WSNs). The design of LCH has two goals: scalability and energy-efficiency. In LCH, the sensor nodes are organized as a layered clustering structure. Each layer runs a distributed clustering protocol. By randomizing the rotation of cluster heads in each layer, the energy load is distributed evenly across sensors in the network. Our simulations show that LCH is effective in densely deployed sensor networks. On average, 70% of live sensor nodes are involved directly in the clustering communication hierarchy. Moreover, the simulations also show that …

Keyrev: An Efficient Key Revocation Scheme For Wireless Sensor Networks, Yong Wang, Byrav Ramamurthy, Xukai Zou

School of Computing: Conference and Workshop Papers

Key management is a core mechanism to ensure the security of applications and network services in wireless sensor networks. It includes two aspects: key distribution and key revocation. Key distribution has been extensively studied in the context of sensor networks. However, key revocation has received relatively little attention. Existing key revocation schemes can be divided into two categories: centralized key revocation scheme and distributed key revocation scheme. In this paper, we first summarize the current key revocation schemes for sensor networks. Then, we propose an efficient centralized key revocation scheme, KeyRev, for wireless sensor networks. Unlike most proposed key revocation …

Group Rekeying Schemes For Secure Group Communication In Wireless Sensor Networks, Yong Wang, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Wireless sensor networks are promising solutions for many applications. However, wireless sensor nodes suffer from many constraints such as low computation capability, small memory, limited energy resources, and so on. Grouping is an important technique to localize computation and reduce communication overhead in wireless sensor networks. In this paper, we use grouping to refer to the process of combining a set of sensor nodes with similar properties. We propose two centralized group rekeying (CGK) schemes for secure group communication in sensor networks. The lifetime of a group is divided into three phases, i.e., group formation, group maintenance, and group dissolution. …

A-Mac: Adaptive Medium Access Control For Next Generation Wireless Terminals, Mehmet C. Vuran, Ian F. Akyildiz

School of Computing: Faculty Publications

Next Generation (NG) wireless networks are envisioned to provide high bandwidth to mobile users via bandwidth aggregation over heterogeneous wireless architectures. NG wireless networks, however, impose challenges due to their architectural heterogeneity in terms of different access schemes, resource allocation techniques as well as diverse quality of service requirements. These heterogeneities must be captured and handled dynamically as mobile terminals roam between different wireless architectures. However, to address these challenges, the existing proposals require either a significant modification in the network structure and in base stations or a completely new architecture, which lead to integration problems in terms of implementation …

A Method For Estimating Fractal Dimension Of Tree Crowns From Digital Images, Dongsheng Zhang, Ashok Samal, James R. Brandle

School of Computing: Faculty Publications

A new method for estimating fractal dimension of tree crowns from digital images is presented. Three species of trees, Japanese yew (Taxus cuspidata Sieb & Zucc), Hicks yew (Taxus × media), and eastern white pine (Pinus strobus L.), were studied. Fractal dimensions of Japanese yew and Hicks yew range from 2.26 to 2.70. Fractal dimension of eastern white pine range from 2.14 to 2.43. The difference in fractal dimension between Japanese yew and eastern white pine was statistically significant at 0.05 significance level as was the difference in fractal dimension between Hicks yew and eastern white …

Bandit-Based Algorithms For Budgeted Learning, Kun Deng, Chris Bourke, Stephen Scott, Julie Sunderman, Yaling Zheng

School of Computing: Conference and Workshop Papers

We explore the problem of budgeted machine learning, in which the learning algorithm has free access to the training examples’ labels but has to pay for each attribute that is specified. This learning model is appropriate in many areas, including medical applications. We present new algorithms for choosing which attributes to purchase of which examples in the budgeted learning model based on algorithms for the multi-armed bandit problem. All of our approaches outperformed the current state of the art. Furthermore, we present a new means for selecting an example to purchase after the attribute is selected, instead of selecting an …

An Interactive Constraint-Based Approach To Sudoku, Christopher G. Reeson, Kai-Chen Huang, Ken Bayer, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

We present SOLVER, a Java applet that uses Constraint Processing (CP) techniques to assist human users in solving Sudoku puzzles. We also showcase CONSTRUCTOR, another applet that allows users to enter and store puzzles, which they can then load in SOLVER. These applets are available from sudoku.unl.edu/Solver and sudoku. unl.edu/Constructor. Our goals are as follows:

• To the public: Illustrate the power of CP techniques in the context of a popular easily approachable puzzle.

• For the research: Investigate how to use CP to interactively support and guide human players.

• For education: Use the Sudoku puzzle as a means …

Efficient Rtl Coverage Metric For Functional Test Selection, Jian Kang, Sharad C. Seth, Vijay Gangaram

School of Computing: Conference and Workshop Papers

For performance-critical microprocessors, efficient test-selection methods are needed for reusing a subset of functional validation tests to detect manufacturing defects. Our new input/output transition fault-coverage metric (TRIO) at the register-transfer level is shown to perform much better than current metric in test selection at only an incrementally higher computational cost. TRIO may also be used for testability analysis early in the design cycle.

Symbolic Path Sensitization Analysis And Applications, Jian Kang, Sharad C. Seth, Shashank K. Mehta

School of Computing: Conference and Workshop Papers

A new symbolic approach models the sensitization paths to selected primary output(s) as Boolean equations, with satisfying solutions representing the set of all sources of single and multiple sensitizations in the circuit. The paper discusses two applications of this idea: model-free fault diagnosis and input sensitization analysis.

A Note On The Karp-Lipton Collapse For The Exponential Hierarchy, Chris Bourke

School of Computing: Technical Reports

We extend previous collapsing results involving the exponential hierarchy by using recent hardness-randomness trade-off results. Specifically, we show that if the second level of the exponential hierarchy has polynomial-sized circuits, then it collapses all the way down to MA.

Real-Time Divisible Load Scheduling For Cluster Computing, Xuan Lin, Ying Lu, Jitender S. Deogun, Steve Goddard

School of Computing: Technical Reports

Cluster computing has emerged as a new paradigm for solving large-scale problems. To enhance QoS and provide performance guarantees in cluster computing environments, various real-time scheduling algorithms and workload models have been investigated. Computational loads that can be arbitrarily divided into independent pieces represent many real-world applications. Divisible load theory (DLT) provides insight into distribution strategies for such computations. However, the problem of providing performance guarantees to divisible load applications has not yet been systematically studied. This paper investigates such algorithms for a cluster environment. Design parameters that affect the performance of these algorithms and scenarios when the choice of …

Dynamic Characterization Of Web Application Interfaces, Marc Randall Fisher Ii, Sebastian Elbaum, Gregg Rothermel

School of Computing: Technical Reports

Web applications are increasingly prominent in society, serving a wide variety of user needs. Engineers seeking to enhance, test, and maintain these applications and third-party programmers wishing to utilize these applications need to understand their interfaces. In this paper, therefore, we present methodologies for characterizing the interfaces of web applications through a form of dynamic analysis, in which directed requests are sent to the application, and responses are analyzed to draw inferences about its interface. We also provide mechanisms to increase the scalability of the approach. Finally, we evaluate the approach’s performance on six non-trivial web applications.

Parallel Randomized State-Space Search, Matthew B. Dwyer, Sebastian Elbaum, Suzette Person, Rahul Purandare

School of Computing: Technical Reports

Model checkers search the space of possible program behaviors to detect errors and to demonstrate their absence. Despite major advances in reduction and optimization techniques, state-space search can still become cost-prohibitive as program size and complexity increase. In this paper, we present a technique for dramatically improving the cost-effectiveness of state-space search techniques for error detection using parallelism. Our approach can be composed with all of the reduction and optimization techniques we are aware of to amplify their benefits. It was developed based on insights gained from performing a large empirical study of the cost-effectiveness of randomization techniques in state-space …

Exploiting Geographical And Temporal Locality To Boost Search Efficiency In Peer-To-Peer Systems, Hailong Cai, Jun Wang

School of Computing: Faculty Publications

As a hot research topic, many search algorithms have been presented and studied for unstructured peer-to-peer (P2P) systems during the past few years. Unfortunately, current approaches either cannot yield good lookup performance, or incur high search cost and system maintenance overhead. The poor search efficiency of these approaches may seriously limit the scalability of current unstructured P2P systems. In this paper, we propose to exploit two-dimensional locality to improve P2P system search efficiency. We present a locality-aware P2P system architecture called Foreseer, which explicitly exploits geographical locality and temporal locality by constructing a neighbor overlay and a friend overlay, respectively. …

Adaptive Online Program Analysis: Concepts, Infrastructure, And Applications, Matthew B. Dwyer, Alex Kinneer, Sebastian Elbaum

School of Computing: Technical Reports

Dynamic analysis of state-based properties is being applied to problems such as validation, intrusion detection, and program steering and reconfiguration. Dynamic analysis of such properties, however, is used rarely in practice due to its associated run-time overhead that causes multiple orders of magnitude slowdown of program execution. In this paper, we present an approach for exploiting the state-fullness of specifications to reduce the cost of dynamic program analysis. With our approach, the results of the analysis are guaranteed to be identical to those of the traditional, expensive dynamic analyses, yet with overheads between 23% and 33% relative to the un-instrumented …

On The Use Of Mutation Faults In Empirical Assessments Of Test Case Prioritization Techniques, Hyunsook Do, Gregg Rothermel

School of Computing: Faculty Publications

Regression testing is an important activity in the software life cycle, but it can also be very expensive. To reduce the cost of regression testing, software testers may prioritize their test cases so that those which are more important, by some measure, are run earlier in the regression testing process. One potential goal of test case prioritization techniques is to increase a test suite’s rate of fault detection (how quickly, in a run of its test cases, that test suite can detect faults). Previous work has shown that prioritization can improve a test suite’s rate of fault detection, but the …

Image Interpolation By Two-Dimensional Parametric Cubic Convolution, Jiazheng Shi, Stephen E. Reichenbach

School of Computing: Faculty Publications

Cubic convolution is a popular method for image interpolation. Traditionally, the piecewise-cubic kernel has been derived in one dimension with one parameter and applied to two-dimensional (2-D) images in a separable fashion. However, images typically are statistically nonseparable, which motivates this investigation of nonseparable cubic convolution. This paper derives two new nonseparable, 2-D cubic-convolution kernels. The first kernel, with three parameters (designated 2D-3PCC), is the most general 2-D, piecewise-cubic interpolator defined on [-2, 2] x [-2, 2] with constraints for biaxial symmetry, diagonal (or 90 rotational) symmetry, continuity, and smoothness. The second kernel, with five parameters (designated 2D-5PCC), relaxes the …

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.

Controlling Factors In Evaluating Path-Sensitive Error Detection Techniques, Matthew B. Dwyer, Suzette Person, Sebastian Elbaum

School of Computing: Technical Reports

Recent advances in static program analysis have made it possible to detect errors in applications that have been thoroughly tested and are in wide-spread use. The ability to find errors that have eluded traditional validation methods is due to the development and combination of sophisticated algorithmic techniques that are embedded in the implementations of analysis tools. Evaluating new analysis techniques is typically performed by running an analysis tool on a collection of subject programs, perhaps enabling and disabling a given technique in different runs. While seemingly sensible, this approach runs the risk of attributing improvements in the cost-effectiveness of the …