Computer Engineering Commons^™

Opportunistic Checkpoint Intervals To Improve System Performance, Sarala Arunagiri, John T. Daly, Patricia J. Teller, Seetharami Seelam, Ron A. Oldfield, Maria Ruiz Varela, Rolf Riesen

Departmental Technical Reports (CS)

The massive scale of current and next-generation massively parallel processing (MPP) systems presents significant challenges related to fault tolerance. For applications that perform periodic checkpoints, the choice of the checkpoint interval, the period between checkpoints, can have a significant impact on the execution time of the application. Finding the optimal checkpoint interval that minimizes the wall clock execution time, has been a subject of research over the last decade. In an environment where there are concurrent applications competing for access to the network and storage resources, in addition to application execution times, contention at these shared resources need to be …

Fast Algorithms For Uncertainty Propagation, And Their Applications To Structural Integrity, Andrzej Pownuk, Jakub Cerveny, Jerald Brady

Departmental Technical Reports (CS)

In many practical situations, we need to know how uncertainty propagates through data processing algorithms, i.e., how the uncertainty in the inputs affects the results of data processing. This problem is important for all types of uncertainty: probabilistic, interval, and fuzzy. From the computational viewpoint, however, this problem is much more complex for interval and fuzzy uncertainty. Therefore, for these types of uncertainty, it is desirable to design faster algorithms.

In this paper, we describe faster algorithms for two practically important situations:

linearization situations, when the approximation errors are small and therefore, the data processing algorithms can be replaced by …

Everything Is A Matter Of Degree: A New Theoretical Justification Of Zadeh's Principle, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main ideas behind fuzzy logic and its applications is that everything is a matter of degree. We are often accustomed to think that every statement about a physical world is true or false -- that an object is either a particle or a wave, that a person is either young or not, either well or ill -- but in reality, we sometimes encounter intermediate situations. In this paper, we show that the existence of such intermediate situations can be theoretically explained -- by a natural assumption that the real world is cognizable.

Towards An Optimal Algorithm For Computing Fixed Points: Dynamical Systems Approach, With Applications To Transportation Engineering, Ruey L. Cheu, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical problems, it is desirable to find an equilibrium. For example, equilibria are important in transportation engineering.

Many urban areas suffer from traffic congestion. Intuitively, it may seem that a road expansion (e.g., the opening of a new road) should always improve the traffic conditions. However, in reality, a new road can actually worsen traffic congestion. It is therefore extremely important that before we start a road expansion project, we first predict the effect of this project on traffic congestion.

When a new road is built, some traffic moves to this road to avoid congestion on the other …

How To Reconcile Physical Theories With The Idea Of Free Will: From Analysis Of A Simple Model To Interval And Fuzzy Approaches, Julio C. Urenda, Olga Kosheleva

Departmental Technical Reports (CS)

Most modern physical theories are formulated in terms of differential equations. As a result, if we know exactly the current state of the world, then this state uniquely determines all the future events -- including our own future behavior. This determination seems to contradict the intuitive notion of a free will, according to which we are free to make decisions -- decisions which cannot be determined based on the past locations and velocities of the elementary particles. In quantum physics, the situation is somewhat better in the sense that we cannot determine the exact behavior, but we can still determine …

Towards More Adequate Representation Of Uncertainty: From Intervals To Set Intervals, With The Possible Addition Of Probabilities And Certainty Degrees, J. T. Yao, Y. Y. Yao, Vladik Kreinovich, Paulo Pinheiro Da Silva, Scott A. Starks, Gang Xiang, H. T. Nguyen

Departmental Technical Reports (CS)

In the ideal case of complete knowledge, for each property Pi (such as "high fever", "headache", etc.), we know the exact set Si of all the objects that satisfy this property. In practice, we usually only have partial knowledge. In this case, we only know the set Si- of all the objects about which we know that Pi holds and the set Si+ about which we know that Pi may hold (i.e., equivalently, that we have not yet excluded the possibility of Pi). This pair of sets is called a set interval.

Based on the knowledge of the original properties, …

Estimating Variance Under Interval And Fuzzy Uncertainty: Parallel Algorithms, Karen Villaverde, Gang Xiang

Departmental Technical Reports (CS)

Traditional data processing in science and engineering starts with computing the basic statistical characteristics such as the population mean E and population variance V. In computing these characteristics, it is usually assumed that the corresponding data values x1,...,xn are known exactly. In many practical situations, we only know intervals [xi-,xi+] that contain the actual (unknown) values of xi or, more generally, a fuzzy number that describes xi. In this case, different possible values of xi lead, in general, to different values of E and V. In such situations, we are interested in producing the intervals of possible values of E …

