Theses & Reports

Instructions for submitting a technical report or thesis.

You can find technical reports published prior to 1990 archived here.

• Ph.D. Thesis 2000 SETL for Internet Data Processing Bacon, David Abstract | PDF

  Title: SETL for Internet Data Processing

  Candidate: Bacon, David

  Advisor(s): Schwartz, Jack

  Abstract:

  Although networks and coordinated processes figure prominently in the kinds of data manipulation found in everything from scientific modeling to large-scale data mining, programmers charged with setting up the requisite software systems frequently find themselves hampered by the inadequacy of available languages. The ``real'' languages such as C++ and Java tend to be low-level, requiring the specification of a great deal of often repetitive detail, whereas the higher-level ``scripting'' languages tend to lack the kinds of structuring facilities that lend themselves to the reliable construction of even modestly large systems.

  The high-level language SETL meets both of these needs. Originally conceived as a language which aimed to bring programming a little closer to the idealized world of mathematics, making it extremely useful in the human-to-human communication of algorithms, SETL has proven itself over the years to be an excellent language for software prototyping, primarily because its conciseness and immediacy lend it well to rapid experimentation. These characteristics, together with its general freedom from machine-oriented restrictions, its value semantics, its comprehension-style constructors for aggregates, its skill with strings, and especially its syntactic support for mappings, also make it well suited to high-level data processing.

  In order to play the role of a full-fledged modern data processing language, however, SETL had to acquire the ability to manipulate processes and communicate with them easily, and furthermore to be able to work with networks, particularly the client-server model that rules the Internet. Accordingly, I have integrated a full set of process and network management features into SETL. In my dissertation, I show how the liberal use of fullweight processes, with the high, protective walls that surround them, sustains a modular design approach which in turn provides a strong defense against the main hazards of distributed computing, namely race conditions and deadlock, while preserving the luxury and convenience of programming in a truly high-level language. To this end, I have evolved protocols and design patterns for developing multiplexing servers and clients in SETL, and in my talk, will present examples of fairly complex systems where hierarchies of processes communicate over the network. Such systems tend to be notorious for their unreliability, but in these instances, robustness seems to follow naturally from the readability of simple programs written in an ancient and friendly language.

• TR2000-802 2000 Continuous Shape Transformation and Metrics on Shapes Davis, Ernest Abstract | PDF

  Title: Continuous Shape Transformation and Metrics on Shapes

  Author(s): Davis, Ernest

  Abstract:

  A natural approach to defining continuous change of shape is in terms of a metric that measures the difference between two regions. We consider four such metrics over regions: the Hausdorff distance, the dual-Hausdorff distance, the area of the symmetric difference, and the optimal-homeomorphism metric. Each of these gives a different criterion for continuous change. We establish qualitative properties of all of these; in particular, the continuity of basic functions such as union, intersection, set difference, area, distance, and the boundary function; the transition graph between RCC relations (Randell, Cui, and Cohn, 1992). We discuss the physical significance of these different criteria.

  We also show that the history-based definition of continuity proposed by Muller (1998) is equivalent to continuity with respect to the Hausdorff distance. An examination of the difference between the transition rules that we have found for the Hausdorff distance and the transition theorems that Muller derives leads to the conclusion that Muller's analysis of state transitions is not adequate. We propose an alternative characterization of transitions in Muller's first-order language over histories.

• TR2000-809 2000 Describing Spatial Transitions Using Mereotopological Relations Over Histories Davis, Ernest Abstract | PDF

  Title: Describing Spatial Transitions Using Mereotopological Relations Over Histories

  Author(s): Davis, Ernest

  Abstract:

  Muller (1998) develops a language of motion and shape change in terms of topological relations and temporal order relations between regions of space-time (histories). He uses this language to state and prove the transition rules developed in (Randell, Cui, and Cohn, 1992) that constrain the changes in spatial relations possible for objects whose shape changes continuously. Unfortunately, Muller's statement of the transition rules is inadequate. This paper presents an alternative statement of these transition rules.

