6781537
Formal Models of Heavy-Tailed Behavior in Combinatorial Search
Recently, it has been found that the cost distributions of randomized backtrack search in combinatorial domains are often heavytailed. Such heavy-tailed distributions explain the high variability observed when using backtrack-style procedures. A good understanding of this phenomenon can lead to better search techniques. For example, restart strategies provide a good mechanism for eliminating the heavy-tailed behavior and boosting the overall search performance. Several state-of-the-art SAT solvers now incorporate such restart mechanisms. The study of heavy-tailed phenomena in combinatorial search has so far been been largely based on empirical data. We introduce several abstract tree search models, and show formally how heavy-tailed cost distribution can arise in backtrack search. We also discuss how these insights may facilitate the development of better combinatorial search methods.
9351295
Looking Algebraically at Tractable Quantified Boolean Formulas
We make use of the algebraic theory that has been used to study the complexity of constraint satisfaction problems, to investigate tractable quantified boolean formulas. We present a pair of results: the first is a new and simple algebraic proof of the tractability of quantified 2-satisfiability; the second is a purely algebraic characterization of models for quantified Horn formulas that were given by Kleine Buning, Subramani, and Zhao, and described proof-theoretically.
958592
Inverse Circumscription
Inverse (or identification) problems involve deciding whether or not an explicitly given set of data points have an implicit description, for instance, in the form of a constraint network. Such problems provide insight into the relationships among various representations of knowledge, which may have differing computational properties. This paper formalizes and studies the inverse circumscription problem, which (roughly speaking) is to decide, given a set of models, if there exists a formula whose circumscription describes the input set.
3576
Collapsibility and Consistency in Quantified Constraint Satisfaction
The concept of consistency has pervaded studies of the constraint satisfiction problem. We introduce two concepts, which are inspired by consistency, for the more general framework of the quantified constraint satisfaction problem (QCSP). We use these concepts to derive, in a uniform fashion, proofs of polynomial-time tractability and corresponding algorithms for certain cases of the QCSP where the types of allowed relations are restricted. We not only unify existing tractability results and algorithms, but also identify new classes of tractable QCSPs.
3121075
Parameterized Compilability
Compilability is a measure of how effectively compilation (or preprocessing) can be applied to knowledge bases specified in a particular knowledge representation formalism; the aim of compilation is to allow for efficient, on-line query processing. A theory of compilability has been established for organizing knowledge representation formalisms according to a scheme of "compilability classes", and bears strong analogies to the classical theory of complexity, which permits the organization of computational problems according to complexity classes. We develop a novel theory of compilability, called parameterized compilability, which incorporates the notion of parameterization as used in parameterized complexity and permits for refined analysis of compilability.
10922325
Quantified Constraint Satisfaction and Bounded Treewidth
Because the constraint satisfaction problem (CSP) is in general intractable, restricted cases of the CSP that are polynomial-time tractable have been heavily sought after. One class of restrictions that has been studied are variable-based restrictions, which concern the interaction among variables. In this paper, we consider the quantified constraint satisfaction problem (QCSP), a framework more general than the CSP. We present a QCSP tractability result arising from variable-based restrictions by giving a polynomial time algorithm for certain classes of QCSP instances having bounded treewidth.
10838244
Streaming SMIL Presentations via a Multimedia Semantic Model
The Synchronized Multimedia Integration Language (SMIL) allows Web designers to design complicated and vivid multimedia presentations in a declarative manner. In this paper, an abstract semantic model called Multimedia Augmented Transition Network (MATN) is used to model the conceptual structure of SMIL, as well as the temporal relations and synchronization control. The advantages of using the MATN model are its simplicity and ease of modification (scalability). Users can easily generate their favorite multimedia presentations using MATNs and render them using the SMIL players. Since the SMIL specification is quite new to the Internet society, the functionality of the players is limited, i.e., they often acquire proprietary platforms or cannot deal with MPEG or RTP media objects. Another contribution of this paper is to propose a novel architecture based on Java JMF technology for tackling with such constraints.
5510684
Robust motion-based image segmentation using fusion
To support real-time tracking of objects in video sequences, there has been considerable effort directed at developing optical flow and general motion-based image segmentation algorithms. The goal is to segment multiple moving objects in the image based on their relative motion. This task can be complicated by the presence of lighting variations. Furthermore, a combination of multiple motions and complex lighting effects can lead to dramatic image variations that may not be adequately accounted for by a single motion-based segmentation algorithm. We propose to fuse the results of multiple motion segmentation algorithms to improve the system robustness. Our approach uses the expectation maximization (EM) algorithm as a fusion engine. It also uses principal components analysis (PCA) to perform dimensionality reduction to improve the performance of the EM algorithm and reduce the processing burden. The performance of the proposed fusion algorithm has been demonstrated in the "smart airbag" application of monitoring occupants in a moving automobile to determine if they are too close to the instrument panel (airbag). Through fusion of the outputs of multiple algorithms we are able to reduce the percentage of pixels missed on the target by 35.
19964958
Near-optimal data allocation over multiple broadcast channels
Data broadcast is known as a scalable way to transmit database items to large client populations through a wireless channel. However, with a large set of items, the expected delay of receiving desired data increases due to the sequential nature of the broadcast channel. One possible solution is to increase the number of available channels and allocate items evenly over these channels, then cyclically broadcast data in each channel. In view of data access skew (the access frequencies of data are usually different), some channels may be reserved exclusively for those few frequently requested items, while the infrequently accessed bulk of data are allocated on other channels. In this paper, an O(N log K) restricted dynamic programming (RDP) algorithm is proposed to partition N items over K channels assuming data access is skewed with the object of minimizing the average expected delay (aed) of clients. To speed up the DP process, for any partition, we predict a possible location which may be very close to the optimal cut by using a low bound as the actual aed for the remaining items. Thus, the number of comparisons in DP can be restricted to a small interval around the predicted cut point. To further reduce the costs in DP, the hierarchical property of optimal solution is adopted. Simulation results show that, the hit rate obtained by RDP is higher than 90% and it also outperforms the existing algorithm 200%. We extend the work of RDP and develop an O(N log N log K) PKR algorithm; simulation results show that the solution is optimal.
15293705
Design and evaluation of a multi-agent collaborative Web mining system
Most existing Web search tools work only with individual users and do not help a user benefit from previous search experiences of others. In this paper, we present the Collaborative Spider, a multi-agent system designed to provide post-retrieval analysis and enable across-user collaboration in Web search and mining. This system allows the user to annotate search sessions and share them with other users. We also report a user study designed to evaluate the effectiveness of this system. Our experimental findings show that subjects' search performance was degraded, compared to individual search scenarios in which users had no access to previous searches, when they had access to a limited number (e.g., 1 or 2) of earlier search sessions done by other users. However, search performance improved significantly when subjects had access to more search sessions. This indicates that gain from collaboration through collaborative Web searching and analysis does not outweigh the overhead of browsing and comprehending other users' past searches until a certain number of shared sessions have been reached. In this paper, we also catalog and analyze several different types of user collaboration behavior observed in the context of Web mining.
1567676
Bringing order to the Web: automatically categorizing search results
We developed a user interface that organizes Web search results into hierarchical categories. Text classification algorithms were used to automatically classify arbitrary search results into an existing category structure on-the-fly. A user study compared our new category interface with the typical ranked list interface of search results. The study showed that the category interface is superior both in objective and subjective measures. Subjects liked the category interface much better than the list interface, and they were 50% faster at finding information that was organized into categories. Organizing search results allows users to focus on items in categories of interest rather than having to browse through all the results sequentially.