The efficacy of neural “retrieve and generate” systems is well established for question answering (QA) over unstructured text. Recent efforts seek to extend this approach to knowledge graph (KG) QA by converting structured triples to unstructured text. However, the relevance of KG triples retrieved by these systems limits their accuracy. In this paper, we improve the relevance of retrieved triples using a carefully designed re-ranker. Specifically, our pipeline (i) retrieves over documents of triples grouped by entity, (ii) re-ranks triples from these documents with context: triples in the 1-hop neighborhood of the documents’ subject entity, and (iii) generates an answer from highly relevant re-ranked triples. To train our re-ranker, we propose a novel “triple-level” labeling strategy that infers fine-grained labels and shows that these significantly improve the relevance of retrieved information. We show that the resulting “retrieve, re-rank, and generate” pipeline significantly improves upon prior KGQA systems, achieving a new state-of-the-art on FreebaseQA by 5.56% Exact Match. We perform multiple ablations that reveal the distinct benefits of our contextual re-ranker and labeling strategy and conclude with a case study that highlights opportunities for future works.

Hyundong Justin Cho, Nicolaas Paul Jedema, Leonardo F. R. Ribeiro, Karishma Sharma, Pedro Szekely, Alessandro Moschitti, Ruben Janssen, Jonathan May. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

Embedding methods have demonstrated robust performance on the task of link prediction in knowledge graphs, by mostly encoding entity relationships. Recent methods propose to enhance the loss function with a literal-aware term. In this paper, we propose KGA: a knowledge graph augmentation method that incorporates literals in an embedding model without modifying its loss function. KGA discretizes quantity and year values into bins, and chains these bins both horizontally, modeling neighboring values, and vertically, modeling multiple levels of granularity. KGA is scalable and can be used as a pre-processing step for any existing knowledge graph embedding model. Experiments on legacy benchmarks and a new large benchmark, DWD, show that augmenting the knowledge graph with quantities and years is beneficial for predicting both entities and numbers, as KGA outperforms the vanilla models and other relevant baselines. Our ablation studies confirm that both quantities and years contribute to KGA's performance, and that its performance depends on the discretization and binning settings. We make the code, models, and the DWD benchmark publicly available to facilitate reproducibility and future research.

Controlled table-to-text generation seeks to generate natural language descriptions for highlighted subparts of a table.Previous SOTA systems still employ a sequence-to-sequence generation method, which merely captures the table as a linear structure and is brittle when table layouts change.We seek to go beyond this paradigm by (1) effectively expressing the relations of content pieces in the table, and (2) making our model robust to content-invariant structural transformations.Accordingly, we propose an equivariance learning framework, LATTICE ( ), which encodes tables with a structure-aware self-attention mechanism.This prunes the full self-attention structure into an order-invariant graph attention that captures the connected graph structure of cells belonging to the same row or column, and it differentiates between relevant cells and irrelevant cells from the structural perspective.Our framework also modifies the positional encoding mechanism to preserve the relative position of tokens in the same cell but enforce position invariance among different cells.Our technology is free to be plugged into existing table-to-text generation models, and has improved T5-based models to offer better performance on ToTTo and HiTab.Moreover, on a harder version of ToTTo, we preserve promising performance, while previous SOTA systems, even with transformationbased data augmentation, have seen significant performance drops. 1

Web advertising related to Human Trafficking (HT) activity has been on the rise in recent years. Answering entity-centric questions over crawled HT Web corpora to assist investigators in the real world is an important social problem, involving many technical challenges. This paper describes a recent entity-centric knowledge graph effort that resulted in a semantic search engine to assist analysts and investigative experts in the HT domain. The overall approach takes as input a large corpus of advertisements crawled from the Web, structures it into an indexed knowledge graph, and enables investigators to satisfy their information needs by posing investigative search queries to a special-purpose semantic execution engine. We evaluated the search engine on real-world data collected from over 90,000 webpages, a significant fraction of which correlates with HT activity. Performance on four relevant categories of questions on a mean average precision metric were found to be promising, outperforming a learning-to-rank approach on three of the four categories. The prototype uses open-source components and scales to terabyte-scale corpora. Principles of the prototype have also been independently replicated, with similarly successful results.

