Questions tagged [sketching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers

How to determine the width and depth of a count-min sketch, depending of the unique elements inside

Follow up this question: What is the correct way to determine the width and depth of a count-min sketch? Let suppose, correct way is following: ...
  • 101
4 votes
3 answers

Integer set disjointness query on sketches with something like homomorphic hashing

Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. ...
  • 364
0 votes
0 answers

Why is Combinatorial Sketching for Finite programs possible?

I was reading Combinatorial Sketching for Finite Programs and wanted to understand why synthesis of the sketching language was possible/feasible. As far as I understand a partial program is ...
2 votes
0 answers

Different properties of Heavy-Hitters and Count-Min Sketch algorithms?

I'm currently using the Heavy-Hitters algorithm as described here and I'm wondering what if any space, time, accuracy, or real-world performance differences I would see if I were to switch to an ...
  • 251
0 votes
0 answers

L1 sampling for sampling edges of a graph

I am trying to sample the edges of an undirected graph using weights. The goal is to run a sparsification algorithm on the graph. I see the point that L1 norm is best for sparsification. Can someone ...
4 votes
0 answers

Is this a known question in matrix sketching?

Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m \ll D $ dimensional columns and ...
  • 173
1 vote
1 answer

Is this a kind of "sketching"?

Say one is given a matrix (assume real and symmetric if necessary) and its $n-$dimensional columns be say $v_1,v_2,..,v_n$. Now is it possible to find a set of $d<n$ lower dimensional vectors ($w_1,...
  • 173
6 votes
0 answers

What is the correct way to determine the width and depth of a count-min sketch?

The width (number of registers) and depth (number of hash functions) of a Count-Min sketch determine the accuracy of counts retrieved. I've found two different methods for calculating the width ($w$) ...
0 votes
0 answers

How does hashing achieve sketching?

Given a sequence $x \in \{ 1,2,3...,\vert \Sigma \vert \}^*$ one wants to create a sketch of it say $s(x)$ of size $\frac{2c}{3}k (ln^2 k)$ bits. And that seems to be achieved as follows, pick at ...
  • 1,105