Physical Sciences and Mathematics Commons^™

A Note On The Fine Structure Constant, Bilal Khan, Irshadullah Khan

CSE Technical Reports

We derive the numerical value of the fine structure constant in purely number-theoretic terms, under the assumption that in a system of charges between two parallel conducting plates, the Casimir energy and the mutual Coulomb interaction energy agree.

Work-In-Progress Reports Submitted To The Library Of Congress As Part Of Digital Libraries, Intelligent Data Analytics, And Augmented Description, Chulwoo Pack, Yi Liu, Leen-Kiat Soh, Elizabeth Lorang

CSE Technical Reports

This document includes work-in-progress reports submitted to the Library of Congress as part of the Aida digital libraries research team's work on Digital Libraries, Intelligent Data Analytics, and Augmented Description: A Demonstration Project. These work-in-progress reports provide a snapshot glimpse, as well as underlying rationale and decision-making, at various points in the development of the project and its machine learning explorations. Reports cover explorations on historic newspapers, minimally-processed manuscript collections, materials digitized from physical originals and those digitized from microform surrogates, and investigate challenges related to image segmentation and document zoning, classification, document image quality analysis, metadata generation, and more.

Smart Underground Antenna Arrays: A Soil Moisture Adaptive Beamforming Approach, Abdul Salam, Mehmet C. Vuran

CSE Technical Reports

In this paper, a novel framework for underground beamforming using adaptive antenna arrays is presented. Based on the analysis of propagation in wireless underground channel, a theoretical model is developed which uses soil moisture information and feedback mechanism to improve performance wireless underground communications. Array element in soil has been analyzed empirically and impacts of soil type and soil moisture on return loss and resonant frequency are investigated. Beam patterns are investigated to communicate with both underground and above ground devices. Depending on the incident angle, refraction from soil-air interface has the adverse effects in the UG communications. It is …

Connecting Program Synthesis And Reachability: Automatic Program Repair Using Test-Input Generation, Thanhvu Nguyen, Westley Weimer, Deepak Kapur, Stephanie Forrest

CSE Technical Reports

We prove that certain formulations of program synthesis and reachability are equivalent. Specifically, our constructive proof shows the reductions between the template-based synthesis problem, which generates a program in a pre-specified form, and the reachability problem, which decides the reachability of a program location. This establishes a link between the two research fields and allows for the transfer of techniques and results between them.

To demonstrate the equivalence, we develop a program repair prototype using reachability tools. We transform a buggy program and its required specification into a specific program containing a location reachable only when the original program can …

Ultimate Codes: Near-Optimal Mds Array Codes For Raid-6, Zhijie Huang, Hong Jiang, Chong Wang, Ke Zhou, Yuhong Zhao

CSE Technical Reports

As modern storage systems have grown in size and complexity, RAID-6 is poised to replace RAID-5 as the dominant form of RAID architectures due to its ability to protect against double disk failures. Many excellent erasure codes specially designed for RAID-6 have emerged in recent years. However, all of them have limitations. In this paper, we present a class of near perfect erasure codes for RAID-6, called the Ultimate codes. These codes encode, update and decode either optimally or nearly optimally, regardless of what the code length is. This implies that utilizing these codes we can build highly efficient and …

S-Code: Lowest Density Mds Array Codes For Raid-6, Zhijie Huang, Hong Jiang, Ke Zhou, Yuhong Zhao, Chong Wang

CSE Technical Reports

RAID, a storage architecture designed to exploit I/O parallelism and provide data reliability, has been deployed widely in computing systems as a storage building block. In large scale storage systems, in particular, RAID-6 is gradually replacing RAID-5 as the dominant form of disk arrays due to its capability of tolerating concurrent failures of any two disks. MDS (maximum distance separable) array codes are the most popular erasure codes that can be used for implementing RAID-6, since they enable optimal storage efficiency and efficient encoding and decoding algorithms. In this paper, we propose a new class of MDS array codes called …

Providing Flexible File-Level Data Filtering For Big Data Analytics, Lei Xu, Ziling Huang, Hong Jiang, Lei Tian, David Swanson

CSE Technical Reports

The enormous amount of big data datasets impose the needs for effective data filtering technique to accelerate the analytics process. We propose a Versatile Searchable File System, VSFS, which provides a transparent, flexible and near real-time file-level data filtering service by searching files directly through the file system. Therefore, big data analytics applications can transparently utilize this filtering service without application modifications. A versatile index scheme is designed to adapt to the exploratory and ad-hoc nature of the big data analytics activities. Moreover, VSFS uses a RAM-based distributed architecture to perform file indexing. The evaluations driven by three real-world analytics …

