311 research outputs found
SERGEANT: A Framework for Building More Flexible Web Agents by Exploiting a Search Engine
No full textLearning Database Abstractions For Query Reformulation
No full textions For Query Reformulation Chun-Nan Hsu Craig A. Knoblock Department of Computer Science Information Sciences Institute University of Southern California University of Southern California Los Angeles, CA 90089-0782 4676 Admiralty Way (213) 740-9328 Marina del Rey, CA 90292 [email protected] (310) 822-1511 [email protected] Abstract The query reformulation approach (also called semantic query optimization) takes advantage of the semantic knowledge about the contents of databases for optimization. The basic idea is to use the knowledge to reformulate a query into a less expensive yet equivalent query. Previous work on semantic query optimization has shown the cost reduction that can be achieved by reformulation, we further point out that when applied to distributed multidatabase queries, the reformulation approach can reduce the cost of moving intermediate data from one site to another. However, a robust and efficient method to discover the required knowledge has not yet been develo..
Interoperation in Complex Information Ecosystems (Dagstuhl Seminar 13252)
No full textThis report documents the program and the outcomes of Dagstuhl Seminar 13252 "Interoperation in Complex Information Ecosystems"
Flexible and scalable cost-based query planning in mediators: A transformational approach
No full textAbstractThe Internet provides access to a wealth of information. For any given topic or application domain there are a variety of available information sources. However, current systems, such as search engines or topic directories in the World Wide Web, offer only very limited capabilities for locating, combining, and organizing information. Mediators, systems that provide integrated access and database-like query capabilities to information distributed over heterogeneous sources, are critical to realize the full potential of meaningful access to networked information.Query planning, the task of generating a cost-efficient plan that computes a user query from the relevant information sources, is central to mediator systems. However, query planning is a computationally hard problem due to the large number of possible sources and possible orderings on the operations to process the data. Moreover, the choice of sources, data processing operations, and their ordering, strongly affects the plan cost.In this paper, we present an approach to query planning in mediators based on a general planning paradigm called Planning by Rewriting (PbR) (Ambite and Knoblock, 1997). Our work yields several contributions. First, our PbR-based query planner combines both the selection of the sources and the ordering of the operations into a single search space in which to optimize the plan quality. Second, by using local search techniques our planner explores the combined search space efficiently and produces high-quality plans. Third, because our query planner is an instantiation of a domain-independent framework it is very flexible and can be extended in a principled way. Fourth, our planner has an anytime behavior. Finally, we provide empirical results showing that our PbR-based query planner compares favorably on scalability and plan quality over previous approaches, which include both classical AI planning and dynamic-programming query optimization techniques
Learning Plan Rewriting Rules
No full textPlanning by Rewriting (PbR) is a new paradigm for efficient high-quality planning that exploits plan rewriting rules and efficient local search techniques to transform an easy-to-generate, but possibly suboptimal, initial plan into a high-quality plan. Despite the advantages of PbR in terms of scalability, plan quality, and anytime behavior, PbR requires the user to define a set of domain-specific plan rewriting rules which can be difficult and time-consuming. This paper presents an approach to automatically learning the plan rewriting rules based on comparing initial and optimal plans. We report results for several planning domains showing that the learned rules are competitive with manually-specified ones, and in several cases the learning algorithm discovered novel rewriting rules. Introduction Planning by Rewriting (PbR) (Ambite & Knoblock 1997; 1998; Ambite 1998) is a planning framework that has shown better scalability than other domainindependent approaches. In a..
A Mixed-Initiative System for Building Mixed-Initiative Systems
No full textMixed-initiative assistants can be applied to a variety of information-rich problem-solving tasks on the Web, such as travel planning and equipment purchasing tasks. A mixed-initiative environment for such tasks can greatly improve the decision making environment for a user if the application is designed to meet the needs of a user. However, each user has different needs and preferences, making it difficult to design a single application for all users. Thus, we are applying the mixed-initiative paradigm recursively to develop a mixed-initiative system for building mixed-initiative systems. This paper describes the basic framework for constructing mixedinitiative systems, which is based on our previous work on developing mixed-initiative information assistants in Heracles. The new system, called Alcmene, will be implemented as an application of Heracles and will allow a user to author a new Heracles application through a mixed-initiative problem-solving process
Planning, Executing, Sensing, and Replanning for Information Gathering
No full textCurrent specialized planners for query processing are designed to work in local, reliable, and predictable environments. However, a number of problems arise in gathering information from large networks of distributed information. In this environment, the same information may reside in multiple places, actions can be executed in parallel to exploit distributed resources, new goals come into the system during execution, actions may fail due to problems with remote databases or networks, and sensing may need to be interleaved with planning in order to formulate efficient queries. We have developed a planner called Sage that addresses the issues that arise in this environment. This system integrates previous work on planning, execution, replanning, and sensing and extends this work to support simultaneous and interleaved planning and execution. Sage has been applied to the problem of information gathering to provide a flexible and efficient system for integrating heterogeneou..
Generating Parallel Execution Plans with a Partial-Order Planner
No full textMany real-world planning problems require generating plans that maximize the parallelism inherent in a problem. There are a number of partial-order planners that generate such plans; however, in most of these planners it is unclear under what conditions the resulting plans will be correct and whether the planner can even find a plan if one exists. This paper identifies the underlying assumptions about when a partial plan can be executed in parallel, defines the classes of parallel plans that can be generated by different partialorder planners, and describes the changes required to turn ucpop into a parallel execution planner. In addition, we describe how this planner can be applied to the problem of query access planning, where parallel execution produces substantial reductions in overall execution time. Introduction There are a wide variety of problems that require generating parallel execution plans. Partial-order planners have been widely viewed as an effective approach to generati..
On robust interpretation of topological relations in identity and tolerance models
No full textIn the last few years the amount of available spatial data has
increased both in volume and in heterogeneity, so that dealing
with this huge amount of information has become an interesting
new research challenge. In particular, spatial data are usually
represented through a vector model upon which several spatial
relations have been defined. Such relations represent the basic
tools for querying and manipulating spatial data and their robust
evaluation in a distributed heterogeneous environment is an
important issue to consider for allowing the effective usage of
these data. Among all possible spatial relations, this paper
considers the topological ones, since they are generally provided
by all existing systems and represent the building blocks for the
implementation of other spatial relations. The conditions and the operations needed to make a dataset robust w.r.t. topological interpretations strictly depends on the adopted evaluation model.
This paper considers an environment where two different
evaluation models for topological relations exist, one in which
equality is based on the identity of geometric primitives, and the
other one where a tolerance in equality evaluation is introduced.
Given such premises, the paper proposes a set of rules for
guaranteeing the robustness in both models, and discusses the
applicability of available algorithms of the Snap Rounding family, in order to preserve robustness in case of perturbations
Reformulating Constraint Satisfaction Problems to Improve Scalability
No full textAbstract. Constraint Programming is a powerful approach for modeling and solving many combinatorial problems, scalability, however, remains an issue in practice. Abstraction and reformulation techniques are often sought to overcome the complexity barrier. In this paper we introduce four reformulation techniques that operate on the various components of a Constraint Satisfaction Problem (CSP) in order to reduce the cost of problem solving and facilitate scalability. Our reformulations modify one or more component of the CSP (i.e., the query, variables domains, constraints) and detect symmetrical solutions to avoid generating them. We describe each of these reformulations in the context of CSPs, then evaluate their performance and effects in on the building identification problem introduced by Michalowski and Knoblock [1].
- …
