The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file. Title from PDF of title page (University of Missouri--Columbia, viewed on November 18, 2009). Thesis advisor: Dr. Roger Fales. Includes bibliographical references.

Thesis: M.S., Massachusetts Institute of Technology, Department of Civil Engineering, 1979 / Bibliography: leaves 113-116. / by Avraham Arie Szwarcbard. / M.S. / M.S. Massachusetts Institute of Technology, Department of Civil Engineering

Reasoning with uncertainty in real complex problems is expected to be increasingly difficult as the need for participation by the experts increases. The Eigen Vector Method (EVM) is a simple technique to quantify personal assessment of uncertain situations. It, however, provides only point estimates and lacks a direct measure of accuracy. The proposed method of Confidence Interval Based Uncertainty Evaluation Technique (CIBUET) explores a method to estimate the variability along with point estimates. A brief review of uncertainty evaluation techniques, the basics of decision theory as a framework for analyzing preferences, and the method of EVM to estimate the priorities are presented. The variance of these point estimates result from the inconsistency in the judgement ratios, which is represented by introducing error factors with each judgement ratio. The nature of the error factors are discussed, and then modelled as lognormally distributed. Methods to estimate the parameters of the error factors and the variances of the priorities are developed. These results are corroborated by numerical simulation. The framework for several applications of the technique is presented. It is illustrated by analyzing a number of example problems taken from the literature. The methodology to extend the technique to analyze inconsistent data encountered in the process of power planning is developed in detail. The application is fully illustrated using the context and data from an actual power planning study. Several approaches taken to extend the technique to multi-level hierarchies are presented. Numerical simulation is utilized to investigate the validity of the approaches and select the most appropriate model. Some special features of the technique and the underlying assumptions with the subsequent implications are discussed at the end. Directions for further research to enhance and extend the technique are identified and some possible approaches for the same are outlined. / Ph. D.

In this thesis, we explore the issues of uncertain data management in several different aspects. First, we propose a novel linear time algorithm to compute the positional probability, the computation of which is a primitive operator for most of the ranking definitions. Our algorithm is based on the conditional probability formulation of positional probability and the system of linear equations. Based on the formulation of conditional probability, we also prove a tight upper bound of the top-k probability of tuples, which is then used to stop the top-k computation earlier. Second, we study top-k probabilistic ranking queries with joins when scores and probabilities are stored in different relations. We focus on reducing the join cost in probabilistic top-k ranking. We investigate two probabilistic score functions, namely, expected rank value and probability of highest ranking. We give upper/lower bounds of such probabilistic score functions in random access and sequential access, and propose new I/O efficient algorithms to find top-k objects. Third, we extend the possible worlds semantics to probabilistic XML ranking query, which is to rank top-k probabilities of the answers of a twig query in probabilistic XML data. The new challenge is how to compute top-k probabilities of answers of a twig query in probabilistic XML in the presence of containment (ancestor/descendant) relationships. We focus on node queries first, and propose a new dynamic programming algorithm which can compute top-k probabilities for the answers of node queries based on the previously computed results in probabilistic XML data. We further propose optimization techniques to share the computational cost. We also show techniques to support path queries and tree queries. Fourth, we study how to rank documents using a set of keywords, given a context that is associated with the documents. We model the problem using a graph with two different kinds of nodes (document nodes and multi-attribute nodes), where the edges between document nodes and multi-attribute nodes exist with some probability. We discuss its score function, cost function, and ranking with uncertainty. We also propose new algorithms to rank documents that are most related to the user-given keywords by integrating the context information. / Uncertain data management has received a lot of attentions recently due to the fact that data obtained can be incomplete or uncertain in many real applications. Ranking of uncertain data becomes an important research issue, the possible worlds semantics-based ranking makes it different from the ranking of deterministic data. In the traditional deterministic data, we can compute a score for each object, and then the objects are ranked based on the computed scores. However, in the scenario of uncertain data, each object has a probability to be the true answer (or the existence probability), besides the computed score. A probabilistic top-k ranking query ranks objects by the interplay of score and probability based on the possible worlds semantics. Many definitions have been proposed in the literature based on the possible worlds semantics. / Chang, Lijun. / Advisers: Hong Cheng; Jeffrey Xu Yu. / Source: Dissertation Abstracts International, Volume: 73-06, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 131-139). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Yuen, Sze Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves [44]-46). / Abstract also in Chinese. / Thesis Committee --- p.i / Abstract --- p.ii / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Related Work --- p.6 / Chapter 2.1 --- Nearest Neighbor Search on Precise Data --- p.6 / Chapter 2.2 --- NN Search on Uncertain Data --- p.8 / Chapter 3 --- Problem Definitions and Basic Characteristics --- p.11 / Chapter 4 --- The Full-Graph Approach --- p.16 / Chapter 5 --- The Pipeline Approach --- p.19 / Chapter 5.1 --- The Algorithm --- p.20 / Chapter 5.2 --- Edge Phase --- p.24 / Chapter 5.3 --- Pruning Phase --- p.27 / Chapter 5.4 --- Validating Phase --- p.28 / Chapter 5.5 --- Discussion --- p.29 / Chapter 6 --- Extension --- p.31 / Chapter 7 --- Experiment --- p.34 / Chapter 7.1 --- Properties of the SNN-core --- p.34 / Chapter 7.2 --- Efficiency of Our Algorithms --- p.38 / Chapter 8 --- Conclusions and Future Work --- p.42 / Chapter A --- List of Publications --- p.43 / Bibliography --- p.44