Entity resolution is the task of identifying records in different datasets that refer to the same entity in the real world. In sensitive domains (e.g. financial accounts, hospital health records), entity resolution must meet privacy requirements to avoid revealing sensitive information such as personal identifiable information to untrusted parties. Existing solutions are either too algorithmically-specific or come with an implicit trade-off between accuracy of the computation, privacy, and run-time efficiency. We propose AMMPERE, an abstract computation model for performing universal privacy-preserving entity resolution. AMMPERE offers abstractions that encapsulate multiple algorithmic and platform-agnostic approaches using variants of Jaccard similarity to perform private data matching and entity resolution. Specifically, we show that two parties can perform entity resolution over their data, without leaking sensitive information. We rigorously compare and analyze the feasibility, performance overhead and privacy-preserving properties of these approaches on the Sharemind multi-party computation (MPC) platform as well as on PALISADE, a lattice-based homomorphic encryption library. The AMMPERE system demonstrates the efficacy of privacy-preserving entity resolution for real-world data while providing a precise characterization of the induced cost of preventing information leakage.

The large coverage and quality of the Wikidata knowledge graph make it suitable for usage in downstream applications, such as entity summarization, entity linking, and question answering. Yet, most retrieval and similarity-based methods for Wikidata make limited use of its semantics, and lose the link between the rich structure in Wikidata and the decision-making algorithm. In this paper, we investigate how to define abstractive representations (profiles) of Wikidata entities. We propose a scalable method that can produce profiles for Wikidata entities based on salient labels associated with their types. We represent the resulting profiles as a graph, and compute profile embeddings. Our empirical analysis shows that the profiles can capture similarity competitively to baselines, but excel in terms of explainability. On the task of neural entity linking in tables, the profiles outperform all baselines in terms of accuracy, whereas their human-readable representation clearly explains the source of improvement. We make our code and data available to facilitate novel use cases based on the Wikidata profiles.

A wealth of human knowledge is expressed in structured tables, across web pages, scientific articles, spreadsheets, and databases. This wealth of knowledge is mirrored by diversity in the vast number of layout structures, content types, formats, and surface forms used to express tables. Recent advances in representation learning and knowledge representation have made progress in exploiting structural regularities in tabular data to unlock this knowledge. In this tutorial, we provide a survey of these advances for a host of table understanding tasks, including table segmentation, semantic typing of cells, transforming tables to knowledge graphs, entity linking, and table retrieval tasks for question answering.

Avijit Thawani, Jay Pujara, Filip Ilievski, Pedro Szekely. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021.

The task of natural language table retrieval (NLTR) seeks to retrieve semantically relevant tables based on natural language queries. Existing learning systems for this task often treat tables as plain text based on the assumption that tables are structured as dataframes. However, tables can have complex layouts which indicate diverse dependencies between subtable structures, such as nested headers. As a result, queries may refer to different spans of relevant content that is distributed across these structures. Moreover, such systems fail to generalize to novel scenarios beyond those seen in the training set. Prior methods are still distant from a generalizable solution to the NLTR problem, as they fall short in handling complex table layouts or queries over multiple granularities. To address these issues, we propose Graph-based Table Retrieval (GTR), a generalizable NLTR framework with multi-granular graph representation learning. In our framework, a table is first converted into a tabular graph, with cell nodes, row nodes and column nodes to capture content at different granularities. Then the tabular graph is input to a Graph Transformer model that can capture both table cell content and the layout structures. To enhance the robustness and generalizability of the model, we further incorporate a self-supervised pre-training task based on graph-context matching. Experimental results on two benchmarks show that our method leads to significant improvements over the current state-of-the-art systems. Further experiments demonstrate promising performance of our method on cross-dataset generalization, and enhanced capability of handling complex tables and fulfilling diverse query intents.