How To Measure A Degree Of Mismatch Between Probability Models, P-Boxes, Etc.: A Decision-Theory-Motivated Utility-Based Approach, Luc Longpre, Scott Ferson, W. Troy Tucker

Departmental Technical Reports (CS)

Different models can be used to describe real-life phenomena: deterministic, probabilistic, fuzzy, models in which we have interval-valued or fuzzy-valued probabilities, etc. Models are usually not absolutely accurate. It is therefore important to know how accurate is a given model. In other words, it is important to be able to measure a mismatch between the model and the empirical data. In this paper, we describe an approach of measuring this mismatch which is based on the notion of utility, the central notion of utility theory.

We also show that a similar approach can be used to measure the loss of …

Relations Between Interval Computing And Soft Computing, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper starts with a brief reminder of why data processing and knowledge processing are needed in the first place, why interval and fuzzy methods are needed for data and knowledge processing, and which of the possible data and knowledge processing techniques we should use. Then, we explain how these reasonable soft computing techniques are naturally related with interval computing. Finally, we explain the need for interval-valued fuzzy techniques -- techniques which will be used a lot in our future applications -- and how the transition to such techniques is also related to interval computing.

Towards Fast Algorithms For Processing Type-2 Fuzzy Data: Extending Mendel's Algorithms From Interval-Valued To A More General Case, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

It is known that processing of data under general type-1 fuzzy uncertainty can be reduced to the simplest case -- of interval uncertainty: namely, Zadeh's extension principle is equivalent to level-by-level interval computations applied to alpha-cuts of the corresponding fuzzy numbers.

However, type-1 fuzzy numbers may not be the most adequate way of describing uncertainty, because they require that an expert can describe his or her degree of confidence in a statement by an exact value. In practice, it is more reasonable to expect that the expert estimates his or her degree by using imprecise words from natural language -- …

Cahsi Year 2 Evaluation Report: Recruiting, Retaining, And Advancing Hispanics In Computing, Heather Thiry, Sarah Hug, Lecia Barker

Departmental Technical Reports (CS)

No abstract provided.

Applications Of 1-D Versions Of Image Referencing Techniques To Hydrology And To Patient Rehabilitation, Roberto Araiza, Martine Ceberio, Naga Suman Kanagala, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

In this paper, we consider two seemingly unrelated problems: the hydrology problem of relation between groundwater and surface water, and a problem of identification of human gait in neuro-rehabilitation. It turns out that in both problems, we can efficiently use soft computing-motivated algorithms originally developed for image referencing.

Beyond Intervals: Phase Transitions Lead To More General Ranges, Karen Villaverde, Gilbert Ornelas

Departmental Technical Reports (CS)

One of the main tasks of science and engineering is to use the current values of the physical quantities for predicting the future values of the desired quantities. Due to the (inevitable) measurement inaccuracy, we usually know the current values of the physical quantities with interval uncertainty. Traditionally, it is assumed that all the processes are continuous; as a result, the range of possible values of the future quantities is also known with interval uncertainty. However, in many practical situations (such as phase transitions), the dependence of the future values on the current ones becomes discontinuous. We show that in …

Selecting The Most Representative Sample Is Np-Hard: Need For Expert (Fuzzy) Knowledge, J. Esteban Gamez, Francois Modave, Olga Kosheleva

Departmental Technical Reports (CS)

One of the main applications of fuzzy techniques is to formalize the notions of "typical", "representative", etc.

The main idea behind fuzzy techniques is that they formalize expert knowledge expressed by words from natural language.

In this paper, we show that if we do not use this knowledge, i.e., if we only use the data, then selecting the most representative sample becomes a computationally difficult (NP-hard) problem. Thus, the need to find such samples in reasonable time justifies the use of fuzzy techniques.

Extracting Computable Bounds (And Algorithms) From Classical Existence Proofs: Girard Domains Enable Us To Go Beyond Local Compactness, Vladik Kreinovich, Karen Villaverde

Departmental Technical Reports (CS)

In classical mathematics, the existence of a solution is often proven indirectly, non-constructively, without an efficient method for constructing the corresponding object. In many cases, we can extract an algorithm from a classical proof: e.g., when an object is (non-constructively) proven to be unique in a locally compact space (or when there are two such objects with a known lower bound on the distance between them). In many other practical situations, a (seemingly) natural formalization of the corresponding practical problem leads to a non-compact set. In this paper, we show that often, in such situations, we can extract efficient algorithms …

Identification Of Human Gait In Neuro-Rehabilitation: Towards Efficient Algorithms, Naga Suman Kanagala, Martine Ceberio, Thompson Sarkodie-Gyan, Vladik Kreinovich, Roberto Araiza

Departmental Technical Reports (CS)