• Ph.D. Thesis 2000 A Rigorous Framework for Fully Supporting the IEEE Standard for Floating-Point Arithmetic in High-Level Programming Languages Figueroa, Sam Abstract | PDF

  Title: A Rigorous Framework for Fully Supporting the IEEE Standard for Floating-Point Arithmetic in High-Level Programming Languages

  Candidate: Figueroa, Sam

  Advisor(s): Dewar, Robert

  Abstract:

  Processors conforming to the IEEE Standard for Floating-Point Arithmetic have been commonplace for some years, and now several programming languages seem to support or conform to this standard, from hereon referred to as ``the IEEE Standard.'' For example, The Java Language Specification by Gosling, Joy, and Steele, which defines the Java language, frequently mentions the IEEE Standard. Indeed, Java, as do other languages, supports some of the features of the IEEE Standard, including a couple floating-point data formats, and even requires (in section 4.2.4 ``Floating-Point Operations'' of the aforementioned book) that ``operators on floating-point numbers behave exactly as specified by IEEE 754.''

  Arguing that the support current languages offer is not enough, this thesis establishes clear criteria for what it means to fully support the IEEE Standard in a programming language. Each aspect of the IEEE Standard is examined in detail from the point of view of how various arithmetic engines implement that aspect of the IEEE Standard, how different languages (and implementations thereof) support it, and what the range of options are in supporting that aspect. Practical recommendations are then offered (particularly, but not exclusively, for Ada and Java), taking, for example, programmer convenience and impact on performance into consideration. A detailed model specification following these recommendations is provided for the Ada language.

  In addition, a variety of issues related to the floating-point aspects of programming languages are discussed, so as to serve as a more complete guide to language designers. One such issue is floating-point expression evaluation schemes, and, more specifically, whether bit-for-bit identical results are actually achievable on a variety of platforms that conform to the IEEE Standard, as the Java language promises. Closely tied to this issue is that of double rounding, which occurs when a (possibly intermediate) result is rounded more than once before subsequent use or before being delivered to its final destination. So this thesis discusses when double rounding makes a difference, how it can be avoided, and what the performance impact is in avoiding it.

• TR2000-808 2000 CANS: Composable, Adaptive Network Services Infrastructure Fu, Xiaodong; Shi, Weisong; Akkerman, Anatoly; Karamcheti, Vijay Abstract | PDF

  Title: CANS: Composable, Adaptive Network Services Infrastructure

  Author(s): Fu, Xiaodong; Shi, Weisong; Akkerman, Anatoly; Karamcheti, Vijay

  Abstract:

  The growth of the internet has been fueled by an increasing number of sophisticated network-accessible services. Unfortunately, the high bandwidth and processing requirements of such services is at odds with current trends towards increased variation in network characteristics and a large diversity in end devices. Ubiquitous access to sucr services requires the injection of additional functionality into the network to handle protocol conversion, data transcoding, and in general bridge disparate portions of the physical network. Several researchers have proposed infrastructures for injecting such functionality; however, many challenges remain before these infrastructures can be widely deployed.

  CANS is an application-level infrastructure for injecting application-specific components into the network that focuses on three such challenges: (a) efficient and dynamic composition of individual components; (b) dynamic and distributed adaptation of injected components in response to system conditions; and (c) support for legacy applications and services. The network view supported by CANS consists of applications, stateful services, and data paths between them built up from mobile soft-state objects called drivers. Both services and data paths can be dynamically created and reconfigured: a planning and event propagation model assists in distributed adaptation, and a run-time type-based composition model dictates how new services and drivers are integrated with existing components. An interception layer that virtualizes network bindings permits legacy applications to plug into the CANS infrastructure, and a delegation model does the same for legacy services.

  This paper describes the CANS architecture and implementation, and a case study involving a shrink-wrapped client application in a dynamically changing network environment where CANS was used to improve overall user experience.

