In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An curve is sequence uncertainty regions, where each region disk, line segment, or set points. A realisation polyline connecting one point from region. Given an second (certain uncertain) curve, seek to compute lower upper bound distance, which are minimum maximum any realisations We prove that both problems NP-hard in several models, problem remains hard...

We study the problem of merging decision trees: Given k trees $T_1,T_2,T_3...,T_k$, we merge these into one super tree T with (often) much smaller size. The resultant T, which is an integration each leaf having a major label, can also be considered as (lossless) compression random forest. For any testing instance, it guaranteed that gives same prediction forest consisting $T_1,T_2,T_3...,T_k$ but saves computational effort needed for traversing multiple trees. proposed method suitable...

Data about individuals may contain private and sensitive information. The differential privacy (DP) was proposed to address the problem of protecting each individual while keeping useful information a population. Sealfon [1] introduced graph model in which topology is assumed be public weight private. That can express hidden congestion patterns known transportation system. In this paper, we revisit privately releasing approximate distances between all pairs vertices [1]. Our goal minimize...

Skyline queries are important in many application domains. In this paper, we propose a novel structure Diagram, which given set of points, partitions the plane into regions, referred to as skyline polyominos. All query points same polyomino have results. Similar kth-order Voronoi diagram commonly used facilitate k nearest neighbor (kNN) queries, can be and other applications. However, it may computationally expensive build diagram. By exploiting some interesting properties skyline, present...

The genomic scaffold filling problem has attracted a lot of attention recently. is on an incomplete sequence (scaffold) I into I', with respect to complete reference genome G, such that the number adjacencies between G and I' maximized. NP-complete APX-hard, admits 1.2-approximation. However, input not quite practical does fit most real datasets (where more often given as list contigs). In this paper, we revisit by considering important case when, (1) S given, missing genes X = c(G) - c(S)...

In normal Voronoi diagram, each site is able to see all points in the plane. this paper, we study problem such that only half-plane and construct so-called Half-plane Diagram (HPVD). We show cell of not necessary convex it could consist many disjoint regions. prove complexity HPVD n sites $O(n^2)$. Then give an algorithm $O(n\log n)$ time $O(n)$ space boundary lines half-planes are parallel visible same side corresponding lines. For where be either lines, $O(n^2)$ HPVD.

In a normal Voronoi diagram, each site is able to see all the points in plane. this paper, we study case such that only visually restricted region plane and construct so-called Visual Restriction Diagram (VRVD). We show visual restriction cell of not necessarily convex it could consist many disjoint regions. prove combinatorial complexity VRVD on n sites Θ(n2), then can be constructed O(n2) time space. Besides that, also give another algorithm with an extra log factor running compute VRVD,...

Many modern data analysis algorithms either assume or are considerably more efficient if the distances between points satisfy a metric. These include metric learning, clustering, and dimension reduction. As real sets noisy, often fail to For this reason, Gilbert Jain Fan et al. introduced closely related sparse repair violation distance problems. The goal of these problems is as few possible ensure they Three variants were considered, one admitting polynomial time algorithm. other shown be...

The Chain Pair Simplification problem (CPS) was posed by Bereg et al. who were motivated the of efficiently computing and visualizing structural resemblance between a pair protein backbones. In this problem, given two polygonal chains lengths n m, goal is to simplify both them simultaneously, so that resulting simplifications as well discrete Frechet distance are bounded. When vertices arbitrary (i.e., not necessarily from original chains), called General CPS (GCPS). In paper we consider...

Releasing all pairwise shortest path (APSP) distances between vertices on general graphs under weight Differential Privacy (DP) is known as a challenging task. In the previous attempt of (Sealfon 2016}, by adding Laplace noise to each edge or output distance, achieve DP with some fixed budget, high probability maximal absolute error among published roughly $O(n)$ where $n$ number nodes. It was shown that this could be reduced for special graphs, which, however, hard graphs. Therefore,...

Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate automated labelling and many more. In the correlation one receives as input set of nodes for each node list co-clustering preferences, goal to output that minimizes disagreement specified nodes' preferences. this paper, we introduce simple computationally efficient algorithm provable privacy guarantees. Our approximation guarantees are stronger than those shown...

Given $x\in(\mathbb{R}_{\geqslant 0})(_{2}^{[n]})$ recording pairwise distances, the Metric Violation Distance problem asks to compute $\ell_{0}$ distance between x and metric cone; i.e., modify minimum number of entries make it a metric. Due its large applications in various data analysis optimization tasks, this has been actively studied recently. We present an $O(\log n)$-approximation algorithm for METRIC VIOLATION Distance, exponentially improving previous best approximation ratio...