More Like this

1. Relative Error Streaming Quantiles

   https://doi.org/10.1145/3617891  

   Cormode, Graham ; Karnin, Zohar ; Liberty, Edo ; Thaler, Justin ; Veselý, Pavel ( January 2023 , Journal of the ACM)

   Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe equipped with a total order, the task is to compute a sketch (data structure) of size polylogarithmic in n . Given the sketch and a query item y , one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y . Most works to date focused on additive ε n error approximation, culminating in the KLL sketch that achieved optimal asymptotic behavior. This paper investigates multiplicative (1 ± ε)-error approximations to the rank. Practical motivation for multiplicative error stems from demands to understand the tails of distributions, and hence for sketches to be more accurate near extreme values. The most space-efficient algorithms due to prior work store either O (log (ε 2 n )/ε 2 ) or O (log  3 (ε n )/ε) universe items. We present a randomized sketch storing O (log  1.5 (ε n )/ε) items that can (1 ± ε)-approximate the rank of each universe item with high constant probability; this space bound is within an \(O(\sqrt {\log (\varepsilonmore »n)}) \) factor of optimal. Our algorithm does not require prior knowledge of the stream length and is fully mergeable, rendering it suitable for parallel and distributed computing environments.« less
2. Monthly and Annual contour lines of the zero and the positive maximum of the Wind Stress Curl over Western North Atlantic during 1980-2019 and the Gulf Stream path during 1993-2019.

   https://doi.org/10.5281/zenodo.8217388  

   Gifford, Ian ; Silver, Adrienne ; Gangopadhyay, Avijit ; Andres, Magdalena ; Gawarkiewicz, Glen ; Oliver, Hilde ( January 2023 )

   Abstract

   <p>This dataset includes multiple fields: (i) files for monthly and annual fields for the max curl line and the zero curl line at 0.1 degree longitudinal resolutions; (ii) files for monthly and annual GS path obtained from Altimetry and originally processed by Andres (2016) at 0.1 degree longitudinal resolution. The maximum curl line (MCL) and the zero curl line (ZCL) calculations are briefly described here and are based on the original wind data (at 1.25 x 1.25 degree) provided by the Japanese reanalysis (JRA-55; Kobayashi et al., 2015) and available at https://zenodo.org/record/8200832 (Gifford et al. 2023). For details see Gifford, 2023. </p> <p>The wind stress curl (WSC) fields used for the MCL and ZCL calculations extend from 80W to 45W and 30N to 45N at the 1.25 by 1.25-degree resolution.  The MCL is defined as the maximum WSC values greater than zero within the domain per 1.25 degree longitude. As such, it is a function of longitude and is not a constant WSC value unlike the zero contour. High wind stress curl values that occurred near the coast were not included within this calculation. After MCL at the 1.25 resolution was obtained the line was smoothed with a gaussian smoothing and interpolated on to a 0.1 longitudinal resolution. The smoothed MCL lines at 0.1 degree resolution are provided in separate files for monthly and annual averages (2 files). Similarly, 2 other files (monthly and annual) are provided for the ZCL.    </p> <p>Like the MCL, the ZCL is a line derived from 1.25 degree longitude throughout the domain under the condition that it&#39;s the line of zero WSC. The ZCL is constant at 0 and does not vary spatially like the MCL. If there are more than one location of zero curl for a given longitude the first location south of the MCL is selected. Similar to the MCL, the ZCL was smoothed with a gaussian smoothing and interpolated on to a 0.1 longitudinal resolution.   </p> <p>The above files span the years from 1980 through 2019. So, the monthly files have 480 months starting January 1980, and the annual files have 40 years of data. The files are organized with each row being a new time step and each column being a different longitude. Therefore, the monthly MCL and ZCL files are each 480 x 351 for the 0.1 resolution data. Similarly, the annual files are 40 x 351 for the 0.1 degree resolution data.  </p> <p><strong>Note that the monthly MCLs and ZCLs are obtained from the monthly wind-stress curl fields. The annual MCLs and ZCLs are obtained from the annual wind-stress curl fields.</strong></p> <p>Since the monthly curl fields preserves more atmospheric mesoscales than the annual curl fields, the 12-month average of the monthly MCLs and ZCLs will not match with the annual MCLs and ZCLs derived from the annual curl field.  The annual MCLs and ZCLs provided here are obtained from the annual curl fields and representative metrics of the wind forcing on an annual time-scale. </p> <p>Furthermore, the monthly Gulf Stream axis path (25 cm isoheight from Altimeter, reprocessed by Andres (2016) technique) from 1993 through 2019 have been made available here. A total of 324 monthly paths of the Gulf Stream are tabulated. In addition, the annual GS paths for these 27 years (1993-2019) of altimetry era have been put together for ease of use. The monthly Gulf Stream paths have been resampled and reprocessed for uniqueness at every 0.1 degree longitude from 75W to 50W and smoothed with a 100 km (10 point) running average via matlab. The uniqueness has been achieved by using Consolidator algorithm (D’Errico, 2023). </p> <p>Each monthly or annual GS path has 251 points between 75W to 50W at 0.1 degree resolution.  </p>
   

   Other

   Please contact igifford&#64;earth.miami.edu for any queries. {&#34;references&#34;: [&#34;Andres, M., 2016. On the recent destabilization of the Gulf Stream path downstream of Cape Hatteras. Geophysical Research Letters, 43(18), 9836-9842.&#34;, &#34;D&#39;Errico, J., 2023. Consolidator (https://www.mathworks.com/matlabcentral/fileexchange/ 8354-consolidator), MATLAB Central File Exchange. Retrieved June 17, 2023.&#34;, &#34;Gifford, Ian. H., 2023. The Synchronicity of the Gulf Stream Free Jet and the Wind Induced Cyclonic Vorticity Pool. MS Thesis, University of Massachusetts Dartmouth. 75pp.&#34;, &#34;Gifford, Ian, H., Avijit Gangopadhyay, Magdalena Andres, Glen Gawarkiewicz, Hilde Oliver, Adrienne Silver, 2023. Wind Stress, Wind Stress Curl, and Upwelling Velocities in the Northwest Atlantic (80-45W, 30-45N) during 1980-2019, https://zenodo.org/record/8200832.&#34;, &#34;Kobayashi, S., Ota, Y., Harada, Y., Ebita, A., Moriya, M., Onoda, H., Onogi, K., Kamahori, H., Kobayashi, C., Endo, H. and Miyaoka, K., 2015. The JRA-55 reanalysis: General specifications and basic characteristics.\u202fJournal of the Meteorological Society of Japan. Ser. II,\u202f93(1), pp.5-48. Kobayashi, S., Ota, Y., Harada, Y., Ebita, A., Moriya, M., Onoda, H., Onogi, K., Kamahori, H., Kobayashi, C., Endo, H. and Miyaoka, K., 2015. The JRA-55 reanalysis: General specifications and basic characteristics.\u202fJournal of the Meteorological Society of Japan. Ser. II,\u202f93(1), pp.5-48.&#34;]}
   More>>