• Ph.D. Thesis 2000 A Language-Theoretic Approach to Algorithms Goyal, Deepak Abstract | PDF

  Title: A Language-Theoretic Approach to Algorithms

  Candidate: Goyal, Deepak

  Advisor(s): Paige, Bob

  Abstract:

  An effective algorithm design language should be 1) wide-spectrum in nature, i.e. capable of expressing both abstract specifications and low-level implementations, and 2) "computationally transparent", i.e. facilitate accurate estimation of time and space requirements. The conflict between these requirements is exemplified by SETL which is wide-spectrum, but lacks computational transparency because of its reliance on hash-based data structures. The first part of this thesis develops an effective algorithm design language, and the second demonstrates its usefulness for algorithm explanation and discovery.

  In the first part three successively more abstract set-theoretic languages are developed and shown to be computationally transparent. These languages can collectively express both abstract specifications and low-level implementations. We formally define a data structure selection method for these languages using a novel type system. Computational transparency is obtained for the lowest-level language through the type system, and for the higher-level languages by transformation into the next lower level. We show the effectiveness of this method by using it to improve a difficult database query optimization algorithm from expected to worst-case linear time. In addition, a simpler explanation and a shorter proof of correctness are obtained.

  In the second part we show how our data structure selection method can be made an effective third component of a transformational program design methodology whose first two components are finite differencing and dominated convergence. Finite differencing replaces costly repeated computations by cheaper incremental counterparts, and dominated convergence provides a generalized iteration scheme for computing fixed-points. This methodology has led us to a simpler explanation of a complex linear-time model-checking algorithm for the alternation-free modal mu-calculus, and to the discovery of an O ( N ³ ) time algorithm for computing intra-procedural may-alias information that improves over an existing O ( N ⁵ ) time algorithm.

• TR2000-801 2000 Paint By Relaxation Hertzmann, Aaron Abstract | PDF

  Title: Paint By Relaxation

  Author(s): Hertzmann, Aaron

  Abstract:

  We use relaxation to produce painted imagery from images and video. An energy function is first specified; a painting is then generated by performing a search for a painting with minimal energy. The appeal of this strategy is that, ideally, we need only specify what we want, not how to directly compute it. Because the energy function is very difficult to optimize, we use a relaxation algorithm combined with various search heuristics.

  This formulation allows us to specify painting style by varying the relative weights of energy terms. The basic energy function yields an economical painting that effectively conveys an image with few strokes. This economical style produces moderate temporal coherence when processing video, without losing the essential 2D quality of the painting. The system allows as fine user control as desired: the user may interac-tively change the painting style, specify variations of style over an image, and/or add specific strokes to the painting. Procedural stroke textures may be used to enhance visual appeal.

• Ph.D. Thesis 2000 Supporting a Flexible Parallel Programming Model on a Network of Non-Dedicated Workstations Huang, Shih-Chen Abstract | PDF

  Title: Supporting a Flexible Parallel Programming Model on a Network of Non-Dedicated Workstations

  Candidate: Huang, Shih-Chen

  Advisor(s): Kedem, Zvi

  Abstract:

  A network of non-dedicated workstations can provide computational resources at minimal or no additional cost. If harnessed properly, the combined computational power of these otherwise ``wasted'' resources can outperform even mainframe computers. Performing demanding computations on a network of non-dedicated workstations efficiently has previously been studied, but inadequate handling of the unpredictable behavior of the environment and possible failures resulted in limited success only.

  This dissertation presents a shared memory software system for executing programs with nested parallelism and synchronization on a network of non-dedicated workstations. The programming model exhibits a very convenient and natural programming style and is especially suitable for computations whose complexity and parallelism emerges only during their execution, such as in divide and conquer problems. To both support and take advantage of the flexibility inherent in the programming model, an architecture that distributes both the shared memory management and the computation is developed. This architecture removes bottlenecks inherent in centralization, thus enhancing scalability and dependability. By adapting available resource dynamically and coping with unpredictable machine slowdowns and failures, the system also supports dynamic load balancing, and fault tolerance--both transparently to the programmer.