There is a large amount of data on the web in tabular form, such as excel sheets, CSVs, and web tables. Often, tabular data is meant for human consumption, using data layouts that are difficult for machines to interpret automatically. Previous work uses the stylistic features of tabular cells (e.g. font size, border type, background color) to classify tabular cells by their role in the data layout of the document (top attribute, data, metadata, etc.). In this paper, we propose a method to embed the semantic and contextual information about tabular cells in a low dimension cell embedding space. We then propose an RNN-based classification technique to use these cell vector representations, combining them with stylistic features introduced in previous work, in order to improve the performance of cell type classification in complex documents. We evaluate the performance of our system on three datasets containing documents with various data layouts, in two settings, in-domain, and cross-domain training. Our evaluation result shows that our proposed cell vector representations in combination with our RNN-based classification technique significantly improves cell type classification performance.

Forecasting of geopolitical events is a notoriously difficult task, with experts failing to significantly outperform a random baseline across many types of forecasting events. One successful way to increase the performance of forecasting tasks is to turn to crowdsourcing: leveraging many forecasts from non-expert users. Simultaneously, advances in machine learning have led to models that can produce reasonable, although not perfect, forecasts for many tasks. Recent efforts have shown that forecasts can be further improved by ``hybridizing'' human forecasters: pairing them with the machine models in an effort to combine the unique advantages of both. In this demonstration, we present Synergistic Anticipation of Geopolitical Events (SAGE), a platform for human/computer interaction that facilitates human reasoning with machine models.

The web contains millions of useful spreadsheets and CSV files, but these files are difficult to use in applications because they use a wide variety of data layouts and terminology. We present Table To Wikidata Mapping Language (T2WML), a language that makes it easy to map and link arbitrary spreadsheets and CSV files to the Wikidata data model. The output of T2WML consists of Wikidata statements that can be loaded in the public Wikidata knowledge base or in a Wikidata clone repository, creating an augmented Wikidata knowledge graph that application developers can query using SPARQL.

Motivated by the problem of human-trafficking, where it is often observed that criminal organizations are linked and behave similarly over time, we introduce the problem of Coupled Clustering of Time-series and their underlying Network. The goal is to find tightly connected subgroups of nodes that also have similar node-specific time series (temporal—not necessarily structural—behavior). We formulate the problem as a coupled matrix factorization for the time series, combined with regularization for network smoothness. We propose CCTN, and an incrementally-updated counterpart, CCTN-inc, which efficiently handles network updates. Extensive experiments show that CCTN is up to 4x more accurate than baselines that consider graph structure or time series alone, and CCTN-inc is up to 55x faster than CCTN. As an application, we explore an exclusive database with millions of online ads on human trafficking, and successfully deploy our technique to detect criminal organizations.

Knowledge Graph Construction (KGC) is an important problem that has many domain-specific applications, including semantic search and predictive analytics. As sophisticated KGC algorithms continue to be proposed, an important, neglected use case is to empower domain experts who do not have much technical background to construct high-fidelity, interpretable knowledge graphs. Such domain experts are a valuable source of input because of their (both formal and learned) knowledge of the domain. In this demonstration paper, we present a system that allows domain experts to construct knowledge graphs by writing sophisticated rule-based entity extractors with minimal training, using a GUI-based editor that offers a range of complex facilities.

We propose a demonstration of myDIG (my Domain-specific Insight Graphs), a system that allows non-technical domain experts, including those with no programming experience, to construct a domain-specific search engine over a raw corpus of webpages. myDIG has been developed and refined over multiple years under the DARPA MEMEX program, and has undergone rigorous user testing with actual domain experts from investigative agencies like the Securities and Exchange Commission (SEC). All components of myDIG are open-source, and the product of fundamental research.

Extracting useful entities and attribute values from illicit domains such as human trafficking is a challenging problem with the potential for widespread social impact. Such domains employ atypical language models, have 'long tails' and suffer from the problem of concept drift. In this paper, we propose a lightweight, feature-agnostic Information Extraction (IE) paradigm specifically designed for such domains. Our approach uses raw, unlabeled text from an initial corpus, and a few (12-120) seed annotations per domain-specific attribute, to learn robust IE models for unobserved pages and websites. Empirically, we demonstrate that our approach can outperform feature-centric Conditional Random Field baselines by over 18% F-Measure on five annotated sets of real-world human trafficking datasets in both low-supervision and high-supervision settings. We also show that our approach is demonstrably robust to concept drift, and can be efficiently bootstrapped even in a serial computing environment.

