In real life, data are often of poor quality as a result, for instance, of uncertainty, mismeasurements, missing values or bad inputs. This issue hampers an implicit yet crucial operation of every database management system: equality testing. ...

Dietze's conjecture concerns the problem of equipping a tree automaton M with weights to make it probabilistic, in such a way that the resulting automaton N predicts a given corpus C as accurately as possible. The conjecture states that the ...

We consider Internet of Things (IoT) sensors deployed inside an area to be monitored. Drones can be used to collect the data from the sensors, but they are constrained in energy and storage. Therefore, all drones need to select a subset of ...

Many Internet protocol (IP) lookup algorithms have been formulated to improve network performance. This study reviewed and experimentally evaluated technologies for trie-based methods that reduce memory access, memory consumption and ...

Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using O ( 1 ) bits per node can break this bound on clustered point sets, while ...

Cloud service for data outsourcing has triggered security and privacy needs that can be satisfied by encrypting data prior to outsourcing to the cloud. Searchable Encryption that uses methods like homomorphic encryption is inefficient ...

The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space ...

We give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with O ˜ ( n 4 / 5 ) worst-case update time and O ( log 2 ⁡ n ) query time. Here, a single update can either change the graph by inserting ...

Truth Discovery is an important learning problem arising in data analytics related fields. It concerns about finding the most trustworthy information from a dataset acquired from a number of unreliable sources. The ...

A robot game, also known as a Z-VAS game, is a two-player vector addition game played on the integer lattice Z n, where one of the players, Adam, aims to avoid the origin while the other player, Eve, aims to reach the origin. The ...

Analyzing pseudo-telepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures generating equivalent scenarios. We introduce a new ...

Symmetric queries are introduced as queries on a sequence of sets of objects the result of which does not depend on the order of the sets. An appropriate data model is proposed, and two query languages are introduced, ...

Most modern libraries for regular expression matching allow back-references (i.e., repetition operators) that substantially increase expressive power, but also lead to intractability. In order to find a better balance between ...

We study monadic second-order logics with counting constraints (CMso) for unordered data trees. Our objective is to enhance this logic with data constraints for comparing string data values. Comparisons between data values at arbitrary ...

DNA sequencing technologies have tremendously increased their throughput, and hence complicated DNA assembly. Numerous assembly programs use de Bruijn graphs (dBG) built from short reads to merge these into contigs, which represent ...

The traditional collaborative filtering (CF) suffers from two key challenges, namely, the normal assumption that it is not robust, and it is difficult to set in advance the penalty terms of the latent features. We therefore propose a hierarchical ...

• The Gamma-Gaussian assumption on the ratings. It is a heavy tail distribution so the model is more robust.
• The Gamma-Gaussian assumption on the latent features. Hence we do not need to specify the regularization term manually.
• The ...

Cloud computing gathers a lot of computing resources together, and provides cheap, efficient and convenient services. With the development of cloud computing, the importance of security issues is increasing. Modular exponentiations are one of the basic ...

Many cryptographic protocols were developed to support efficient group membership operations. Although those schemes can be extensively used for controlling temporary access with guest devices which do occur in many real world situations, those schemes ...

Driven by the SQL standard, we investigate simple and partial inclusion dependencies (INDs) with not null constraints. Implication of simple INDs and not null constraints is not finitely axiomatizable. We propose not null inclusion dependencies (NNINDs) ...

This article proposes a new algorithm that improves the complexity bound for solving parity games. Our approach combines McNaughton's iterated fixed point algorithm with a preprocessing step, which is called prior to every recursive call. The ...