The ramification problem in temporal databases: an approach with conflicting constraints

In this paper we study the ramification problem in the setting of temporal databases. Standard solutions from the literature on reasoning about action are inadequate because they rely on the assumption that fluents persist, and because actions have effects on the next situation only. In this paper we provide a solution to the ramification problem based on an extension of the situation calculus and the work of McCain and Turner. More specifically, we study the case where there are conflicting effects of an action, a particularly complex problem. Also we present a tool which implements the proposed solution.     

Nearest neighbor estimate of conditional mutual information in feature selection

Mutual information (MI) is used in feature selection to evaluate two key-properties of optimal features, the relevance of a feature to the class variable and the redundancy of similar features. Conditional mutual information (CMI), i.e., MI of the candidate feature to the class variable conditioning on the features already selected, is a natural extension of MI but not so far applied due to estimation complications for high dimensional distributions. We propose the nearest neighbor estimate of CMI, appropriate for high-dimensional variables, and build an iterative scheme for sequential feature selection with a termination criterion, called CMINN. We show that CMINN is equivalent to feature selection MI filters, such as mRMR and MaxiMin, in the presence of solely single feature effects, and more appropriate for combined feature effects. We compare CMINN to mRMR and MaxiMin on simulated datasets involving combined effects and confirm the superiority of CMINN in selecting the correct features (indicated also by the termination criterion) and giving best classification accuracy. The application to ten benchmark databases shows that CMINN obtains the same or higher classification accuracy compared to mRMR and MaxiMin at a smaller cardinality of the selected feature subset.     

Star-like auto-configurable layouts of variable radius for visualizing and exploring RDF/S ontologies

The visualization of ontologies is a challenging task especially if they are large. In this paper we propose a visualization approach which is based on star-like graphs of variable radius which enables users to gradually explore and navigate through the entire ontology without overloading them. The star-like graphs are visualized using a Force Directed Placement algorithm (FDP) specially suited for RDF schemas whose configuration parameters can be adjusted interactively by the end-user via an intuitive on-screen tool bar. In addition, and since each star-like graph exhibits different graph features, we propose a novel automatic configuration method for the FDP algorithm parameters that is based on a number of quality metrics (area density and verticality of subclass hierarchies) and corresponding corrective actions. The experimental evaluation showed the quality of the yielded layout is significantly improved and the proposed approach is acceptably fast for real-time exploration. The user study showed that users prefer these views and perform various very common tasks faster.     

Estimation of linear trend onset in time series

We propose a method to detect the onset of linear trend in a time series and estimate the change point T from the profile of a linear trend test statistic, computed on consecutive overlapping time windows along the time series. We compare our method to two standard methods for trend change detection and evaluate them with Monte Carlo simulations for different time series lengths, autocorrelation strengths, trend slopes and distribution of residuals. The proposed method turns out to estimate T better for small and correlated time series. The methods were also applied to global temperature records suggesting different turning points.     

Incremental model-based estimation using geometric constraints

We present a model-based framework for incremental, adaptive object shape estimation and tracking in monocular image sequences. Parametric structure and motion estimation methods usually assume a fixed class of shape representation (splines, deformable superquadrics, etc.) that is initialized prior to tracking. Since the model shape coverage is fixed a priori, the incremental recovery of structure is decoupled from tracking, thereby limiting both processes in their scope and robustness. In this work, we describe a model-based framework that supports the automatic detection and integration of low-level geometric primitives (lines) incrementally. Such primitives are not explicitly captured in the initial model, but are moving consistently with its image motion. The consistency tests used to identify new structure are based on trinocular constraints between geometric primitives. The method allows not only an increase in the model scope, but also improves tracking accuracy by including the newly recovered features in its state estimation. The formulation is a step toward automatic model building, since it allows both weaker assumptions on the availability of a prior shape representation and on the number of features that would otherwise be necessary for entirely bottom-up reconstruction. We demonstrate the proposed approach on two separate image-based tracking domains, each involving complex 3D object structure and motion.     

Efficient Management of Persistent Knowledge

Although computer speed has steadily increased and memory is getting cheaper, the need for storage managers to deal efficiently with applications that cannot be held into main memory is vital. Dealing with large quantities of clauses implies the use of persistent knowledge and thus, indexing methods are essential to access efficiently the subset of clauses relevant to answering a query. We introduce PerKMan, a storage manager that uses G-trees, and aims at efficient manipulation of large amounts of persistent knowledge. PerKMan may be connected to Prolog systems that offer an external C language interface. As well as the fact that the storage manager allows different arguments of a predicate to share a common index dimension in a novel manner, it indexes rules and facts in the same manner. PerKMan handles compound terms efficiently and its data structures adapt their shape to large dynamic volumes of clauses, no matter what the distribution. The storage manager achieves fast clause retrieval and reasonable use of disk space.