The paper describes a novel algorithm for timely sensor data retrieval in resource-poor environments under freshness constraints. Consider a civil unrest, national security, or disaster management scenario, where a dynamic situation evolves and a decision-maker must decide on a course of action in view of latest data. Since the situation changes, so is the best course of action. The scenario offers two interesting constraints. First, one should be able to successfully compute the course of action within some appropriate time window, which we call the decision deadline. Second, at the time the course of action is computed, the data it is based on must be fresh (i.e., within some corresponding validity interval). We call it the freshness constraint. These constraints create an interesting novel problem of timely data retrieval. We address this problem in resource-scarce environments, where network resource limitations require that data objects (e.g., pictures and other sensor measurements pertinent to the decision) generally remain at the sources. Hence, one must decide on (i) which objects to retrieve and (ii) in what order, such that the cost of deciding on a valid course of action is minimized while meeting data freshness and decision deadline constraints. Such an algorithm is reported in this paper. The algorithm is shown in simulation to reduce the cost of data retrieval compared to a host of baselines that consider time or resource constraints. It is applied in the context of minimizing cost of finding unobstructed routes between specified locations in a disaster zone by retrieving data on the health of individual route segments.

Programming by example enables users to transform data formats without coding. To be practical, the method must synthesize the correct transformation with minimal user input. We present a method that minimizes user effort by color-coding the transformation result and recommending specific records where the user should provide examples. Simulation results and a user study show that our method significantly reduces user effort and increases the success rate for synthesizing correct transformation programs by example.

This paper presents an abstract for a general data transformation approach. Using programming by demonstration technique, we learn the transformation rules through user given examples. These transformation rules are automatically generated from a predefined grammar. Due to the grammar space is huge, we propose a grammar space reduction method to reduce the search space and a sketch of search algorithm is adopted to identify the rules that are consistent with the examples. The final experimental results show our approach achieves promising results on different transformation scenarios.

Humans have difficulty evaluating the effects of uncertainty on schedules. People often mitigate the effects of uncertainty by adding slack based on experience and non-stochastic analyses such as the critical path method (CPM). This is costly as it leads to longer than necessary schedules, and can be ineffective without a clear understanding of where slack is needed. COMPASS is an interactive real-time tool that analyzes schedule uncertainty for a stochastic task network. An important feature is that it concurrently calculates stochastic critical paths and critical tasks. COMPASS visualizes this information on top of a traditional Gantt view, giving users insight into how delays caused by uncertain durations propagate down the schedule. Evaluations with 10 users show that users can use COMPASS to answer a variety of questions about the possible evolutions of a schedule (e.g., what is the likelihood that all activities will complete before a given date?)

The latest generation of WWW tools and services enables Web users to generate applications that combine content from multiple sources. This type of Web application is referred to as a mashup. Many of the tools for constructing mashups rely on a widget paradigm, where users must select, customize, and connect widgets to build the desired application. While this approach does not require programming, the users must still understand programming concepts to successfully create a mashup. As a result, they are put off by the time, effort, and expertise needed to build a mashup. In this article, we describe our programming-by-demonstration approach to building mashup by example. Instead of requiring a user to select and customize a set of widgets, the user simply demonstrates the integration task by example. Our approach addresses the problems of extracting data from Web sources, cleaning and modeling the extracted data, and integrating the data across sources. We implemented these ideas in a system called Karma, and evaluated Karma on a set of 23 users. The results show that, compared to other mashup construction tools, Karma allows more of the users to successfully build mashups and makes it possible to build these mashups significantly faster compared to using a widget-based approach.

This paper presents a bio-inspired, distributed control algorithm calledTENTACLESfor a group of radio robots to move, self-configure and maintain communication between some critical entities (such as humans, command centers, or other systems) in an unknown environment. The basic idea is to direct robots' explorative movements to grow ¿tentacles¿ from entities and establish links when tentacles meet. This approach can self-heal failures of robots and improve communication coverage and quality over time. Experiments in simulations and real robots have shown positive results.