Many neurological diseases such as stroke, traumatic body injury, spinal cord injury drastically decrease the patient's ability to walk without physical assistance. To re-establish normal gait, patients undergo extensive rehabilitation. At present, rehabilitation requires gait assessment by highly qualified experienced clinicians. To make rehabilitations easier to access and to decrease the rehabilitation cost, it is desirable to automate gait assessment. In precise terms, gait assessment means comparing the recorded patient's gait with a standard (average) gait of healthy people of the same body measurements. One of the problems in this comparison is that patients walk slower; so, to properly compare …

Integrating Random Testing With Constraints For Improved Efficiency And Diversity, Yoonsik Cheon, Antonio Cortes, Martine Ceberio, Gary T. Leavens

Departmental Technical Reports (CS)

Random testing can be fully automated, eliminates subjectiveness in constructing test cases, and increases the diversity of test data. However, randomly generated tests may not satisfy program's assumptions (e.g., method preconditions). While constraint solving can satisfy such assumptions, it does not necessarily generate diverse tests and is hard to apply to large programs. We blend these techniques by extending random testing with constraint solving, improving the efficiency of generating valid test data while preserving diversity. For domains such as objects, we generate input values randomly; however, for values of finite domains such as integers, we represent test data generation as …

A Library-Based Approach To Translating Ocl Constraints To Jml Assertions For Runtime Checking, Carmen Avila, Guillermo Flores, Jr., Yoonsik Cheon

Departmental Technical Reports (CS)

OCL is a formal notation to specify constraints on UML models that cannot otherwise be expressed by diagrammatic notations such as class diagrams. Using OCL one can document detailed design decisions and choices along with the behavior, e.g., class invariants and method pre and postconditions. However, OCL constraints cannot be directly executed and checked at runtime by an implementation, thus constraint violations may not be detected or noticed, causing many potential development and maintenance problems. In this paper we propose an approach to checking OCL constraints at runtime by translating them to executable JML assertions. The key components of our …

Identifying And Explaining Map Quality Through Provenance: A User Study, Nicholas Ricky Del Rio, Paulo Pinheiro Da Silva

Departmental Technical Reports (CS)

Applications deployed on cyber-infrastructures often rely on multiple data sources and distributed compute resources to access, process, and derive results. When application results are maps, it is possible that non-intentional imperfections can get introduced into the map generation processes because of several reasons including the use of low quality datasets, use of data filtering techniques incompatible for the kind of map to be generated, or even the use of inappropriate mapping parameters, e.g., low-resolution gridding parameters. Without some means for accessing and visualizing the provenance associated with map generation processes, i.e., metadata about information sources and methods used to derive …

Equidecomposability (Scissors Congruence) Of Polyhedra In R^3 And R^4 Is Algorithmically Decidable: Hilbert's 3rd Problem Revisited, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Computational Complexity Of Determining Which Statements About Causality Hold In Different Space-Time Models, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

Causality is one of the most fundamental notions of physics. It is therefore important to be able to decide which statements about causality are correct in different models of space-time. In this paper, we analyze the computational complexity of the corresponding deciding problems. In particular, we show that: for Minkowski space-time, the deciding problem is as difficult as the Tarski's decision problem for elementary geometry, while for a natural model of primordial space-time, the corresponding decision problem is of the lowest possible complexity among all possible spacetime models.

Interval Computations And Interval-Related Statistical Techniques: Tools For Estimating Uncertainty Of The Results Of Data Processing And Indirect Measurements, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we only know the upper bound D on the (absolute value of the) measurement error d, i.e., we only know that the measurement error is located on the interval [-D,D]. The traditional engineering approach to such situations is to assume that d is uniformly distributed on [-D,D], and to use the corresponding statistical techniques. In some situations, however, this approach underestimates the error of indirect measurements. It is therefore desirable to directly process this interval uncertainty. Such "interval computations" methods have been developed since the 1950s. In this chapter, we provide a brief overview of related …

Reasons Why Mobile Telephone Conversations May Be Annoying: Considerations And Pilot Studies, Nigel Ward, Anais G. Rivera, Alejandro Vega

Departmental Technical Reports (CS)

Mobile telephone conversations in public places are often annoying to bystanders. Previous work has focused on the psychological and social causes for this, but has not examined the possible role of properties of the communication channel. In our paper "Do Bystanders and Dialog Participants Differ in Preferences for Telecommunications Channels?" (21st International Symposium on Human Factors in Telecommunication, 2008) we consider the possibility that a reason for the annoyance could be that bystander preferences differ from talker preferences, but conclude that this is in fact unlikely to be a major factor. This technical report provides supplemental information, specifically a broader …