Solving optimization problems under uncertainty has been an important topic since the appearance of mathematical optimization in the mid 19th century. George Dantzig’s 1955 paper, “Linear Programming under Uncertainty” is considered one of the ten most influential papers in Management Science [26]. The methodology introduced in Dantzig’s paper is named stochastic programming, since it assumes an underlying probability distribution of the uncertain input parameters. However, stochastic programming suffers from the “curse of dimensionality”, and knowing the exact distribution of the input parameter may not be realistic. On the other hand, robust optimization models the uncertainty using a deterministic uncertainty set. The goal is to optimize the worst-case scenario from the uncertainty set. In recent years, many studies in robust optimization have been conducted and we refer the reader to Ben-Tal and Nemirovski [4–6], El Ghaoui and Lebret [19], Bertsimas and Sim [15, 16], Goldfarb and Iyengar [23], Bertsimas et al. [8] for a review of robust optimization. Computing an optimal adjustable (or dynamic) solution to a robust optimization problem is generally hard. This motivates us to study the hardness of approximation of the problem and provide efficient approximation algorithms. In this dissertation, we consider adjustable robust linear optimization problems with packing and covering formulations and their approximation algorithms. In particular, we study the performances of static solution and affine solution as approximations for the adjustable robust problem. Chapter 2 and 3 consider two-stage adjustable robust linear packing problem with uncertain second-stage constraint coefficients. For general convex, compact and down-monotone uncertainty sets, the problem is often intractable since it requires to compute a solution for all possible realizations of uncertain parameters [22]. In particular, for a fairly general class of uncertainty sets, we show that the two-stage adjustable robust problem is NP-hard to approximate within a factor that is better than Ω(logn), where n is the number of columns of the uncertain coefficient matrix. On the other hand, a static solution is a single (here and now) solution that is feasible for all possible realizations of the uncertain parameters and can be computed efficiently. We study the performance of static solutions an approximation for the adjustable robust problem and relate its optimality to a transformation of the uncertain set. With this transformation, we show that for a fairly general class of uncertainty sets, static solution is optimal for the adjustable robust problem. This is surprising since the static solution is widely perceived as highly conservative. Moreover, when the static solution is not optimal, we provide an instance-based tight approximation bound that is related to a measure of non-convexity of the transformation of the uncertain set. We also show that for two-stage problems, our bound is at least as good (and in many case significantly better) as the bound given by the symmetry of the uncertainty set [11, 12]. Moreover, our results can be generalized to the case where the objective coefficients and right-hand-side are also uncertainty. In Chapter 3, we focus on the two-stage problems with a family of column-wise and constraint-wise uncertainty sets where any constraint describing the set involves entries of only a single column or a single row. This is a fairly general class of uncertainty sets to model constraint coefficient uncertainty. Moreover, it is the family of uncertainty sets that gives the previous hardness result. On the positive side, we show that a static solution is an O(\log n · min(\log \Gamma, \log(m+n))-approximation for the two-stage adjustable robust problem where m and n denote the numbers of rows and columns of the constraint matrix and \Gamma is the maximum possible ratio of upper bounds of the uncertain constraint coefficients. Therefore, for constant \Gamma, surprisingly the performance bound for static solutions matches the hardness of approximation for the adjustable problem. Furthermore, in general the static solution provides nearly the best efficient approximation for the two-stage adjustable robust problem. In Chapter 4, we extend our result in Chapter 2 to a multi-stage adjustable robust linear optimization problem. In particular, we consider the case where the choice of the uncertain constraint coefficient matrix for each stage is independent of the others. In real world applications, decision problems are often of multiple stages and a iterative implementation of two-stage solution may result in a suboptimal solution for multi-stage problem. We consider the static solution for the adjustable robust problem and the transformation of the uncertainty sets introduced in Chapter 2. We show that the static solution is optimal for the adjustable robust problem when the transformation of the uncertainty set for each stage is convex. Chapters 5 considers a two-stage adjustable robust linear covering problem with uncertain right-hand-side parameter. As mentioned earlier, such problems are often intractable due to astronomically many extreme points of the uncertainty set. We introduce a new approximation framework where we consider a “simple” set that is “close” to the original uncertainty set. Moreover, the adjustable robust problem can be solved efficiently over the extended set. We show that the approximation bound is related to a geometric factor that represents the Banach-Mazur distance between the two sets. Using this framework, we provide approximation bounds that are better than the bounds given by an affine policy in [7] for a large class of interesting uncertainty sets. For instance, we provide an approximation solution that gives a m^{1/4}-approximation for the two-stage adjustable robust problem with hypersphere uncertainty set, while the affine policy has an approximation ratio of O(\sqrt{m}). Moreover, our bound for general p-norm ball is m^{\frac{p-1}{p^2}} as opposed to m^{1/p} as given by an affine policy.

Skyline analysis is important for multi-criteria decision making applications. The data in some of these applications are inherently uncertain due to various factors. Although a considerable amount of research has been dedicated separately to efficient skyline computation, as well as modeling uncertain data and answering some types of queries on uncertain data, how to conduct skyline analysis on uncertain data remains an open problem at large. In this thesis, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all the objects whose skyline probabilities are at least p. Computing probabilistic skylines on large uncertain data sets is challenging. An uncertain object is conceptually described by a probability density function (PDF) in the continuous case, or in the discrete case a set of instances (points) such that each instance has a probability to appear. We develop two efficient algorithms, the bottom-up and top-down algorithms, of computing p-skyline of a set of uncertain objects in the discrete case. We also discuss that our techniques can be applied to the continuous case as well. The bottom-up algorithm computes the skyline probabilities of some selected instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show that probabilistic skylines are interesting and useful, and our two algorithms are efficient on large data sets, and complementary to each other in performance.

Skyline analysis is important for multi-criteria decision making applications. The data in some of these applications are inherently uncertain due to various factors. Although a considerable amount of research has been dedicated separately to efficient skyline computation, as well as modeling uncertain data and answering some types of queries on uncertain data, how to conduct skyline analysis on uncertain data remains an open problem at large. In this thesis, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all the objects whose skyline probabilities are at least p. Computing probabilistic skylines on large uncertain data sets is challenging. An uncertain object is conceptually described by a probability density function (PDF) in the continuous case, or in the discrete case a set of instances (points) such that each instance has a probability to appear. We develop two efficient algorithms, the bottom-up and top-down algorithms, of computing p-skyline of a set of uncertain objects in the discrete case. We also discuss that our techniques can be applied to the continuous case as well. The bottom-up algorithm computes the skyline probabilities of some selected instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show that probabilistic skylines are interesting and useful, and our two algorithms are efficient on large data sets, and complementary to each other in performance.

Graduation date: 2005

The Lyapunov direct method is utilized to determine the robustness bounds for nonlinear, time-variant uncertainies p[subscript i]. Determination of the robustness bounds consists of two principal steps: (i) generation of a Lyapunov function and (ii) determination of the bounds based on the generated Lyapunov function. Presently in robustness investigations, a Lyapunov function is generated by inserting the nominal matrix to the Lyapunov equation and setting Q as identity matrix. The objective of this study is to utilize structural features of the uncertainties to develop a recursive algorithm for the generation of the globally optimal quadratic Lyapunov function. The proposed method is seemingly an improvement with respect to those reported in recent literature in three senses: i) ease of application, given an interactive program which requires only system matrices as inputs; ii) provision of improved estimates of the robustness bounds; and iii) extendability of the procedure to the design of robust controllers. The algorithm and the program prepared (in MATLAB) are presented. Several examples are considered for purposes of the comparison of robustness bounds estimates. Examples are demonstrated to show the superiority of the robustness bounds estimated by the proposed method over those obtained by small gain theorem. In a number of cases, the estimated robustness bounds are proven to be the exact robustness bounds. / Graduation date: 1993