In many domains, decision makers want to find and understand patterns of events as these patterns often give insight into the causal relationships among events. Current systems to specify patterns are either too difficult to use or only support simple patterns. We present QueryMarvel, an interactive visual query environment that allows ordinary users to easily and efficiently specify complex temporal patterns. It uses and extends the semantic elements and rules of comic strips with the goal to make specifying and interpreting temporal patterns as easy as reading and writing a comic story. User tests show that using QueryMarvel, users can understand and create temporal patterns faster and with fewer errors than using a form-based interface.

One of the most difficult tasks in software development is understanding the behavior of the final product. Making sure that a system behaves as users expect is a challenging endeavor. Understanding the behavior of a multi-agent system is even more challenging given the additional complexities of multi-agent problems. In this paper, we address the problem of users creating visualizations to debug and understand complex multi-agent systems. We introduce VizScript, a generic framework that expedites the process of creating such visualizations. VizScript combines a generic application instrumentation, a knowledge-base, and simple scene definitions primitives with a reasoning system, to produce an easy to use visualization platform. Using VizScript, we were able to recreate the visualizations for a complex multiagent system with an order-of-magnitude less effort than was required in a Java implementation

Coordinators are intelligent software agents that help humans to collaborate and coordinate execution of multiple activities in dynamic, distributed and uncertain domains. One of the main challenges is the generation of effective user interfaces for team coordination. Intelligent interfaces that avoid information overload, and facilitate user interactions to repair mission plans are needed, and they are the focus of this work.

Creating a Mashup, a web application that integrates data from multiple web sources to provide a unique service, involves solving multiple problems, such as extracting data from multiple web sources, cleaning it, and combining it together. Existing work relies on a widget paradigm where users address those problems during a Mashup building process by selecting, customizing, and connecting widgets together. While these systems claim that their users do not have to write a single line of code, merely abstracting programming methods into widgets has several disadvantages. First, as the number of widgets increases to support more operations, locating the right widget for the task can be confusing and time consuming. Second, customizing and connecting these widgets usually requires users to understand programming concepts. In this paper, we present a Mashup building approach that (a) combines most problem areas in Mashup building into a unified interactive framework that requires no widgets, and (b) allows users with no programming background to easily create Mashups by example.

We address the problem of users creating visualizations to debug and understand multi-agent systems. The key challenges are that (1) needs arise dynamically, i.e., it is difficult to know a priori what visualizations one wants, (2) extensive expertise on the system, the algorithms and visualization tools are often needed for implementation, and (3) agents can be running in a distributed environment. We have developed VizScript, a collection of tools to expedite the process of creating visualizations. VizScript combines a generic application instrumentation, a knowledge base, and simple scene definition primitives with a reasoning system, to produce an easy to use visualization system. Using VizScript we were able to recreate the visualizations for a complex multi-agent system with an order-of-magnitude less effort than was required in a Java implementation.

The magnitude of data available on the web prompts the need for an easy to use query interface that enables users to integrate data from multiple web sources in an intelligent fashion. Past work in the area of databases has resulted in different query interface systems that simplify query formulation. While these approaches reduce the user's effort to compose queries, the user is still required to pick data sources to use and the interaction is not guaranteed to yield a non-empty result set. We introduce a novel approach that exploits the structure of the relational data source(s) to formulate a set of constraints. These constraints are used in conjunction with partial plans to produce an intelligent query interface that (a) does not require the user to know details about data sources or existing values (b) suggests valid inputs to the user (c) creates consistent queries that always return values.

One-way constraints have been incorporated in many graphical user interface toolkits because they are simple to learn, easy to write, and can express many types of useful graphical relationships. This paper is an evaluative paper that examines users' experience with one-way constraints in two user interface development toolkits, Garnet and Amulet, over a 15-year time span. The lessons gained from this examination can help guide the design of future constraint systems. The most important lessons are that (1) constraints should be allowed to contain arbitrary code that is written in the underlying toolkit language and does not require any annotations, such as parameter declarations, (2) constraints are difficult to debug and better debugging tools are needed, and (3) programmers will readily use one-way constraints to specify the graphical layout of an application, but must be carefully and time-consumingly trained to use them for other purposes. Copyright © 2005 John Wiley & Sons, Ltd.