3. Frequency Estimation with One-Sided Error

   https://doi.org/10.1137/1.9781611977073.31  

   Indyk, P. ; Narayanan, S. ; Woodruff, D.P. ( January 2022 , Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   Frequency estimation is one of the most fundamental problems in streaming algorithms. Given a stream S of elements from some universe U={1…n}, the goal is to compute, in a single pass, a short sketch of S so that for any element i∈U, one can estimate the number xi of times i occurs in S based on the sketch alone. Two state of the art solutions to this problems are the Count-Min and Count-Sketch algorithms. The frequency estimator x~ produced by Count-Min, using O(1/ε⋅logn) dimensions, guarantees that ∥x~−x∥∞≤ε∥x∥1 with high probability, and x~≥x holds deterministically. Also, Count-Min works under the assumption that x≥0. On the other hand, Count-Sketch, using O(1/ε2⋅logn) dimensions, guarantees that ∥x~−x∥∞≤ε∥x∥2 with high probability. A natural question is whether it is possible to design the best of both worlds sketching method, with error guarantees depending on the ℓ2 norm and space comparable to Count-Sketch, but (like Count-Min) also has the no-underestimation property. Our main set of results shows that the answer to the above question is negative. We show this in two incomparable computational models: linear sketching and streaming algorithms. We also study the complementary problem, where the sketch is required to not over-estimate, i.e., x~≤x should holdmore »always.« less
4. Linear Sketching over F_2

   https://doi.org/10.4230/LIPIcs.CCC.2018.8  

   Kannan, Sampath ; Mossel, Elchanan ; Sanyal, Swagato ; Yaroslavtsev, Grigory ( August 2018 , Leibniz international proceedings in informatics)

   We initiate a systematic study of linear sketching over F_2. For a given Boolean function treated as f : F_2^n -> F_2 a randomized F_2-sketch is a distribution M over d x n matrices with elements over F_2 such that Mx suffices for computing f(x) with high probability. Such sketches for d << n can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between F_2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F_2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F_2-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F_2-sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F_2 can be constructed as F_2-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does not require themore »stream length to be triply exponential in n and holds for streams of length O(n) constructed through uniformly random updates.« less
5. Linear Sketching over F2

   Kannan, Sampath ; Mossel, Elchanan ; Sanyal, Swagato ; Yaroslavtsev, Grigory ( June 2018 , 33rd Computational Complexity Conference, (CCC 2018))

   We initiate a systematic study of linear sketching over $\ftwo$. For a given Boolean function treated as $f \colon \ftwo^n \to \ftwo$ a randomized $\ftwo$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\ftwo$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high probability. Such sketches for $d \ll n$ can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between $\ftwo$-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that $\ftwo$-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree $\ftwo$-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that $\ftwo$-sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over $\ftwo$ can be constructed as $\ftwo$-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does notmore »require the stream length to be triply exponential in $n$ and holds for streams of length $\tilde O(n)$ constructed through uniformly random updates.« less