Vsfs: A Versatile Searchable File System For Hpc Analytics, Lei Xu, Ziling Huang, Hong Jiang, Lei Tian, David Swanson

CSE Technical Reports

Big-data/HPC analytics applications have urgent needs for file-search services to drastically reduce the scale of the input data to accelerate analytics. Unfortunately, the existing solutions either are poorly scalable for large-scale systems, or lack well-integrated interface to allow applications to easily use them. We propose a distributed searchable file system, VSFS, which provide a novel and flexible POSIX-compatible searchable file system namespace that can be seamlessly integrate with any legacy code without modification. Additionally, to provide real-time indexing and searching performance, VSFS uses DRAM-based distributed consistent hashing ring to manages all file-index. The results of our evaluation show that VSFS …

Solving The Search For Suitable Code: An Initial Implementation, Kathryn T. Stolee, Sebastian Elbaum

CSE Technical Reports

Searching for code is a common task among programmers, with the ultimate goal of finding and reusing code or getting ideas for implementation. While the process of searching for code - issuing a query and selecting a relevant match - is straightforward, several costs must be balanced, including the costs of specifying the query, examining the results to find desired code, and not finding a relevant result. For the popular syntactic searches the query cost is quite low, but the results are often vague or irrelevant, so the examination cost is high and matches may not be found. Semantic searches …

A Scalable Inline Cluster Deduplication Framework For Big Data Protection, Yinjin Fu, Hong Jiang, Nong Xiao

CSE Technical Reports

Cluster deduplication has become a widely deployed technology in data protection services for Big Data to satisfy the requirements of service level agreement (SLA). However, it remains a great challenge for cluster deduplica- tion to strike a sensible tradeoff between the conflicting goals of scalable dedu- plication throughput and high duplicate elimination ratio in cluster systems with low-end individual secondary storage nodes. We propose Σ-Dedupe, a scalable inline cluster deduplication framework, as a middleware deployable in cloud da- ta centers, to meet this challenge by exploiting data similarity and locality to op- timize cluster deduplication in inter-node and intra-node scenarios, …

Relational Neighborhood Inverse Consistency For Constraint Satisfaction, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Technical Reports

Freuder and Elfe [1996] introduced Neighborhood Inverse Consistency (NIC) as a new local consistency property for Constraint Satisfaction Problems (CSPs) that filters the domains of variables. 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. In this document, we discuss Relational Neighborhood Inverse Consistency (RNIC), which is an extension of NIC to filter relations introduced in [Woodward et al., 2011a], how we enhance the propagation effectiveness by reformulating the dual graph of the CSP. We also describe an automated selection policy …

Isomorph-Free Generation Of 2-Connected Graphs With Applications, Derrick Stolee

CSE Technical Reports

Many interesting graph families contain only 2-connected graphs, which have ear decompositions. We develop a technique to generate families of unlabeled 2-connected graphs using ear augmentations and apply this technique to two problems. In the first application, we search for uniquely Kr-saturated graphs and find the list of uniquely K4-saturated graphs on at most 12 vertices, supporting current conjectures for this problem. In the second application, we verify the Edge Reconstruction Conjecture for all 2-connected graphs on at most 12 vertices. This technique can be easily extended to more problems concerning 2-connected graphs.

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

CSE 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 …

Tree-Based Algorithms For Computing K-Combinations And K-Compositions, Shant Karakashian, Berthe Y. Choueiry

CSE Technical Reports

In this document, we describe two tree-based algorithms for computing all k-combinations and k-compositions of a finite set.

We have developed two algorithms for solving the following combinatorial tasks:

• Given a finite set S and a natural number k, find all subsets of S of size k. In the literature, this problem is called k-subsets and k-combinations.

• Given two natural numbers k, n where k [less than or equal to] n, find all k-compositions of n where a k-composition is an ordered combination of k nonzero natural numbers whose sum is n. Note that in the literature, a …

Rapport: Semantic-Sensitive Namespace Management In Large-Scale File Systems, Yu Hua, Hong Jiang, Yifeng Zhu, Dan Feng

CSE Technical Reports

Explosive growth in volume and complexity of data exacerbates the key challenge to effectively and efficiently manage data in a way that fundamentally improves the ease and efficacy of their use. Existing large-scale file systems rely on hierarchically structured namespace that leads to severe performance bottlenecks and renders it impossible to support real-time queries on multi-dimensional attributes. This paper proposes a novel semantic-sensitive scheme, called Rapport, to provide dynamic and adaptive namespace management and support complex queries. The basic idea is to build files’ namespace by utilizing their semantic correlation and exploiting dynamic evolution of attributes to support namespace management. …