Computing Population Variance And Entropy Under Interval Uncertainty: Linear-Time Algorithms, Gang Xiang, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In statistical analysis of measurement results, it is often necessary to compute the range [V-,V+] of the population variance V=((x1-E)^2+...+(xn-E)^2)/n (where E=(x1+...+xn)/n) when we only know the intervals [Xi-Di,Xi+Di] of possible values of the xi. While V- can be computed efficiently, the problem of computing V+ is, in general, NP-hard. In our previous paper "Population Variance under Interval Uncertainty: A New Algorithm" (Reliable Computing, 2006, Vol. 12, No. 4, pp. 273-280), we showed that in a practically important case, we can use constraints techniques to compute V+ in time O(n*log(n)). In this paper, we provide new algorithms that compute V- …

Propagation And Provenance Of Probabilistic And Interval Uncertainty In Cyberinfrastructure-Related Data Processing And Data Fusion, Paulo Pinheiro Da Silva, Aaron A. Velasco, Martine Ceberio, Christian Servin, Matthew G. Averill, Nicholas Ricky Del Rio, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

In the past, communications were much slower than computations. As a result, researchers and practitioners collected different data into huge databases located at a single location such as NASA and US Geological Survey. At present, communications are so much faster that it is possible to keep different databases at different locations, and automatically select, transform, and collect relevant data when necessary. The corresponding cyberinfrastructure is actively used in many applications. It drastically enhances scientists' ability to discover, reuse and combine a large number of resources, e.g., data and services.

Because of this importance, it is desirable to be able to …

Statistical Hypothesis Testing Under Interval Uncertainty: An Overview, Vladik Kreinovich, Hung T. Nguyen, Sa-Aat Niwitpong

Departmental Technical Reports (CS)

An important part of statistical data analysis is hypothesis testing. For example, we know the probability distribution of the characteristics corresponding to a certain disease, we have the values of the characteristics describing a patient, and we must make a conclusion whether this patient has this disease. Traditional hypothesis testing techniques are based on the assumption that we know the exact values of the characteristic(s) x describing a patient. In practice, the value X comes from measurements and is, thus, only known with uncertainty: X =/= x. In many practical situations, we only know the upper bound D on the …

A Fitness Function To Find Feasible Sequences Of Method Calls For Evolutionary Testing Of Object-Oriented Programs, Myoung Yee Kim, Yoonsik Cheon

Departmental Technical Reports (CS)

In evolutionary testing of an object-oriented program, the search objective is to find a sequence of method calls that can successfully produce a test object of an interesting state. This is challenging because not all call sequences are feasible; each call of a sequence has to meet the assumption of the called method. The effectiveness of an evolutionary testing thus depends in part on the quality of the so-called fitness function that determines the degree of the fitness of a candidate solution. In this paper, we propose a new fitness function based on assertions such as method preconditions to find …

How To Estimate, Take Into Account, And Improve Travel Time Reliability In Transportation Networks, Ruey L. Cheu, Vladik Kreinovich, Francois Modave, Gang Xiang, Tao Li, Tanja Magoc

Departmental Technical Reports (CS)

Many urban areas suffer from traffic congestion. Intuitively, it may seem that a road expansion (e.g., the opening of a new road) should always improve the traffic conditions. However, in reality, a new road can actually worsen traffic congestion. It is therefore extremely important that before we start a road expansion project, we first predict the effect of this project on traffic congestion.

Traditional approach to this prediction is based on the assumption that for any time of the day, we know the exact amount of traffic that needs to go from each origin city zone A to every …

Usability Inspection Methods After 15 Years Of Research And Practice, David G. Novick, Tasha Hollingsed

Departmental Papers (CS)

Usability inspection methods, such as heuristic evaluation, the cognitive walkthrough, formal usability inspections, and the pluralistic usability walkthrough, were introduced fifteen years ago. Since then, these methods, analyses of their comparative effectiveness, and their use have evolved in different ways. In this paper, we track the fortunes of the methods and analyses, looking at which led to use and to further research, and which led to relative methodological dead ends. Heuristic evaluation and the cognitive walkthrough appear to be the most actively used and researched techniques. The pluralistic walkthrough remains a recognized technique, although not the subject of significant further …

Toward A More Accurate View Of When And How People Seek Help With Computer Applications, David G. Novick, Edith Elizalde, Nathaniel Bean

Departmental Papers (CS)

Based on 40 interviews and 11 on-site workplace observations of people using computer applications at work, we confirm that use of printed and on-line help is very low and find that providing greater detail of categories solution methods can present a more realistic picture of users’ behaviors. Observed study participants encountered a usability problem on average about once every 75 minutes and typically spent about a minute looking for a solution. Participants consumed much more time when they were unaware of a direct way of doing something and instead used less effective methods. Comparison of results from different data-collection methods …