>Synchronized punch-card displaysare an interface technique to visualize tens of thousands of variables by encoding their values as color chips in a rectangular array. Our technique ties multiple such displays to a timeline of events enabling the punch-card displays to show animations of the behavior of complex systems. Punch-card displays not only make it easy to understand the high-level behavior of systems, but also enable users to quickly focus on individual variables and on fine-grained time intervals. This paper describes synchronized punch-card displays and shows how this technique is extremely powerful for understanding the behavior of complex multi-agent systems.

One-way, dataflow constraints are commonly used in graphical interface toolkits, programming environments, and circuit applications. Previous papers on dataflow constraints have focused on the design and implementation of individual algorithms. In contrast, this article focuses on the lessons we have learned from a decade of implementing competing algorithms in the Garnet and Amulet graphical interface toolkits. These lessons reveal the design and implementation tradeoffs for different one-way, constraint satisfaction algorithms. The most important lessons we have learned are that (1) mark-sweep algorithms are more efficient than topological ordering algorithms; (2) lazy and eager evaluators deliver roughly comparable performance for most applications; and (3) constraint satisfaction algorithms have more than adequate speed, except that the storage required by these algorithms can be problematic.

This paper presents an architecture for information retrieval agents in which each agent declaratively describes its domain, input, output, and user interface.A mediating piece of software can then assemble software agents for a given information retrieval task, and produce a single, unified user interface for that task from the individual agents' descriptions.

Article Free Access Share on Adaptive forms: an interaction paradigm for entering structured data Authors: Martin R. Frank University of Southern California - Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, California University of Southern California - Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CaliforniaView Profile , Pedro Szekely University of Southern California - Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, California University of Southern California - Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CaliforniaView Profile Authors Info & Claims IUI '98: Proceedings of the 3rd international conference on Intelligent user interfacesJanuary 1998 Pages 153–160https://doi.org/10.1145/268389.268418Online:01 January 1998Publication History 11citation475DownloadsMetricsTotal Citations11Total Downloads475Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Current interface development tools cannot be used to specify complex displays without resorting to programming using a toolkit or graphics package.Interface builders and multi-media authoring tools only support the construction of static displays where the components of the display are known at design time (e.g., buttons, menus).This paper describes a presentation modeling system where complex displays of dynamically changing data can be modeled declaratively.The system incorporates principles of graphic design such as guides and grids, supports constraint-based layout and automatic update when data changes, has facilities for easily specifying the layout of collections of data, and has facilities for making displays sensitive to the characteristics of the data being presented and the presentation context (e.g., amount of space available).Finally, the models are designed to be amenable to interactive specification and specification using demonstrational techniques.

Model-based interface design can save substantial effort in building help systems for interactive applications by generating help automatically from the model used to implement the interface, and by providing a framework for developers to easily refine the automatically-generated help texts.This paper describes a system that generates hypertext-based help about data presented in application displays, commands to manipulate data, and interaction techniques to invoke commands.The refinement component provides several levels of customization, including programming-by-example techniques to let developers edit directly help windows that the system produces, and the possibility to refine help generation rules.

Pointer variables have long been considered useful for constructing and manipulating data structures in traditional programming languages. This article discusses how pointer variables can be integrated into one-way constraint models and indicates how these constraints can be usefully employed in user interfaces. Pointer variables allow constraints to model a wide array of dynamic application behavior, simplify the implementation of structured objects and demonstrational systems, and improve the storage and efficiency of constraint-based applications. This article presents two incremental algorithms—one lazy and one eager— for solving constraints with pointer variables. Both algorithms are capable of handling (1) arbitrary systems of one-way constraints, including constraints that involve cycles, and (2) editing models that allow multiple changes between calls to the constraint solver. These algorithms are fault tolerant in that they can handle and recover gracefully from formulas that crash due to programmer error. Constraints that use pointer variables have been implemented in a comprehensive user interface toolkit, Garnet, and our experience with applications written in Garnet have proven the usefulness of pointer variable constraints. Many large-scale applications have been implemented using these constraints.