Dsfs: Decentralized Security For Large Parallel File Systems, Zhongying Niu, Hong Jiang, Ke Zhou, Dan Feng, Tianming Yang, Dongliang Lei, Anli Chen

CSE Technical Reports

This paper describes DSFS, a decentralized security system for large parallel file system. DSFS stores global access control lists (ACLs) in a centralized decisionmaking server and pushes pre-authorization lists (PALs) into storage devices. Thus DSFS allows users to flexibly set any access control policy for the global ACL or even change the global ACL system without having to upgrade the security code in their storage devices. With pre-authorization lists, DSFS enables a networkattached storage device to immediately authorize I/O, instead of demanding a client to acquire an authorization from a centralized authorization server at a crucial time. The client needs …

Coset: Cooperative Set Last Level Caches, Dongyuan Zhan, Hong Jiang, Sharad Seth

CSE Technical Reports

The speed gap between processors and DRAM remains a crit-ical performance bottleneck for contemporary computer systems, which necessitates an effective management of last level caches (LLC) to minimize expensive off-chip accesses. However, because all sets in a conventional set-associative cache design are statically assigned an equal number of blocks, the LLC capacity utilization can drastically diminish when the cache actually exhibits non-uniform capacity demands across the sets. To reveal the wide exis-tence of set-level non-uniformity of capacity demand in real appli-cations, this technical report first establishes an accurate metric for measuring individual sets’ capacity demands by developing a group of …

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

CSE Technical Reports

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 …

Exploiting Set-Level Non-Uniformity Of Capacity Demand To Enhance Cmp Cooperative Caching, Dongyuan Zhan, Hong Jiang, Sharad C. Seth

CSE Technical Reports

As the Memory Wall remains a bottleneck for Chip Multiprocessors (CMP), the effective management of CMP last level caches becomes of paramount importance in minimizing expensive off-chip memory accesses. For the CMPs with private last level caches, Cooperative Caching (CC) has been proposed to enable capacity sharing among private caches by spilling an evicted block from one cache to another. But this eviction-driven CC does not necessarily promote cache performance since it implicitly favors the applications full of block evictions regardless of their real capacity demand. The recent Dynamic Spill-Receive (DSR) paradigm improves cooperative caching by prioritizing applications with higher …

Design Of An All-Optical Wdm Lightpath Concentrator, Shivashis Saha, Jitender S. Deogun

CSE Technical Reports

A design of a nonblocking, all-optical lightpath concentrator using WOC and WDM crossbar switches is presented. The proposed concentrator is highly scalable, cost-efficient, and can switch signals in both space and wavelength domains without requiring a separate wavelength conversion stage.

Selection Of Switching Sites In All-Optical Nework Topology Design, Shivashis Saha, Eric D. Manley, Jitender S. Deogun

CSE Technical Reports

In this paper, we consider the problem of topology design for optical networks. We investigate the problem of selecting switching sites to minimize total cost of the optical network. The cost of an optical network can be expressed as a sum of three main factors: the site cost, the link cost, and the switch cost. To the best of our knowledge, this problem has not been studied in its general form as investigated in this paper. We present a mixed integer quadratic programming (MIQP) formulation of the problem to find the optimal value of the total network cost. We also …

An Efficient Algorithm For Real-Time Divisible Load Scheduling, Anwar Mamat, Ying Lu, Jitender S. Deogun, Steve Goddard

CSE Technical Reports

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, existing approaches are not very efficient and cannot scale to large clusters. In this paper we propose an efficient algorithm for real-time divisible load scheduling, which has a time complexity linear to the number of tasks and the number of nodes in the cluster.

Network Coding For Wdm All-Optical Multicast, Eric D. Manley, Jitender S. Deogun, Lisong Xu, Dennis R. Alexander

CSE Technical Reports

Network coding has become a useful means for achieving efficient multicast, and the optical community has started to examine its application to optical networks. However, a number of challenges, including limited processing capability and coarse bandwidth granularity, need to be overcome before network coding can be effectively used in optical networks. In this paper, we address some of these problems. We consider the problem of finding efficient routes to use with coding, and we study the effectiveness of using network coding for optical-layer dedicated protection of multicast traffic. We also propose architectures for all-optical circuits capable of performing the processing …

Spa: On-Line Availability Upgrades For Parity-Based Raids Through Supplementary Parity Augmentations, Lei Tian, Hong Jiang, Dan Feng, Qiang Cao, Changsheng Xie, Qin Xin

CSE Technical Reports

