10594579
Hard Queries can be Addressed with Query Splitting Plus Stepping Stones and Pathways
A key finding of the Reliable Information Access Workshop of 2003 was that in collections like those used for TREC 6-8, there are a number of hard queries for which no current search engine can return a high quality set of results. Our Stepping Stones and Pathways (SSP) approach may yield an effective solution to such hard problems, as well as support exploration of collections of content not well known to a person (with broad interest and/or complex information needs). Our initial and promising testing of SSP had users prepare two separate short queries in order to launch processing. However, since beginning with a single information need is a more typical initial situation, we have extended the SSP research by exploring query splitting, especially as might apply to handling hard queries. This paper summarizes our recent results and identifies some of the future work needed.
2329429
Embodied data objects: tangible interfaces to information appliances
This paper describes the idea of embodied data objects. Using this concept, everyday objects can be used to represent bits and bytes of active information. These data objects can be used to interact with information-appliance-like devices that provide specific services as dictated by the context of interaction. The inherent affordances of physical artifacts are leveraged to make the interaction with these service-oriented devices intuitive and natural. We describe the idea of embodied data objects, followed by the design and implementation of two such service-oriented devices: a presentation projector and a printer.
7732726
Towards a syllabus repository for computer science courses
A syllabus defines the contents of a course, as well as other information such as resources and assignments. In this paper, we report on our work towards creating a syllabus repository of Computer Science courses across universities in the USA. We present some statistics from our initial collection of 8000+ syllabi. We show a syllabus creator that is integrated with Moodle [5] moodle_2006_moodle, an open-source course management system, which allows for the creation of a syllabus for a particular course. Among other information, it includes knowledge units from the Computing Curricula 2001 body of knowledge. The goal of the syllabus repository is to provide added value to the Computer Science Education community, and we present some such offerings. We conclude by presenting our future plans for the syllabus repository. These include using automated techniques to collect and classify syllabi, providing recommendations to instructors when creating a syllabus, and allowing the community to share their syllabi automatically. The syllabus collection will be part of the Computing and Information Technology Interactive Digital Educational Library (CITIDEL), a collection of the National Science Digital Library (NSDL).
26301648
Data Integrity Framework and Language Support for Active Web Intermediaries
With the maturity of content adaptation technologies (such as I-CAP and OPES) in web intermediaries and of content personalization in the network, data integrity has already become a key concern when such technologies are deployed. To address this issue, we propose a data integrity framework with the following functionalities: (i) a server can specify its authorizations, (ii) active web intermediaries can provide value-added services in accordance with the server’s intentions, and more importantly, (iii) a client is facilitated to verify the received message with the server’s authorizations and intermediaries’ footprints. With the actual implementation of our data integrity framework in web (content and proxy) servers and clients, we show the feasibility and practicability of our proposed design through its low performance overhead and possible data (re)use.
24026
4-Connected Projective-Planar Graphs Are Hamiltonian
We prove the result stated in the title (conjectured by Grunbaum) and a conjecture of Plummer that every graph which can be obtained from a 4-connected planar graph by deleting two vertices is Hamiltonian. The proofs are constructive and give rise to polynomial-time algorithms.
18288842
Finding Four Independent Trees
Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an $O(|V|^2)$ algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an $O(|V|^3)$ algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs.
7132341
HASE: A Hybrid Approach to Selectivity Estimation for Conjunctive Predicates
Current methods for selectivity estimation fall into two broad categories, synopsis-based and sampling-based. Synopsis-based methods, such as histograms, incur minimal overhead at query optimization time and thus are widely used in commercial database systems. Sampling-based methods are more suited for ad-hoc queries, but often involve high I/O cost because of random access to the underlying data. Though both methods serve the same purpose of selectivity estimation, their interaction in the case of selectivity estimation for conjuncts of predicates on multiple attributes is largely unexplored. Our work aims at taking the best of both worlds, by making consistent use of synopses and sample information when they are both present. To achieve this goal, we propose HASE, a novel estimation scheme based on a powerful mechanism called generalized raking. We formalize selectivity estimation in the presence of single attribute synopses and sample information as a constrained optimization problem. By solving this problem, we obtain a new set of weights associated with the sampled tuples, which has the nice property of reproducing the known selectivities when applied to individual predicates. We discuss different variants of the optimization problem and provide algorithms for solving it. We also provide asymptotic error bounds on the estimate. Extensive experiments are performed on both synthetic and real data, and the results show that HASE significantly outperforms both synopsis-based and sampling-based methods.
13571183
Chain Decompositions of 4-Connected Graphs
In this paper we give a decomposition of a $4$-connected graph $G$ into nonseparating chains, which is similar to an ear decomposition of a $2$-connected graph. We also give an $O(|V(G)|^2|E(G)|)$ algorithm that constructs such a decomposition. In applications, the asymptotic performance can often be improved to $O(|V(G)|^3)$. This decomposition will be used to find four independent spanning trees in a $4$-connected graph.
13475547
Towards estimating the number of distinct value combinations for a set of attributes
Accurately and efficiently estimating the number of distinct values for some attribute(s) or sets of attributes in a data set is of critical importance to many database operations, such as query optimization and approximation query answering. Previous work has focused on the estimation of the number of distinct values for a single attribute and most existing work adopts a data sampling approach. This paper addresses the equally important issue of estimating the number of distinct value combinations for multiple attributes which we call COLSCARD (for COLumn Set CARDinality). It also takes a different approach that uses existing statistical information (e.g., histograms) available on the individual attributes to assist estimation. We start with cases where exact frequency information on individual attributes is available, and present a pair of lower and upper bounds on COLSCARD that are consistent with the available information, as well as an estimator of COLSCARD based on probability. We then proceed to study the case where only partial information (in the form of histograms) is available on individual attributes, and show how the proposed estimator can be adapted to this case. We consider two types of widely used histograms and show how they can be constructed in order to obtain optimal approximation. An experimental evaluation of the proposed estimation method on synthetic as well as two real data sets is provided.