32378250
Using Distributed Objects to Build the Stanford Digital Library Infobus
For digital libraries to thrive, the providers of information processing services must be able to evolve their systems autonomously. However, as the complexity of their offerings increases, software tools more sophisticated than existing Web facilities are needed. Distributed object technology may be the answer. The availability of high-volume, increasingly sophisticated information is making the need for metadata facilities more urgent. Traditional, library-based approaches break down when used in an advanced digital library. More modular mechanisms are needed, and the CORBA system is one approach. Digital libraries are affected at a deep technical level by the widely differing user traditions of Web users and library patrons. The challenge and opportunity of digital libraries will be the synthesis of these traditions. The authors set out to create a technical infrastructure to support the construction of digital libraries. In their view, a digital library comprises widely distributed resources that can be maintained autonomously by different organizations and will not require adherence to uniform interfaces.
15321340
Approximate Query Translation Across Heterogeneous Information Sources
In this paper we present a mechanism for approximately translating Boolean query constraints across heterogeneous information sources. Achieving the best translation is challenging because sources support different constraints for formulating queries, and often these constraints cannot be precisely translated. For instance, a query [score > 8] might be “perfectly” translated as [rating > 0.8] at some site, but can only be approximated as [grade = A] at another. Unlike other work, our general framework adopts a customizable “closeness” metric for the translation that combines both precision and recall. Our results show that for query translation we need to handle interdependencies among both query conjuncts as well as disjuncts. As the basis, we identify the essential requirements of a rule system for users to encode the mappings for atomic semantic units. Our algorithm then translates complex queries by rewriting them in terms of the semantic units. We show that, under practical assumptions, our algorithm generates the best approximate translations with respect to the closeness metric of choice. We also present a case study to show how our technique may be applied in practice.
2091518
Evaluating the cost of Boolean query mapping
Non-uniform query languages make searching over heterogeneous information sources difcult. Our approach is to allow a user to compose Boolean queries in one rich front-end language. For each user query and target source, we transform the user query into a subsuming query that can be supported by the source but that may return extra documents. The results are then processed by a lter query to yield the correct nal results. This post-ltering approach may involve signicant cost because the documents that the users will not see may have to be retrieved and ltered. There are generally two ways to implement post-ltering: batch post-ltering and incremental post-ltering. In this paper we evaluate the costs of both methods for different search features such as proximity operators. The experimental results show that in many cases incremental post-ltering cost may be acceptable, while the batch post-ltering cost may sometimes be extremely large.
18207157
Clustering Structured Web Sources: A Schema-Based, Model-Differentiation Approach
The Web has been rapidly “deepened” with the prevalence of databases online On this “deep Web,” numerous sources are structured, providing schema-rich data Their schemas define the object domain and its query capabilities This paper proposes clustering sources by their query schemas, which is critical for enabling both source selection and query mediation, by organizing sources of with similar query capabilities In abstraction, this problem is essentially clustering categorical data (by viewing each query schema as a transaction) Our approach hypothesizes that “homogeneous sources” are characterized by the same hidden generative models for their schemas To find clusters governed by such statistical distributions, we propose a novel objective function, model-differentiation, which employs principled hypothesis testing to maximize statistical heterogeneity among clusters Our evaluation shows that, on clustering the Web query schemas, the model-differentiation function outperforms existing ones with the hierarchical agglomerative clustering algorithm.
17572048
Supporting ad-hoc ranking aggregates
This paper presents a principled framework for efficient processing of ad-hoc top-k (ranking) aggregate queries, which provide the k groups with the highest aggregates as results. Essential support of such queries is lacking in current systems, which process the queries in a naïve materialize-group-sort scheme that can be prohibitively inefficient. Our framework is based on three fundamental principles. The Upper-Bound Principle dictates the requirements of early pruning, and the Group-Ranking and Tuple-Ranking Principles dictate group-ordering and tuple-ordering requirements. They together guide the query processor toward a provably optimal tuple schedule for aggregate query processing. We propose a new execution framework to apply the principles and requirements. We address the challenges in realizing the framework and implementing new query operators, enabling efficient group-aware and rank-aware query plans. The experimental study validates our framework by demonstrating orders of magnitude performance improvement in the new query plans, compared with the traditional plans.
6980873
Making holistic schema matching robust: an ensemble approach
The Web has been rapidly "deepened" by myriad searchable databases online, where data are hidden behind query interfaces. As an essential task toward integrating these massive "deep Web" sources, large scale schema matching (i.e., discovering semantic correspondences of attributes across many query interfaces) has been actively studied recently. In particular, many works have emerged to address this problem by "holistically" matching many schemas at the same time and thus pursuing "mining" approaches in nature. However, while holistic schema matching has built its promise upon the large quantity of input schemas, it also suffers the robustness problem caused by noisy data quality. Such noises often inevitably arise in the automatic extraction of schema data, which is mandatory in large scale integration. For holistic matching to be viable, it is thus essential to make it robust against noisy schemas. To tackle this challenge, we propose a data-ensemble framework with sampling and voting techniques, which is inspired by bagging predictors. Specifically, our approach creates an ensemble of matchers, by randomizing input schema data into many independently downsampled trials, executing the same matcher on each trial and then aggregating their ranked results by taking majority voting. As a principled basis, we provide analytic justification of the effectiveness of this data-ensemble framework. Further, empirically, our experiments on real Web data show that the "ensemblization" indeed significantly boosts the matching accuracy under noisy schema input, and thus maintains the desired robustness of a holistic matcher.
14390424
A Temporal Assertion Extension to Verilog
Many circuit designs need to follow some temporal rules. However, it is hard to express and verify them in the past. Therefore, a temporal assertion extension to Verilog, called Temporal Wizard, is proposed in this paper. It provides several Verilog system tasks for the users to write assertions in testbench directly. Two new concepts, tag and thread, are also introduced so that data can be associated with temporal assertions and provide more functionalities than previous temporal assertion checkers.
17374517
Model Checking with Induction
We have proposed inductive model checking (IMC) to alleviate the state explosion problem in model checking. IMC divides the whole verification tasks into several sub-tasks, and applies the three inductive steps (basis, hypothesis, and induction) to verify a system with model checking. In this paper, we continue our research by determining those temporal formulas, namely, persistent temporal formulas, which are verifiable with IMC. One important characteristic of a persistent temporal formula is that it contains a periodic temporal formula that must be held persistently. From the verification results of the periodic formula with different sequences of states, IMC concludes the verification of the persistent temporal formula
61942372
Simulation-based bug trace minimization with BMC-based refinement
Finding the cause of a bug can be one of the most time-consuming activities in design verification. This is particularly true in the case of bugs discovered in the context of a random simulation- based methodology, where bug traces, or counter-examples, may contain several hundred thousand cycles. In this work we propose Butramin, a bug trace minimizer. Butramin considers a bug trace produced by a random simulator or a semi-formal verification software and produces an equivalent trace of shorter length. Butramin applies a range of minimization techniques, deploying both simulation-based and formal methods, with the objective of producing highly reduced traces that still expose the original bug. We evaluated Butramin on a range of designs, including the publicly available picoJava microprocessor. Our experiments show that in most cases Butramin is able to reduce traces to a small fraction of their initial size, in terms of cycle length and signals involved.
13199279
Rule-mitigated collaboration framework
Computer supported cooperative work (CSCW) research is the discipline that explores how to utilize computing and networking technologies to facilitate cooperation and collaboration among people. A variety of research has been conducted on CSCW architecture. However, how to ensure CSCW system effectiveness and efficiency on supporting collaboration remains a challenge. In this paper we present a rule mitigated framework for CSCW applications. This research contributes to the state of the art by presenting a robust and comprehensive architecture to support distributed collaboration.
1146148
A Bayes Net Toolkit for Student Modeling in Intelligent Tutoring Systems
This paper describes an effort to model a student's changing knowledge state during skill acquisition. Dynamic Bayes Nets (DBNs) provide a powerful way to represent and reason about uncertainty in time series data, and are therefore well-suited to model student knowledge. Many general-purpose Bayes net packages have been implemented and distributed; however, constructing DBNs often involves complicated coding effort. To address this problem, we introduce a tool called BNT-SM. BNT-SM inputs a data set and a compact XML specification of a Bayes net model hypothesized by a researcher to describe causal relationships among student knowledge and observed behavior. BNT-SM generates and executes the code to train and test the model using the Bayes Net Toolbox [1]. Compared to the BNT code it outputs, BNT-SM reduces the number of lines of code required to use a DBN by a factor of 5. In addition to supporting more flexible models, we illustrate how to use BNT-SM to simulate Knowledge Tracing (KT) [2], an established technique for student modeling. The trained DBN does a better job of modeling and predicting student performance than the original KT code (Area Under Curve = 0.610 > 0.568), due to differences in how it estimates parameters.