CountSketches, Feature Hashing and the Median of Three
Authors: Kasper Green Larsen, Rasmus Pagh, Jakub Tětek
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we empirically support our new theoretical bounds by estimating the variance of Count Sketch with 1 row and 3 rows on different data sets. We implemented Count Sketch in C++ using the multiply-shift hash function (Dietzfelbinger, 1996) as the 2-wise independent hash functions h and g. We seeded the hash functions using the built-in Mersenne twister 64-bit pseudorandom generator. Experiments were run both for frequency estimation (Section 4) and for inner product estimation (Section 4). Figures 2-7 show experimental results, and Table 1 summarizes variances. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Aarhus University, Denmark 2BARC, Department of Computer Science, University of Copenhagen, Denmark. |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. It mentions implementing Count Sketch in C++ but provides no repository link, explicit code release statement, or code in supplementary materials. |
| Open Datasets | Yes | Sentiment140: A collection of 1.6M tweets from Twitter (Go et al., 2009). Kosarak: Provided by Ferenc Bodon to the FIMI data set located at http://fimi.uantwerpen.be/data/. |
| Dataset Splits | No | The paper does not provide specific dataset split information (exact percentages, sample counts, citations to predefined splits, or detailed splitting methodology) in the context of typical machine learning train/validation/test splits, as the experiments focus on estimating variance of a sketching algorithm. |
| Hardware Specification | No | The paper does not provide specific hardware details (exact GPU/CPU models, processor types with speeds, memory amounts, or detailed computer specifications) used for running its experiments. |
| Software Dependencies | No | The paper mentions implementation in 'C++' and using 'Mersenne twister 64-bit pseudorandom generator' but does not provide specific version numbers for compilers or any other software dependencies needed to replicate the experiment. |
| Experiment Setup | Yes | For each experiment, we plot the variance as a function of the total space usage (2t 1)s as we increase the number of columns s. We run experiments with s = 2^2, 2^3, ..., 2^10 on each data set. For each choice of s, we estimate the variance by constructing 1000 Count Sketches on the input with new randomness for each. For each Count Sketch we pick 100 random items and compute the estimation error for each. |