HUMANOID is a user interface design tool that lets designers express abstract conceptualizations of an interface in an executable form, allowing designers to experiment with scenarios and dialogues even before the application model is completely worked out. Three properties of the HUMANOID approach allow it to do so: a modularization of design issues into independent dimensions, support for multiple levels of specificity in mapping application models to user interface constructs, and mechanisms for constructing executable default user interface implementations from whatever level of specificity has been provided by the designer.

Graphical tools are increasingly using constraints to specify the graphical layout and behavior of many parts of an application.However, conventional constraints directly encode the objects they reference, and thus cannot provide support for the dynamic rttntime creation and manipulation of application objects.This paper discusses an extension to current constraint models that allows constraints to indirectly reference objects through pointer variables.Pointer variables permit programmers to create the constraint equivalent of procedures in traditional programming languages.This procedural abstraction allows constraints to model a wide array of dynamic application behavior, simplifies the implementation of structured object and demonstrational systems, and improves the storage and efficiency of highly interactive, graphical applications.It also promotes a simpler, more effective style of programming than conventional constraints.Constraints that use pointer variables are powerful enough to allow a comprehensive user interface toolkit to be built for the first time on top of a constraint system.

This paper describes a template-based method for constructing interactive displays with the building-blocks (widgets 1 provided in a user interface toolkit.Templates specify how to break down complex application objects into smaller pieces, specify the graphical components (widgets) to be used for displaying each piece, and specify their layout.Complex interfaces are constructed by recursively applying templates, thus constructing a tree of widgets to display a complex application object.The template-based method is more general than the interactive, WYSIWYG interface builders in that it can specify dynamic displays for application data that changes at run time.The template-based method also leads to more consistent, extendable and modifiable interfaces. I .O IntroductionUser interface toolkits such as the X Toolkit [ 101 and the Macintosh Tool-Box [S] provide abstractions that make the construction of user interfaces significantly easier than programming using graphics primitives.Unfortunately the toolkits do not make the construction of user interfaces easy enough.The tasks of assembling the widgets to construct complex displays, and of tying the widgets to application data structures remains difficult and time consuming.Interactive user interface builder systems such as Prototyper [ 141 provide interactive what-you-see-is-what-you-get interfaces to assemble tool-box widgets into more complex

The user interface building blocks of any User Interface Management System (UIMS) have built-in assumptions about what information about application programs they need, and assumptions about how to get that information. The lack of a standard to represent this information leads to a proliferation of different assumptions by different building blocks, hampering changeability of the user interface and portability of applications to different sets of building blocks. This paper describes a formalism for specifying the information about applications needed by the user interface building blocks (i.e. the UIMS/Application interface) so that all building blocks share a common set of assumptions. The paper also describes a set of user interface building blocks specifically designed for these standard UIMS/Application interfaces. These building blocks can be used to produce a wide variety of user interfaces, and the interfaces can be changed without having to change the application program.

One of the most difficult aspects of creating graphical, direct manipulation user interfaces is managing the relationships between the graphical objects on the screen and the application data structures that they represent. Coral (Constraint-based Object-oriented Relations And Language) is a new user interface toolkit under development that uses efficiently-implemented constraints to support these relationships. Using Coral, user interface designers can construct interaction techniques such as menus and scroll bars. More importantly, Coral makes it easy to construct direct-manipulation user interfaces specialized to particular applications. Unlike previous constraint-based toolkits, Coral supports defining constraints in the abstract, and then applying them to different object instances. In addition, it provides iteration constructs where lists of items (such as those used in menus) can be constrained as a group. Coral has two interfaces: a declarative interface that provides a convenient way to specify the desired constraints, and a procedural interface that will allow a graphical user interface management system (UIMS) to automatically create Coral calls.

The presentation of an application program specifies how the data and operations provided by an application are presented to users. Most traditional techniques for implementing presentations lead to unstructured, unmodular implementations that are hard to construct and change. We present a model of presentation that identifies the dependencies between the presentation and functionality portions of an application. Based on this model, we show how several implementation techniques can be used to construct presentations in a modular way.