• Ph.D. Thesis 2000 Global Optimization Using Embedded Graphs Ishikawa, Hiroshi Abstract | PDF

  Title: Global Optimization Using Embedded Graphs

  Candidate: Ishikawa, Hiroshi

  Advisor(s): Geiger, Davi

  Abstract:

  One of the challenges of computer vision is that the information we seek to extract from images is not even defined for most images. Because of this, we cannot hope to find a simple process that produces the information directly from a given image. Instead, we need a search, or an optimization, in the space of parameters that we are trying to estimate.

  In this thesis, I introduce two new optimization methods that use graph algorithms. They are characterized by their ability to find a global optimum efficiently. Each method defines a graph that can be seen as embedded in a Euclidean space. Graph- theoretic entities such as cuts and cycles represent geometric objects that embody the information we seek.

  The first method finds a hypersurface in a Euclidean space that minimizes a certain kind of energy functional. The hypersurface is approximated by a cut of an embedded graph so that the total cost of the cut corresponds to the energy. A globally optimal solution is found by using a minimum cut algorithm. In particular, it can globally solve first order Markov Random Field problems in more generality than was previously possible. I prove that the convexity of the smoothing function in the energy is essential for the applicability of the method and provide an exact criterion in terms of the MRF energy.

  The second method proposed here efficiently finds an optimal cycle in a Euclidean space. It uses a minimum ratio cycle algorithm to find a cycle with minimum energy in an embedded graph. In the case of two dimensions, the energy can depend not only on the cycle itself but also on the region defined by the cycle. Because of this, the method unifies the two competing views of boundary and region segmentation.

  I demonstrate the utility of the methods in applications, with the results of experiments in the areas of binocular stereo, image restoration, and image segmentation. The image segmentation, or contour extraction, experiments are carried out in various situations using different types of information, for example motion, stereo, and intensity.

