An official website of the United States government
This paper considers statistical analysis on noisy datasets where near-duplicate elements need to be treated as identical ones. We focus on two basic problems, distinct elements and ℓ0-sampling, in the data stream model where the sequence of elements can only be scanned once using a limited space, under which a comprehensive data deduplication step before statistical analysis is not feasible. Previous streaming algorithms for these problems could only handle noisy datasets inO(1)-dimensional Euclidean spaces. In this paper, we propose sublinear-space streaming algorithms that work for noisy datasets in any metric space. We also give a lower bound result showing that solving the distinct elements problem on noisy datasets in general metric spaces is inherently more difficult than solving it on noiseless datasets and on noisy datasets inO(1)-dimensional Euclidean spaces.
more »
« less
This content will become publicly available on May 12, 2027
Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity
We propose a novel framework for statistical estimation on noisy datasets. Within this framework, we focus on the frequency moments (Fp) problem and demonstrate that it is possible to approximateFpof the unknown ground-truth dataset using sublinear space in the data stream model and sublinear communication in the coordinator model, provided that the approximation ratio is parameterized by a data-dependent quantity, which we call theFp-mismatch-ambiguity. We also establish a set of lower bounds, which are tight in terms of the input size. Our results yield several interesting insights:-In the data stream model, theFpproblem is inherently more difficult in the noisy setting than in the noiseless one. In particular, whileF2can be approximated in logarithmic space in terms of the input size in the noiseless setting, any algorithm forF2in the noisy setting requires polynomial space. -In the coordinator model, in sharp contrast to the noiseless case, achieving polylogarithmic communication in the input size is generally impossible forFpunder noise. However, when theFpmismatch ambiguity falls below a certain threshold, it becomes possible to achieve communication that is entirely independent of the input size.
more »
« less
- Award ID(s):
- 1844234
- PAR ID:
- 10688797
- Publisher / Repository:
- ACM
- Date Published:
- Journal Name:
- Proceedings of the ACM on Management of Data
- Volume:
- 4
- Issue:
- 2
- ISSN:
- 2836-6573
- Page Range / eLocation ID:
- 1 to 24
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A new lens capability for three-dimensional (3D) focal control is presented using an optofluidic system consisting ofn × narrayed liquid prisms. Each prism module contains two immiscible liquids in a rectangular cuvette. Using the electrowetting effect, the shape of the fluidic interface can be rapidly adjusted to create its straight profile with the prism’s apex angle. Consequently, an incoming ray is steered at the tilted interface due to the refractive index difference between two liquids. To achieve 3D focal control, individual prisms in the arrayed system are simultaneously modulated, allowing incoming light rays to be spatially manipulated and converged on a focal point located atPfocal(fx,fy,fz) in 3D space. Analytical studies were conducted to precisely predict the prism operation required for 3D focal control. Using three liquid prisms positioned on thex-,y-, and 45°-diagonal axes, we experimentally demonstrated 3D focal tunability of the arrayed optofluidic system, achieving focal tuning along lateral, longitudinal, and axial directions as wide as 0 ≤ fx ≤ 30 mm, 0 ≤ fy ≤ 30 mm, and 500 mm ≤ fz ≤ ∞. This focal tunability of the arrayed system allows for 3D control of the lens’s focusing power, which could not be attained by solid-type optics without the use of bulky and complex mechanical moving components. This innovative lens capability for 3D focal control has potential applications in eye-movement tracking for smart displays, autofocusing of smartphone cameras, or solar tracking for smart photovoltaic systems.more » « less
-
In this work, we study the notion ofrepresentation obliviousnessin the context of pseudodeterministic streaming algorithms. A (randomized) streaming algorithm A is pseudodeterministic, if for every stream D, there is a ''canonical value'' g(D) so that with probability at least 2/3, A on input stream D outputs g(D). Intuitively, a randomized algorithm is representation oblivious if the output distribution of the algorithm does not depend on the representation of the input. We investigate this notion in the context of streaming algorithms, more specifically, distinct elements estimation (F0estimation) in data streams. In this context, representation obliviousness captures the idea that the output distribution of an algorithm for estimating F0should only depend on the set of distinct elements of the stream. This is a natural notion, as we note that standard streaming algorithms are representation-oblivious in this sense. We prove that any representation oblivious pseudodeterministic streaming algorithm for estimating F0must use Ω(n) space, where [n] is the universe. More generally, we prove that any representation oblivious pseudodeterministic t(n)-pass streaming algorithm requires Ω(n/t(n)) space. This lower bound matches the space requirement of the straightforward multi-pass deterministic algorithm that exactly computes F0.more » « less
-
This Letter presents a novel, to the best of our knowledge, method to calibrate multi-focus microscopic structured-light three-dimensional (3D) imaging systems with an electrically adjustable camera focal length. We first leverage the conventional method to calibrate the system with a reference focal lengthf0. Then we calibrate the system with other discrete focal lengthsfiby determining virtual features on a reconstructed white plane usingf0. Finally, we fit the polynomial function model using the discrete calibration results forfi. Experimental results demonstrate that our proposed method can calibrate the system consistently and accurately.more » « less
-
We consider the formulation of a symbolic execution (SE) procedure for functional programs that interact with effectful, opaque libraries. Our procedure allows specifications of libraries and abstract data type (ADT) methods that are expressed inLinear Temporal Logic over Finite Traces(LTLf), interpreting them assymbolic finite automata(SFAs) to enable intelligent specification-guided path exploration in this setting. We apply our technique to facilitate the falsification of complex data structure safety properties in terms of effectful operations made by ADT methods on underlying opaque representation type(s). Specifications naturally characterize admissible traces of temporally-ordered events that ADT methods (and the library methods they depend upon) are allowed to perform. We show how to use these specifications to construct feasible symbolic input states for the corresponding methods, as well as how to encode safety properties in terms of this formalism. More importantly, we incorporate the notion ofsymbolic derivatives, a mechanism that allows the SE procedure to intelligently underapproximate the set of precondition states it needs to explore, based on the automata structures latent in the provided specifications and the safety property that is to be falsified. Intuitively, derivatives enable symbolic execution to exploit temporal constraints defined by trace-based specifications to quickly prune unproductive paths and discover feasible error states. Experimental results on a wide-range of challenging ADT implementations demonstrate the effectiveness of our approach.more » « less
