# Questions tagged [sketching]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
33 views

### 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
104 views

### 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
119 views

### 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,950
86 views

### 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
106 views

### 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 ...
70 views

### 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