Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Inverse procedural modeling of 3D models for virtual worlds
2016
This course presents a collection of state-of-the-art approaches for modeling and editing of 3D models for virtual worlds, simulations, and entertainment, in addition to real-world applications. The first contribution of this course is a coherent review of inverse procedural modeling (IPM) (i.e., proceduralization of provided 3D content). We describe different formulations of the problem as well as solutions based on those formulations. We show that although the IPM framework seems under-constrained, the state-of-the-art solutions actually use simple analogies to convert the problem into a set of fundamental computer science problems, which are then solved by corresponding algorithms or opt…
Dynamic network identification from non-stationary vector autoregressive time series
2018
Learning the dynamics of complex systems features a large number of applications in data science. Graph-based modeling and inference underpins the most prominent family of approaches to learn complex dynamics due to their ability to capture the intrinsic sparsity of direct interactions in such systems. They also provide the user with interpretable graphs that unveil behavioral patterns and changes. To cope with the time-varying nature of interactions, this paper develops an estimation criterion and a solver to learn the parameters of a time-varying vector autoregressive model supported on a network of time series. The notion of local breakpoint is proposed to accommodate changes at individu…
Online Topology Identification from Vector Autoregressive Time Series
2019
Causality graphs are routinely estimated in social sciences, natural sciences, and engineering due to their capacity to efficiently represent the spatiotemporal structure of multivariate data sets in a format amenable for human interpretation, forecasting, and anomaly detection. A popular approach to mathematically formalize causality is based on vector autoregressive (VAR) models and constitutes an alternative to the well-known, yet usually intractable, Granger causality. Relying on such a VAR causality notion, this paper develops two algorithms with complementary benefits to track time-varying causality graphs in an online fashion. Their constant complexity per update also renders these a…
Design of Multiresolution Operators Using Statistical Learning Tools: Application to Compression of Signals
2012
Using multiresolution based on Harten's framework [J. Appl. Numer. Math., 12 (1993), pp. 153---192.] we introduce an alternative to construct a prediction operator using Learning statistical theory. This integrates two ideas: generalized wavelets and learning methods, and opens several possibilities in the compressed signal context. We obtain theoretical results which prove that this type of schemes (LMR schemes) are equal to or better than the classical schemes. Finally, we compare traditional methods with the algorithm that we present in this paper.
A Novel Approach to Introducing Adaptive Filters Based on the LMS Algorithm and Its Variants
2004
This paper presents a new approach to introducing adaptive filters based on the least-mean-square (LMS) algorithm and its variants in an undergraduate course on digital signal processing. Unlike other filters currently taught to undergraduate students, these filters are nonlinear and time variant. This proposal introduces adaptive filtering in the context of a linear time-invariant system using a real problem. In this way, introducing adaptive filters using concepts already familiar to the students motivates their interest through practical application. The key point for this simplification is that the input to the filter is constant so that the adaptive filter becomes linear. Therefore, a …
Optimisation des requêtes de similarité dans les espaces métriques répondant aux besoins des usagers
2012
The complexity of data stored in large databases has increased at very fast paces. Hence, operations more elaborated than traditional queries are essential in order to extract all required information from the database. Therefore, the interest of the database community in similarity search has increased significantly. Two of the well-known types of similarity search are the Range (Rq) and the k-Nearest Neighbor (kNNq) queries, which, as any of the traditional ones, can be sped up by indexing structures of the Database Management System (DBMS). Another way of speeding up queries is to perform query optimization. In this process, metrics about data are collected and employed to adjust the par…
Obtaining the Compatibility between Musicians Using Soft Computing
2010
Modeling the musical notes as fuzzy sets provides a flexible framework which better explains musicians’ daily practices. Taking into account one of the characteristics of the sound: the pitch (the frequency of a sound as perceived by human ear), a similarity relation between two notes can be defined. We call this relation compatibility. In the present work, we propose a method to asses the compatibility between musicians based on the compatibility of their interpretations of a given composition. In order to aggregate the compatibilities between the notes offered and then obtain the compatibility between musicians, we make use of an OWA operator. We illustrate our approach with a numerical e…
Social Media Data in an Augmented Reality System for Situation Awareness Support in Emergency Control Rooms
2021
AbstractDuring crisis situations, emergency operators require fast information access to achieve situation awareness and make the best possible decisions. Augmented reality could be used to visualize the wealth of user-generated content available on social media and enable context-adaptive functions for emergency operators. Although emergency operators agree that social media analytics will be important for their future work, it poses a challenge to filter and visualize large amounts of social media data. We conducted a goal-directed task analysis to identify the situation awareness requirements of emergency operators. By collecting tweets during two storms in Germany we evaluated the usefu…
GSWABE: faster GPU-accelerated sequence alignment with optimal alignment retrieval for short DNA sequences
2014
In this paper, we present GSWABE, a graphics processing unit GPU-accelerated pairwise sequence alignment algorithm for a collection of short DNA sequences. This algorithm supports all-to-all pairwise global, semi-global and local alignment, and retrieves optimal alignments on Compute Unified Device Architecture CUDA-enabled GPUs. All of the three alignment types are based on dynamic programming and share almost the same computational pattern. Thus, we have investigated a general tile-based approach to facilitating fast alignment by deeply exploring the powerful compute capability of CUDA-enabled GPUs. The performance of GSWABE has been evaluated on a Kepler-based Tesla K40 GPU using a varie…
A distributed-memory MPI parallelization scheme for multi-domain incompressible SPH
2022
A parallel scheme for a multi-domain truly incompressible smoothed particle hydrodynamics (SPH) approach is presented. The proposed method is developed for distributed-memory architectures through the Message Passing Interface (MPI) paradigm as communication between partitions. The proposal aims to overcome one of the main drawbacks of the SPH method, which is the high computational cost with respect to mesh-based methods, by coupling a multi-resolution approach with parallel computing techniques. The multi-domain approach aims to employ different resolutions by subdividing the computational domain into non-overlapping blocks separated by block interfaces. The particles belonging to differe…