• Ph.D. Thesis 2000 On the Use of Functionals on Boundaries in Hierarchical Models of Object Recognition Jermyn, Ian Abstract | PDF

  Title: On the Use of Functionals on Boundaries in Hierarchical Models of Object Recognition

  Candidate: Jermyn, Ian

  Advisor(s): Geiger, Davi

  Abstract:

  Object recognition is a central problem in computer vision. Typically it is assumed to follow a sequential model in which successively more specific hypotheses are generated about the image. This is a rather simplistic model, allowing as it does no margin for error at any point. We follow a more general approach in which the various representations involved are allowed to influence one another from the outset. As a guide and ultimate goal, we study the problem of finding the region occupied by human beings in images, and the separation of the region into arms, legs and head. We approach the problem as that of defining a functional on the space of boundaries in images whose minimum specifies the region occupied by the human figure. Previous work that uses such functionals suffers from a number of difficulties. These include an uncontrollable dependence on scale, an inability to find the global minimum for boundaries in polynomial time, and the inability to include region as well as boundary information. We present a new form of functional on boundaries in a manifold that solves these problems, and is also the unique form of functional in a specific class that possesses a non-trivial, efficiently computable global minimum. We describe applications of the model to single images and to the extraction of boundaries from stereo pairs and motion sequences. In addition, the functionals used in previous work could not include information about the shape of the region sought. We develop a model for the part structures of boundaries that extends previous work to the case of real images, thus including shape information in the functional framework. We show that such part structures are hyperpaths in a hypergraph. An `optimal hyperpath' algorithm is developed that globally minimizes the functional under some conditions. We show how to use exemplars of a shape to construct a functional that includes specific information about the topology of the part structure sought. An algorithm is developed that globally minimizes such functionals in the case of a fixed boundary. The behaviour of the functional mimics an aspect of human shape comparison.

   

• TR2000-803 2000 Verifying a Design Pattern for the Fault-Tolerant Execution of Parallel Programs Kindler, Ekkart; Shasha, Dennis Abstract | PDF

  Title: Verifying a Design Pattern for the Fault-Tolerant Execution of Parallel Programs

  Author(s): Kindler, Ekkart; Shasha, Dennis

  Abstract:

  We present a protocol for the fault-tolerant execution of parallel programs. The protocol leaves the implementation free to make choices concerning efficiency tradeoffs. Thus, we are proposing a design pattern rather than a fully specified algorithm. The protocol is modeled with the help of Petri nets.

  Based on the Petri net model, we formally prove the correctness of the design pattern. This verification serves two goals: first, it guarantees the correctness of the design pattern; second, it serves as a test case for the underlying verification technique.

• TR2000-810 2000 An Overlapping Domain Decomposition Preconditioner for a Class of Discontinuous Galerkin Approximations of Advection-Diffusion Problems Lasser, Caroline; Toselli, Andrea Abstract | PDF

  Title: An Overlapping Domain Decomposition Preconditioner for a Class of Discontinuous Galerkin Approximations of Advection-Diffusion Problems

  Author(s): Lasser, Caroline; Toselli, Andrea

  Abstract:

  We consider a scalar advection-diffusion problem and a recently proposed discontinuous Galerkin approximation, which employs discontinuous finite element spaces and suitable bilinear forms containing interface terms that ensure consistency. For the corresponding sparse, non-symmetric linear system, we propose and study an additive, two--level overlapping Schwarz preconditioner, consisting of a coarse problem on a coarse triangulation and local solvers associated to suitable problems defined on a family of subdomains.

  This is a generalization of the corresponding overlapping method for approximations on continuous finite element spaces. Related to the lack of continuity of our approximation spaces, some interesting new features arise in our generalization, which have no analog in the conforming case.

  We prove an upper bound for the number of iterations obtained by using this preconditioner with GMRES, which is independent of the number of degrees of freedom of the original problem and the number of subdomains. The performance of the method is illustrated by several numerical experiments for different test problems, using linear finite elements in two dimensions.

• Ph.D. Thesis 2000 Delegation Logic: A Logic-based Approach to Distrbuted Authorization Li, Ninghui Abstract | PDF

  Title: Delegation Logic: A Logic-based Approach to Distrbuted Authorization

  Candidate: Li, Ninghui

  Advisor(s): Feigenbaum, Joan; Siegel, Alan

  Abstract:

  We address the problem of authorization in large-scale, open, distributed systems. Authorization decisions are needed in electronic commerce, mobile-code execution, remote resource sharing, content advising, privacy protection, etc. We adopt the trustmanagement approach, in which “authorization” is viewed as a “proof-of-compliance” problem: Does a set of credentials prove that a request complies with a policy? We develop a logic-based language Delegation Logic (DL) to represent policies, credentials, and requests in distributed authorization. Delegation Logic extends logic programming (LP) languages with expressive delegation constructs that feature delegation depth and a wide variety of complex principals (including, but not limited to, k-out-of-n thresholds). D1LP, the monotonic version of DL, extends the LP language Datalog with delegation constructs. D2LP, the nonmonotonic version of DL, also features classical negation, negation-as-failure, and prioritized conflict handling. Our approach to defining and implementing DL is based on tractably compiling DL programs into ordinary logic programs (OLP’s). This compilation approach enables DL to be implemented modularly on top of existing technologies for OLP, e.g., Prolog. As a trust-management language, Delegation Logic provides a concept of proof-ofcompliance that is founded on well-understood principles of logic programming and knowledge representation. DL also provides a logical framework for studying delegation, negation of authority, conflicts between authorities, and their interplay.

• TR2000-798 2000 Local Names in SPKI/SDSI 2.0 Li, Ninghui Abstract | PDF
• TR2000-799 2000 Variational Analysis of the Abscissa Mapping for Polynomials Overton, Michael; Burke, James V. Abstract | PDF
• TR2000-797 2000 A Feti preconditioner for two dimensional edge element approximations of Maxwell's equations on non-matching grids Rapetti, F.; Toselli, A. Abstract | PDF
• TR2000-807 2000 A Numerical Study of FETI Algorithms for Mortar Finite Element Methods Stefanica, Dan Abstract | PDF

  Title: A Numerical Study of FETI Algorithms for Mortar Finite Element Methods

  Author(s): Stefanica, Dan

  Abstract:

  The Finite Element Tearing and Interconnecting (FETI) method is an iterative substructuring method using Lagrange multipliers to enforce the continuity of the finite element solution across the subdomain interface. Mortar finite elements are nonconforming finite elements that allow for a geometrically nonconforming decomposition of the computational domain into subregions and, at the same time, for the optimal coupling of different variational approximations in different subregions. We present a numerical study of FETI algorithms for elliptic self-adjoint equations discretized by mortar finite elements. Several preconditioners which have been successful for the case of conforming finite elements are considered. We compare the performance of our algorithms when applied to classical mortar elements and to a new family of biorthogonal mortar elements and discuss the differences between enforcing mortar conditions instead of continuity conditions for the case of matching nodes across the interface. Our experiments are carried out for both two and three dimensional problems, and include a study of the relative costs of applying different preconditioners for mortar elements.

• TR2000-804 2000 Domain Decomposition Methods for Mortar Finite Elements Stefanica, Dan Abstract | PDF

  Title: Domain Decomposition Methods for Mortar Finite Elements

  Author(s): Stefanica, Dan

  Abstract:

  Domain decomposition methods are powerful iterative methods for solving systems of algebraic equations arising from the discretization of partial differential equations by, e.g., finite elements. The computational domain is decomposed into overlapping or nonoverlapping subdomains. The problem is divided into, or assembled from, smaller subproblems corresponding to these subdomains. In this dissertation, we focus on domain decomposition methods for mortar finite elements, which are nonconforming finite element methods that allow for a geometrically nonconforming decomposition of the computational domain into subregions and for the optimal coupling of different variational approximations in different subregions.

  We introduce a FETI method for mortar finite elements, and provide numer- ical comparisons of FETI algorithms for mortar finite elements when different preconditioners, given in the FETI literature, are considered. We also analyze the complexity of the preconditioners for the three dimensional versions of the algorithms.

  We formulate a variant of the balancing method for mortar finite elements, which uses extended local regions to account for the nonmortar sides of the subre- gions. We prove a polylogarithmic condition number estimate for our algorithm in the geometrically nonconforming case. Our estimate is similar to those for other Neumann{Neumann and substructuring methods for mortar finite elements.

  In addition, we establish several fundamental properties of mortar finite elements: the existence of the nonmortar partition of any interface, the L^2 stability of the mortar projection for arbitrary meshes on the nonmortar side, and prove Friedrichs and Poincare inequalities for geometrically nonconforming mortar elements.

• Ph.D. Thesis 2000 Queryable Expert Systems Tanzer, David Abstract | PDF

  Title: Queryable Expert Systems

  Candidate: Tanzer, David

  Abstract:

  
  

  DEPARTMENT OF COMPUTER SCIENCE
  DOCTORAL DISSERTATION DEFENSE
  
  
  Candidate: David Tanzer
  Advisor: Dennis Shasha
  
  
  
  
  
  
  

  Queryable Expert Systems
  
  

  10:00 a.m., Tuesday, October 17, 2000
  12th floor conference room, 719 Broadway
  
  
  

  
  
  
  
  
  
  

  Abstract
  
  

  Interactive rule-based expert systems, which work by ``interviewing'' their users, have found applications in fields ranging from aerospace to help desks. Although they have been shown to be useful, people find them difficult to query in flexible ways. This limits the reusability of the knowledge they contain. Databases and noninteractive rule systems such as logic programs, on the other hand, are queryable but they do not offer an interview capability. This thesis is the first investigation that we know of into query-processing for interactive expert systems.

  In our query paradigm, the user describes a hypothetical condition and then the system reports which of its conclusions are reachable, and which are inevitable, under that condition. For instance, if the input value for bloodSugar exceeds 100 units, is the conclusion diabetes then inevitable? Reachability problems have been studied in other settings, e.g., the halting problem, but not for interactive expert systems.

  We first give a theoretical framework for query-processing that covers a wide class of interactive expert systems. Then we present a query algorithm for a specific language of expert systems. This language is a restriction of production systems to an acyclic form that generalizes decision trees and classical spreadsheets. The algorithm effects a reduction from the reachability and inevitability queries into datalog rules with constraints. When preconditions are conjunctive, the data complexity is tractable. Next, we optimize for queries to production systems that contain regions which are decision trees. When general-purpose datalog methods are applied to the rules that result from our queries, the number of constraints that must be solved is O ( n ² ), where n is the size of the trees. We lower the complexity to O ( n ). Finally, we have built a query tool for a useful subset of the acyclic production systems. To our knowledge, these are the first interactive expert systems that can be queried about the reachability and inevitability of their conclusions.
  

  ---

  
  

  
  
• TR2000-800 2000 FETI domain decomposition methods for scalar advection-diffusion problems Toselli, A. Abstract | PDF

  Title: FETI domain decomposition methods for scalar advection-diffusion problems

  Author(s): Toselli, A.

  Abstract:

  In this paper, we show that iterative substructuring methods of Finite Element Tearing and Interconnecting type can be successfully employed for the solution of linear systems arising from the finite element approximation of scalar advection-diffusion problems. Using similar ideas as those of a recently developed Neumann-Neumann method, we propose a one-level algorithm and a class of two-level algorithms, obtained by suitably modifying the local problems on the subdomains. We present some numerical results for some significant test cases. Our methods appear to be optimal for flows without closed streamlines and possibly very small values of the viscosity. They also show very good performances for rotating flows and moderate Reynolds numbers. Therefore, the algorithms proposed appear to be well-suited for many convection-dominated problems of practical interest.

• TR2000-806 2000 hp-finite element approximations on non-matching grids for partial differential equations with non-negative characteristic form Toselli, Andrea Abstract | PDF

  Title: hp-finite element approximations on non-matching grids for partial differential equations with non-negative characteristic form

  Author(s): Toselli, Andrea

  Abstract:

  We propose and analyze a domain decomposition method on non-matching grids for partial differential equations with non-negative characteristic form. No weak or strong continuity of the finite element functions, their normal derivatives, or linear combinations of the two is imposed across the boundaries of the subdomains. Instead, we employ suitable bilinear forms defined on the common interfaces, typical of discontinuous Galerkin approximations. We prove an error bound which is optimal with respect to the mesh-size and suboptimal with respect to the polynomial degree. Our analysis is valid for arbitrary shape-regular meshes and arbitrary partitions into subdomains. Our method can be applied to advective, diffusive, and mixed-type equations, as well, and is well-suited for problems coupling hyperbolic and elliptic equations.

• Ph.D. Thesis 2000 Scenario Customization for Information Extraction Yangarber, Roman Abstract | PDF

  Title: Scenario Customization for Information Extraction

  Candidate: Yangarber, Roman

  Advisor(s): Grishman, Ralph

  Abstract:

  Information Extraction (IE) is an emerging NLP technology, whose function is to process unstructured, natural language text, to locate specific pieces of information, or facts , in the text, and to use these facts to fill a database. IE systems today are commonly based on pattern matching. The core IE engine uses a cascade of sets of patterns of increasing linguistic complexity. Each pattern consists of a regular expression and an associated mapping from syntactic to logical form. The pattern sets are customized for each new topic , as defined by the set of facts to be extracted.

  Construction of a pattern base for a new topic is recognized as a time-consuming and expensive process--a principal roadblock to wider use of IE technology in the large. An effective pattern base must be precise and must have wide coverage. This thesis addresses the portability problem in two stages.

  First, we introduce a set of tools for building patterns manually from examples . To adapt the IE system to a new subject domain quickly, the user chooses a set of example sentences from a training text, and specifies how each example maps to the extracted event--its logical form. The system then applies meta-rules to transform the example automatically into a general set of patterns. This effectively shifts the portability bottleneck from building patterns to finding good examples.

  Second, we propose a novel methodology for discovering good examples automatically from a large un-annotated corpus of text. The system is initially seeded with a small set of relevant patterns provided by the user. An unsupervised learning procedure then identifies new patterns and classes of related terms on successive iterations. We present experimental results, which confirm that the discovered patterns exhibit high quality, as measured in terms of precision and recall.

• TR2000-805 2000 Expressing and Enforcing Distributed Resource Sharing Agreements Zhao, Tao; Karamcheti, Vijay Abstract | PDF

  Title: Expressing and Enforcing Distributed Resource Sharing Agreements

  Author(s): Zhao, Tao; Karamcheti, Vijay

  Abstract:

  Advances in computing and networking technology, and an explosion in information sources has resulted in a growing number of distributed systems getting constructed out of resources contributed by multiple sources. Use of such resources is typically governed by sharing agreements between owning principals, which limit both who can access a resource and in what quantity. Despite their increasing importance, existing resource management infrastructures offer only limited support for the expression and enforcement of sharing agreements, typically restricting themselves to identifying compatible resources. In this paper, we present a novel approach building on the concepts of tickets and currencies to express resource sharing agreements in an abstract, dynamic, and uniform fashion. We also formu-late the allocation problem of enforcing these agreements as a linear-programming model, automatically factoring the transitive availability of resources via chained agreements. A case study modeling resource sharing among ISP-level web proxies shows the benefits of enforcing transitive agreements: worst-case waiting times of clients accessing these proxies improves by up to two orders of magnitude.