DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2020.63

Sketched MinDist

Authors: Jeff M. Phillips and Pingfan Tang

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

We sketch geometric objects J as vectors through the MinDist function, setting the i-th coordinate v_i(J) = inf_{p ∈ J} ‖p-q_i‖ for q_i ∈ Q from a point set Q. Building a vector from these coordinate values induces a simple, effective, and powerful distance: the Euclidean distance between these sketch vectors. This paper shows how large this set Q needs to be under a variety of shapes and scenarios. For hyperplanes we provide direct connection to the sensitivity sampling framework, so relative error can be preserved in d dimensions using |Q| = O(d/ε²). However, for other shapes, we show we need to enforce a minimum distance parameter ρ, and a domain size L. For d=2 the sample size Q then can be Õ((L/ρ) ⋅ 1/ε²). For objects (e.g., trajectories) with at most k pieces this can provide stronger for all approximations with Õ((L/ρ)⋅ k³ / ε²) points. Moreover, with similar size bounds and restrictions, such trajectories can be reconstructed exactly using only these sketch vectors. Cumulatively, these results demonstrate that these MinDist sketch vectors provide an effective and efficient shape model, a compact representation, and a precise representation of geometric objects.

Cite as

Jeff M. Phillips and Pingfan Tang. Sketched MinDist. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{phillips_et_al:LIPIcs.SoCG.2020.63,
  author =	{Phillips, Jeff M. and Tang, Pingfan},
  title =	{{Sketched MinDist}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{63:1--63:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.63},
  URN =		{urn:nbn:de:0030-drops-122218},
  doi =		{10.4230/LIPIcs.SoCG.2020.63},
  annote =	{Keywords: curve similarity, sensitivity sampling, sketching}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2018.16

Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data

Authors: Kevin Buchin, Jeff M. Phillips, and Pingfan Tang

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract

Robust estimators, like the median of a point set, are important for data analysis in the presence of outliers. We study robust estimators for locationally uncertain points with discrete distributions. That is, each point in a data set has a discrete probability distribution describing its location. The probabilistic nature of uncertain data makes it challenging to compute such estimators, since the true value of the estimator is now described by a distribution rather than a single point. We show how to construct and estimate the distribution of the median of a point set. Building the approximate support of the distribution takes near-linear time, and assigning probability to that support takes quadratic time. We also develop a general approximation technique for distributions of robust estimators with respect to ranges with bounded VC dimension. This includes the geometric median for high dimensions and the Siegel estimator for linear regression.

Cite as

Kevin Buchin, Jeff M. Phillips, and Pingfan Tang. Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2018.16,
  author =	{Buchin, Kevin and Phillips, Jeff M. and Tang, Pingfan},
  title =	{{Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.16},
  URN =		{urn:nbn:de:0030-drops-87292},
  doi =		{10.4230/LIPIcs.SoCG.2018.16},
  annote =	{Keywords: Uncertain Data, Robust Estimators, Geometric Median, Tukey Median}
}

Search Results

Documents authored by Tang, Pingfan

Sketched MinDist

Abstract

Cite as

Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data

Abstract

Cite as

Thanks for your feedback!

Could not send message