In this paper, we propose a simple but powerful on-line availability upgrade mechanism, Supplementary Parity Augmentations (SPA), to address the availability issue for parity-based RAID systems. The basic idea of SPA is to store and update the supplementary parity units on one or a few newly augmented spare disks for on-line RAID systems in the operational mode, thus achieving the goals of improving the reconstruction performance while tole-rating multiple disk failures and latent sector errors simultaneously. By applying the exclusive OR operations appropriately among supplementary parity, full parity and data units, SPA can reconstruct the data on the failed disks …

A Multiagent Framework For Human Coalition Formation, Nobel Khandaker, Leen-Kiat Soh

CSE Technical Reports

Human users form coalitions to solve complex tasks and earn rewards. Examples of such coalition formation can be found in the military, education, and business domains. Multiagent coalition formation techniques cannot be readily used to form human coalitions due to the unique aspects of the human coalition formation problem, e.g., uncertainty in human user behavior and changes in human user behaviors due to human learning. Thus, a multiagent system designed to form human coalitions has to solve a learning problem, that is further made difficult by the limited learning opportunities and usability issues (i.e., actions or decisions being perceived as …

Multiagent Simulation Of Collaboration And Scaffolding Of A Cscl Environment, Nobel Khandaker, Leen-Kiat Soh

CSE Technical Reports

Multiagent techniques improves student learning in Computer-Supported Collaborative Learning (CSCL) environments through multiagent coalition formation and intelligent support to the instructors and students. Researchers designing the multiagent tools and techniques for CSCL environments are often faced with high cost, time, and effort required to investigate the effectiveness of their tools and techniques in large-scale and longitudinal studies in a real-world environment containing human users. Here, we propose SimCoL, a multiagent environment that simulates collaborative learning among students and agents providing support to the teacher and the students. Our goal with SimCoL is to provide a comprehensive testbed for multiagent researchers …

Agent Sensing In Limited Resource Environments, Adam Eck, Leen-Kiat Soh

CSE Technical Reports

One of the key challenges for multiagent systems (MAS) is optimizing performance in limited resource environments. Previous research in this area has focused on the problems of 1) resource allocation and arbitration, and 2) bounded rationality, which describe the relationship between resource constraints and both agent reasoning and actuation. However, less work exists ad-dressing the effect of consuming resources during agent sensing, particularly two important tradeoffs. First, sensing can reduce resource availability, resulting in a tradeoff between overall system performance and an agent’s sensing behavior (the Performance Tradeoff). Second, consuming resources during sensing can alter the outcome of the measurement …

Debar: A Scalable High-Performance De-Duplication Storage System For Backup And Archiving, Tianming Yang, Hong Jiang, Dan Feng, Zhongying Niu

CSE Technical Reports

We present DEBAR, a scalable and high-performance de-duplication storage system for backup and archiving, to overcome the throughput and scalability limitations of the state-of-the-art data de-duplication schemes, including the Data Domain De-duplication File System (DDFS). DEBAR uses a two-phase de-duplication scheme (TPDS) that exploits memory cache and disk index properties to judiciously turn the notoriously random and small disk I/Os of fingerprint lookups and updates into large sequential disk I/Os, hence achieving a very high de-duplication throughput. The salient feature of this approach is that both the system backup and archiving capacity and the de-duplication performance can be dynamically and …

Technical Reports (2004 - 2009)

CSE Technical Reports

Authors of Technical Reports (2005-2009):
Choueiry, Berthe
Cohen, Myra
Deogun, Jitender
Dwyer, Matthew
Elbaum, Sebastian
Goddard, Steve
Henninger, Scott
Jiang, Hong
Lu, Ying
Ramamurthy, Byrav
Rothermel, Gregg
Scott, Stephen
Seth, Sharad
Soh, Leen-Kiat
Srisa-an, Witty
Swanson, David
Variyam, Vinodchandran
Wang, Jun
Xu, Lisong

Exploring Parameterized Relational Consistency, Shant K. Karakashian, Robert J. Woodward, Berthe Y. Choueiry

CSE Technical Reports

Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. For non-binary Constraint Satisfaction Problems (CSPs), the relational-consistency property R(i,j)C of [Dechter and van Beek 1997] may add new non-binary constraints to the constraint network, thus modifying its topology. The domain-filtering properties of [Bessiere et al. 2008] filter the domains of the variables and leave the constraints unchanged but are restricted to combinations of two constraints. We restate the property of m-wise consistency [Gyssens 1986; Jegou 1993] as relational (*,m)-consistency, R(*,m)C. R(*,m)C ensures that any tuple in a relation is consistent in every …