Improved privacy for heavy-hitters detection.
problem Private detection of heavy-hitters in dynamic data.
method New algorithm for privately identifying heavy-hitters.
result Improved error guarantees over existing techniques.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
9 results for “heavy-hitters”
In many applications that involve processing high-dimensional data, it is important to identify a small set of entities that account for a significant fraction of detections. Rather than formalize this as a clustering problem, in which all detections must be grouped into hard or soft categories, we formalize it as an i…
Estimates heavy hitters in data streams with queries, balancing accuracy and efficiency.
problem Identifying elements with high probability in i.i.d. samples.
method Sequential estimation algorithms for two query models: index and pair queries.
result Upper and lower bounds on query complexity for different distributions and noise models.
A very simple event frequency approximation algorithm that is sensitive to event timeliness is suggested. The algorithm iteratively updates categorical click-distribution, producing (path of) a random walk on a standard -dimensional simplex. Under certain conditions, this random walk is self-similar and corresponds …
New sketches for weighted sampling without replacement improve accuracy and efficiency.
problem Efficiently sampling weighted data with high accuracy and minimal redundancy.
method Design of novel composable sketches for WOR sampling, based on CountSketch.
result First to provide WOR sampling for and signed updates.
Deconvoluting Kernel Density Estimation and Regression for Locally Differentially Private Datamath.ST
Paper tackles privacy-preserving data density issues using deconvolution.
problem Privacy-preserving noise affects data density, leading to under/over-estimation.
method Develops deconvoluting kernel density estimators and regression models.
result Demonstrates improved accuracy in estimating heavy-hitters with locally differential data.
Extracting information from electronic health records (EHR) is a challenging task since it requires prior knowledge of the reports and some natural language processing algorithm (NLP). With the growing number of EHR implementations, such knowledge is increasingly challenging to obtain in an efficient manner. We address…
Adaptive Threshold Samplingstat.ML
Sampling is a fundamental problem in computer science and statistics. However, for a given task and stream, it is often not possible to choose good sampling probabilities in advance. We derive a general framework for adaptively changing the sampling probabilities via a collection of thresholds.In general, adaptive samp…
Two novel search strategies reduce complexity for target localization with size-dependent noise.
problem Target localization with varying measurement noise based on query region size.
method Proposes and strategies with low complexity and connected query geometry.
result Unified analysis shows asymptotically optimal in search time, near-optimal in rate.