{'fraction_non_alphanumeric': 0.05094225970226315, 'fraction_numerical': 0.012420044172905372, 'mean_word_length': 3.8194636439037875, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Range-efficient consistent sampling and locality-sensitive hashing for polygons

Locality-sensitive hashing (LSH) is a fundamental technique for similarity search and similarity estimation in high-dimensional spaces. The basic idea is that similar objects should produce hash collisions with probability significantly larger than objects with low similarity. We consider LSH for objects that can be represented as point sets in either one or two dimensions. To make the point sets finite size we consider the subset of points on a grid. Directly applying LSH (e.g. min-wise hashing) to these point sets would require time proportional to the number of points. We seek to achieve time that is much lower than direct approaches. Technically, we introduce new primitives for range-efficient consistent sampling (of independent interest), and show how to turn such samples into LSH values. Another application of our technique is a data structure for quickly estimating the size of the intersection or union of a set of preprocessed polygons. Curiously, our consistent sampling method uses transformation to a geometric problem.


Introduction
Suppose that you would like to search a collection of polygons for a shape resembling a particular query polygon. Or that you have a collection of discrete probability distributions, and would like to search for a distribution that resembles a given query distribution. A framework for addressing this kind of question is locality-sensitive hashing (LSH), which seeks to achieve hash collisions between similar objects, while keeping the collision probability low for objects that are not very similar. Arguably the most practically important LSH method is min-wise hashing, which works on any type of data where similarity can be expressed in terms of Jaccard similarity of sets, i.e., the ratio between the size of the intersection and the size of the union of the sets. Indeed, the seminal papers of Broder et al. introducing min-wise hashing [5,7] have more than 1000 citations. Independently, Cohen [12] developed estimation algorithms based on similar ideas (see also [13]). The basic idea behind min-wise hashing is to map a set S to argmin x∈S h(x), which for a strong enough hash function h gives collision probability equal (or close) to the Jaccard similarity (see e.g. [6] for a discussion of sufficient requirements on h). If we represent discrete probability distributions by histograms there is a one-to-one relationship between the Jaccard similarity of two histograms and the statistical distance between the corresponding distributions. So a search for close distributions in terms of Jaccard similarity will translate into a search for distributions that are close in statistical distance, see Figure 1.
To make min-wise hashing well-defined on infinite point sets in the plane we may shift to an approximation by considering only those points contained in a finite grid of points. However, for a good approximation these sets must be very large, which means that computing a hash value h(x) for each point x ∈ S, in order to do min-wise hashing, is not attractive.

Our results
We consider efficient locality-sensitive hashing for objects that can be represented as point sets in either one or two dimensions, and whose similarity is measured as the Jaccard similarity of these point sets. The model of computation considered is a Word RAM with word size at least log p, where p is a prime number. We use integers in U = {0, . . . , p − 1} (or equivalently elements in the field F p of size p) to represent coordinates of points on the grid. Our first result concerns histograms with n values in U . Our construction gives an explicit alternative to existing results on weighted min-wise hashing (see [18,21]) whose analysis relies on hash functions that are fully random and cannot be described in small space. It was previously shown that a form of priority sampling based on 2-independence can be used to estimate Jaccard similarity of histograms [26], but similarity estimation is less general than locality-sensitive hashing methods such as weighted min-wise hashing. We proceed to show the generality of our technique by presenting an LSH method for geometric objects. We will use approximation to achieve high performance even for "hard" shapes, and adopt the so-called fuzzy model [1]. In a fuzzy polygon, points that are "close" to the boundary (relative to the polygon's diameter) may or may not be included in the polygon. That is, given a polygon P and real value 0 < φ ≤ 1, define the outer range P + = P + (w) to be the locus of points whose distance from a point interior to P is at most w = φ · d(P ), where d(P ) is the diameter of P . The inner range P − = P − (w) of P is defined symmetrically.
Using the fuzzy model a valid answer to the Jaccard similarity of two polygons P 1 and P 2 w.
denotes the area of the region. To simplify the statement of the theorem we say that a polygon is α-dense in a rectangle I if for some value α > 0 its area is at least a fraction α of the area of I. We use this to bound the time it takes to generate the sample points.
Theorem 2. For every choice of constants ε > 0, φ > 0 and square I ⊆ R 2 it is possible to choose an explicit random hash function H whose description size is constant, that can be evaluated in time O((t log p)/α), where t is the time to test if a given point lies inside a polygon, and with the following guarantee on collision probability: Let P 1 , P 2 ⊆ I be polygons such that where J is some valid Jaccard similarity of P 1 and P 2 in the fuzzy model with parameter φ.
It is an interesting problem whether the additive error in Theorems 1 and 2 can be improved to a multiplicative 1 + ε error.

XX:3
In Section 5 we present further applications of our technique and show how a small summary can be constructed for a set P of polygons such that for any subset Q of P, an estimate of the area of ∩Q and ∪Q can be computed efficiently in the fuzzy model with respect to φ.
Techniques. Our main technical contribution lies in methods for range-efficient min-wise hashing in one and two dimensions, efficiently implementing min-wise hashing for intervals and rectangles. More specifically, we consider intervals in U and rectangles in U × U . The new technique can be related to earlier methods for sampling items with small hash values in one or more dimensions [24,27]. (In fact, en route we obtain new hash-based sampling algorithms with improved speed, which may be of independent interest.) However, using [24,27] to sample a single item is not likely to yield a good locality-sensitive hash function. The reason is that the hash functions used in these methods are taken from simple, 2-independent families and, as explained by Thorup [26], min-wise hashing using 2-independence does not in general yield collision probability that is close to (or even a function of) the Jaccard similarity. Instead we use a 2-phase approach: First produce a sample of k elements having the smallest hash values, and then perform standard min-wise hashing on a carefully selected subset of the sample using a different hash function.
We can combine and filter the samples to handle a variety of point sets that are not intervals or rectangles. To create a sample for a subset of a rectangle we can generate a sample of the rectangle, and then filter away those sample points that are not in the subset. This is efficient if the subset is suitably dense in the rectangle (which we ensure by working in the fuzzy model).
To create a sample from the union of two sets, simply take the union of the samples. Theorems 1 and 2 are obtained in this way, and it would be possible to instantiate many other applications.
At the heart of our range-efficient sampling algorithms for one and two dimensions lies a reduction to the problem of finding an integer point (or integer points) in a given interval with small vertical distance to a given line. Such a point can effectively be found by traversing the integer convex hull of the line. Using a result of Charrier and Buzer [10] this can be done in logarithmic time. Thus, geometry shows up in an unexpected way in the solution.

Comparison with related work
We are not aware of previous work dealing with range-efficient locality-sensitive hashing. The most closely related work is on range-efficient consistent (or coordinated) sampling, which is a technique for constructing summaries and sketches of large data sets. The technique comes in two flavors: bottom-k (or min-wise) sampling, which fixes the sample size, and consistent sampling (or sub-sampling), which fixes the sampling probability. In both cases the idea is to choose as a sample those elements from a set S ⊆ U that have small hash values under a random hash function h : U → [0; 1]. If the sample size is fixed and some hash values are identical then an arbitrary tie-breaking rule can be used, e.g., selecting the minimum element. To make argmin uniquely defined, which is convenient, we take argmin x∈I h(x) to be the smallest value y ∈ I for which h(y) = min x∈I h(x). To denote the set of the k elements having the smallest hash values (with ties broken in the same way) we use the notation argmin k . We focus on settings in which U is large and it is infeasible to store a table of all hash values.
In one dimension. Pavan and Tirthapura [24] consider the 2-independent family of linear hash functions in the field of size p, i.e., functions of the form h(x) = (ax + b) mod p. They show how to find hash values h(x) below a given threshold ∆, where x is restricted to an interval I. We will argue in Section 2 that Lemma 3 can be applied repeatedly to subintervals to output the k smallest hash values (and corresponding inputs) in time O(k log |I|). The possibility of choosing a = 0 is included for mathematical convenience (to ensure 2-independence), though in most applications it will be better to choose a > 0 (which in addition makes argmin uniquely defined without a tie-breaking rule).
In more than one dimension. Tirthapura and Woodruff [27] consider another class of 2independent functions, namely linear transformations on vectors over the field F 2 . Integers naturally correspond to such vectors, and for a dyadic interval I containing all integers that share a certain prefix, the problem of finding elements in I that map to zero is equivalent to solving a linear system of equations. Since an arbitrary interval can be split into a logarithmic number of dyadic intervals they are able to compute all the integers that map to zero in polylogarithmic time. The sampling probability can be chosen as an arbitrary integer power of two. This method generalizes to rectangles in dimension d ≥ 2.
In this paper we instead consider linear, 2-independent hash functions of the form (x, y) → (ax + by + c) mod p . We do not know of a method for efficiently computing a min-hash over a rectangle for such functions, but we are able to efficiently implement consistent sampling with sampling probability 1/p.
For random a, b, c the expected size of the sample I is |I|/p, and because of 2-independence the distribution of |I | is concentrated around this value. Compared to the method of [27] ours is faster, but has the disadvantage that the sampling probability cannot be chosen freely. However, as we will see this restriction is not a real limitation to our applications to locality sensitive hashing and size estimation.
From consistent sampling to LSH. Our technique for transforming a consistent sample to an LSH value is of independent interest. Thorup [26] shows that min-wise hashing using 2independence does not in general yield collision probability that is close to (or even a function of) the Jaccard similarity. On the positive side he shows that bottom-k samples of two sets made using a 2-independent hash function can be used to estimate the Jaccard similarity J of the sets with arbitrarily good precision. However, this does not yield a locality-sensitive hash function with collision probability (close to) J, and obvious approaches such as min-wise hashing applied to the samples fails to have the right collision probability. Instead, we use consistent sampling (using a 2-independent family) followed by a stronger hash function for which min-wise hashing has the desired collision probability up to an additive error ε. This transformation yields the first LSH family for Jaccard similarity (with proven guarantees on collision probability) where the function can be: evaluated in O(n + poly(1/ε)) time on a set of size n, and described and computed in a constant number of machine words (independent of n). Previous such functions have used either time per element that grows as ε approaches zero [20], or required description space that is a root of n (see [14]).

Preliminaries
We will make extensive use of 2-independence: It will be convenient to use the notation x ± ∆ for a number in the interval [x − ∆; x + ∆]. Carter and Wegman [8] showed that the family . . , p − 1} when p is a prime. Finally, we make use of ε-minwise independent families: Indyk [20] showed that an efficient ε-minwise independent family mapping to a range of size O(p/ε) can be constructed by using an O(log(1/ε))-independent family of functions (e.g. polynomial hash functions). Dahlgaard and Thorup [14] showed that the evaluation time can be made constant, independent of ε, by using space |U | Ω(1) . If we only care about sets of size up to some numbern, this space usage can be improved to (n/ε) Ω(1) .

Range-efficient bottom-k sampling in one dimension
The aim of this section is to show Lemma 3 and how it can be used to efficiently compute consistent as well as bottom-k samples. Together with the general transformation presented in Section 4 this will lead to Theorem 1. Without loss of generality suppose 0 < i 1 In case a = 0 this is trivial (just output i 1 ), so we focus on the case a > 0. We will show how the problem can be reduced to the problem of finding the integer point at the smallest (vertical) distance below the line segment To see this observe that for x ∈ N we have vertical distance (ax + b)/p − (ax + b)/p between the line and the nearest integer point. Using the equality we see that minimizing (ax + b mod p) is equivalent to minimizing (ax + b)/p − (ax + b)/p , as claimed. Therefore it suffices to search for the point (x, y) ∈ D = I × N below that is closest to . Since is a line, the point (x, y) must lie on the convex hull CH( ) of the set of points in D that lie below , referred to as the "integer convex hull", see Figure 2. Clearly, the closest point will always be on the upper part of the hull, denoted CH L ( ). Zolotykh [29] showed that CH( ) consists of O(log(i 2 − i 1 )) line segments. To find a point on the integer convex hull with the smallest vertical distance to we will use a result by Charrier and Buzer [10]. Charrier and Buzer initially assume that passes through the origin. However, they note (Section 7 in [10]) that this requirement is not needed. Thus, using their result on the line defined in (1) we obtain Lemma 3.
We now discuss how to use Lemma 3 to output the k smallest hash values (and corresponding inputs, i.e., the bottom-k sample) in time O(k log p). First compute CH L ( ) and find the point (x 1 , y 1 ) ∈ CH L ( ) with the smallest vertical distance to . Next, split the problem into two subintervals; one for the part of in the x-interval [i 1 , x 1 − 1] and one for the part of in the x-interval [x 1 + 1, i 2 ]. Using a heap to find the integer point with smallest vertical distance in the intervals considered, we can repeat this process until k points have been found. To compute a consistent sample rather than the bottom-k sample we simply stop the procedure whenever we see an element with a hash value larger than the threshold. It is an interesting problem whether it is possible to improve this bound to O(k + log |I|).

3
Rectangle-efficient consistent sampling The aim and structure of this section are similar to those of Section 2, but now addressing the case where we want to do hashing-based sampling in a rectangle I = {i 1 . . . , i 2 } × {j 1 . . . , j 2 }. Specifically, we prove Lemma 4 and show how one can use it to perform consistent sampling. This will be used in Section 4 to prove Theorem 2 and in Section 5 to construct an efficient data structure for estimating the size of intersections and unions of polygons. Assume without loss of generality that 0 ≤ i 1 < i 2 < p, 0 ≤ j 1 < j 2 < p and i 2 − i 1 ≤ j 2 − j 1 . Consider the 2-independent family H 2 = {(x, y) → (ax + by + c) mod p | a, b, c ∈ U } and choose h ∈ H 2 . To prove Lemma 4 we have to argue that can be computed in time O((|I | + 1) log(i 2 − i 1 )). Similar to the previous section we will show how the problem can be reduced to the problem of finding all integer points below a line segment with a small vertical distance to . To find all (x, y) ∈ I for which h(x, y) = (ax + by + c) mod p = 0, as a first step we translate the function h such that we can consider input y ∈ [0, y 2 ]. Specifically, we replace h with h : (x, y) → (ax + by + c ) mod p, where c = c + bj 1 , and consider inputs with (x, y) ∈ [i 1 , i 2 ] × [0, j 2 ], j 2 = j 2 − j 1 . This is equivalent to the original task since h(x, y) = h (x, y − j 1 ). Next note that for x ∈ [i 1 , i 2 ] and y ∈ [0, j 2 ]: To simplify the expression set q = −b −1 a and s = −b −1 c . Then we have a zero hash value when y = (qx + s) mod p = (qx + s) − kp for some positive integer k. Dividing by p and substituting α = q/p and β = s/p we get y p = αx + β − k, where x ∈ [i 1 , i 2 ] and y/p ∈ [0, j 2 /p]. Now we can express the original problem as finding all (x, k) }. An integer point (x , y ) below with x ∈ [i 1 , i 2 ] and vertical distance at most j 2 /p to corresponds to a point (x , y ) such that h (x , y ) = 0.
To find all the points (x , y ) that fulfill the restrictions we can apply the same technique as in Section 2. That is, compute the integer convex hull CH L ( ) using the algorithm by Charrier and Buzer [10]. One difference from the setting of Section 2 is that we are interested in all integer points close to , but CH L ( ) is guaranteed only to include one such point if it exists. This is handled by recursing on subintervals in which no points have been reported until we find an interval where the integer convex hull does not contain a point close to . Recall that the time to output the integer convex hull is O(log(i 2 − i 1 )) by the result of Zolotykh [29], so the cost per point reported is logarithmic. This concludes the proof of Lemma 4.
For some α > 0 consider an arbitrary set S ⊆ I, and the sample S = S ∩ I where I is defined in (2). Let 1/p be the sampling probability. We now show that p |S | is concentrated around its expectation |S| when p is not too large. To get an (ε, δ)-estimator we thus need p ≤ δε 2 µ. The expected time for computing I in Lemma 4 is upper bounded by O(E[|I | + 1] log p) which is O((|I|/p + 1) log p). If we choose p = Ω(δε 2 |S|), to get an (ε, δ)-estimator, and let α = |S|/|I| be the fraction of points of I that are also in S, then the expected time simplifies to O(log(p)/(αδε 2 )). That is, the bound independent of the size of S, has logarithmic dependence on p, and linear dependence on 1/α, 1/δ, and 1/ε.

From consistent sampling to locality-sensitive hashing
We now present a general transformation of methods for 2-independent consistent sampling to locality-sensitive hashing for Jaccard similarity. Together with the consistent sampling methods in Sections 2 and 3 this will yield Theorems 1 and 2. Thorup [26] observed that min-wise hashing based on a 2-independent family does not give collision probability that is close to (or a function of) Jaccard similarity. He observes a bias for a 2-independent family of hash functions based on multiplication, similar to the ones used in this paper. Thus we take a different route: First produce a consistent sample using 2-independence, and then apply min-wise hashing to the sample using a stronger hash function. The expected time per element is constant if we make sure that the sample has expected constant size.
We have not specified f . The most obvious choice is to use an O(log(1/ε))-independent hash function [20]. Another appealing choice is twisted tabulation hashing [14] that yields constant evaluation time, independent of ε. The expected size of S ∩ I is bounded by a function of ε and α. This means that we can combine twisted tabulation with an injective universe reduction step to reduce the domain of twisted tabulation to a (large) constant depending on ε and α.
Proof of Theorem 1. Consider a vector x = (x 1 , . . . , x n ) ∈ U n . We follow the folklore approach [18] of conceptually mapping each vector x to a set P x , such that the Jaccard similarity of P x and P y exactly equals the weighted Jaccard similarity of x and y. In particular, it is easy to verify that this is the case if we let P x = {(i, j) | i = 1, . . . , n; j = 1, . . . , x i }. Note that P x and P y both have size N . We will use the following class of hash functions from U × U to U : The 2-independence of H 2 follows from the arguments of Carter and Wegman [8]. A proof is included in Appendix A for completeness. When restricted to points of the form (i, ·) for a fixed i, each function h ∈ H 2 has a form suitable for Corollary 8 in Section 2. This means we can find the minimum for P x restricted to a given column i in time O(log x i ). Using a heap to keep track of the smallest hash value from each column of P x not (yet) reported in the sample, we can output all elements of P x with a hash value smaller than any given threshold τ in time O(log p) per element. The threshold τ is chosen to match the desired sampling probability p * .
Lemma 11 then says that we get the desired collision probability up to an additive error of ε. The expected time to hash is O(n log p) (to populate the priority queue) plus O(log p) times the expected number of samples. The expected number of samples |S|/p is constant for every constant ε > 0, which gives the desired time bound in expectation.
It is possible to turn the expected bound into a worst case bound by stopping the computation if the running time exceeds 1/δ times the expectation, which happens with probability at most δ. If we simply output a constant in this case the collision probability changes by at most δ (which we can compensate for by decreasing ε).
Proof of Theorem 2. The proof is similar to the proof of Theorem 1 but with some added geometric observations. Let P 1 and P 2 be two polygons contained in I. As mentioned in the introduction, a valid answer to the Jaccard similarity of polygons P 1 and P 2 with respect to φ is any value X∩ X∪ such that A(P − 1 (w 1 ) ∩ P − 2 (w 2 )) ≤ X ∩ ≤ A(P + 1 (w 1 ) ∩ P + 2 (w 2 )) and . We now switch to considering the restrictions of P + 1 (w 1 /2) and P + 2 (w 1 /2) to a p-by-p grid of points whose enclosing rectangle contains I. See [19] for a survey on snapping points to a grid.
The grid points are identified in the natural way with integer coordinates in [p] × [p]. We choose p such that the number of points inside I is Θ(p/α) times the desired number of samples required for Lemma 11 to hold.
Lemma 11 gives us the desired collision probability up to an additive error of ε. The expected time to hash is O(log p) plus O(t log p) times the expected number of samples, where t is the time to test if a given grid point lies inside a polygon. If we assume that P 1 and P 2 are α-dense in I, that is, there exists an α > 0 such that |P + 1 (w 1 /2)|, |P + 2 (w 2 /2)| > α · |L + |, then the expected number of samples is |L + |/(αp) for any constants ε and φ, which gives the desired time bound in expectation. In many natural settings α is a constant, which implies that the expected number of samples is also constant.

Estimating union and intersection of polygons
In this section we consider the question: Given a set P = {P 1 , . . . , P n } of n preprocessed polygons in the plane, how efficiently can we compute the area of the union or the intersection of a given subset Q ⊆ P? In contrast to elementary approaches based on global, fully random sampling, our solution allows polygons to be independently preprocessed based on a small amount of shared randomness that specifies a pseudorandom sample. Computing the area of the union of a set of geometric objects is a well-studied problem in computational geometry. One example is the Klee's Measure Problem (KMP). Given n axisparallel boxes in the d-dimensional space, the problem asks for the measure of their union. In 1977, Victor Klee [22] showed that it can be solved in O(n log n) time for d = 1. This was generalized to d > 1 dimensions by Bentley [3] in the same year, and later improved by van Leeuwen and Wood [28], Overmars and Yap [23] and, Chan [9]. In 2010, Bringmann and Friedrich [4] gave an O( dn 2 ) Monte Carlo (1 + )-approximation algorithm for the problem. A related question is the computation of the area of the intersection of n polygons in ddimensional space. Bringmann and Friedrich [4] showed that there cannot be a (deterministic or randomized) multiplicative (2 d 1− )-approximation algorithm in general, unless NP=BPP. They therefore gave an additive -approximation for a large class of geometric bodies, with a running time of O( nd 2 ) assuming that the following three queries can be approximately answered efficiently: point inside body, volume of body and sample point within a body.
In this section we will approach the problem slightly differently. The approach we suggest is to produce a small summary of the set P, such that given any subset Q of P the union and intersection of Q can be estimated efficiently. Unfortunately, the lower bound arguments by Bringmann and Friedrich [4] defeat any reasonable hope of achieving polynomial running time for arbitrary polygons. To get around the lower bounds we again adopt the approximation model proposed by Arya and Mount [1] (stated in Section 1.1) , which has been used extensively in the literature [11,15,16].
Similar to the approach by Bringmann and Friedrich [4] we will also use sampling of the polygons to estimate the size of the union and intersection. However, compared to earlier attempts, the main advantage of our approach is that we generate the sample points (a summary of the input) in a preprocessing step and after that we may discard the polygons. Union and intersection queries are answered using only the summary. Also, we do not impose any restrictions on the input polygons. The drawbacks are that we only consider the case when d = 2 and the approximation model [1] we use is somewhat more "forgiving" than previously used models.
For each polygon P i in P, is the diameter of P i and 0 ≤ φ ≤ 1 is a given constant. Let Q be the input to a union or intersection query, that is, Q is a subset of P. To simplify the notations we will write ∪Q + (w) = ∪ Pi∈Q P i (w i ) and ∪Q − (w) = ∪ Pi∈Q P i (w i ). Define ∩Q + (w) and ∩Q − (w) symmetrically.
Following the above discussion, given a legal answer to a set intersection query X = ∩Q is any X such that ∩Q − (w) ⊆ X ⊆ ∩Q + (w) and for a union query X = ∪Q a legal answer is any X such that ∪Q − (w) ⊆ X ⊆ ∪Q + (w). It is immediate from the above definitions that for any polygon P and any w ≥ √ 2 we have: P − (w) ⊂ P ⊂ P + (w). We will use the number of integer coordinates, denoted |P |, within a polygon P to estimate the area of the polygon, denoted A(P ). Proofs of Lemmas 12, 13 and 15 can be found in the appendix.

Lemma 12. For a polygon P having integer coordinates we have A(P ) ≤ |P |.
To make the queries more efficient we will not estimate the number of integer coordinates in the intersection/union X of a query, instead we will estimate an approximation of |X|. We show: Lemma 13. For any polygon P and w ≥ √ 8: A(P ) ≤ A(P + (w/2)) ≤ |P + (w/2)| ≤ A(P + (w)).
As an immediate consequence of Lemma 13 we can use the consistent samples in P + i (w i /2), 1 ≤ i ≤ n, for our estimates of the intersection and union, provided that w i ≥ √ 8. It remains to show how a summary of P can be computed and how the summary can be used to answer union and intersection queries.
Constructing a summary. For a given query Q containing k ≤ n polygons, let P min = argmin Pi∈Q |P + i (w i /2)|, P max = argmax Pi∈Q |P + i (w i /2)| and let d min = argmin Pi∈Q d(P i ). If P i = P max and P j = P min then we will write P + max (w) = P + i (w i ) and P + min (w) = P + j (w i ), respectively. Before giving the construction of summary and query algorithms we state two lemmas: We will use the rectangle-efficient consistent sampling technique described in Section 3 to generate a summary of P to estimate the area of ∩Q or ∪Q, where Q is a given subset of P.
The idea of the construction algorithm for the summary is simple. Let X = ∩Q + (w/2) or X = ∪Q + (w/2) depending on the query and, assume that φ · d min > √ 8. In a preprocessing step construct a summary of P, denoted S. The summary S will contain consistent samples for a number of different sampling rates. To answer a query, pick a minimum sampling rate 1/p that guarantees that the expected number of consistent samples in X is small but sufficient to guarantee an (ε, δ)-estimate of |X|. If X contains enough unique consistent samples then the algorithm reports an estimate of X, otherwise it iteratively increases the sampling rate with a constant factor until X contains sufficiently many unique consistent samples. From Section 3.1 we know that an (ε, δ)-estimator of X requires the sampling rate to be approximately 1/(δ · ε 2 · |X|).
From Lemmas 14 and 15 we have that the smallest area that will ever be considered in a query Q has size at least f min = φ 2 2 |P + min (w/2)| and the largest area is at most f max = n · |P + max (w/2)|. To get an (ε, δ)-estimate of |X| at least 1/δ 2 ε unique consistent samples are required to lie within X. As output from the above algorithm we get two data structures: p[ ]: Returns a prime number between [2 −1 , 2 ]. S[P i , ]: Returns the set of consistent samples within P + i (w i /2), i.e., points satisfying the equation (ax + by + c) mod p[j] = 0. If the set is empty it returns False.
Complexity. Consider the total number of consistent samples generated for a polygon P i . The number of consistent samples is expected to increase with a factor of two in each iteration of the algorithm, that is, the expected total number of consistent samples form an exponentially growing geometric series which sums to O( 1 φ 2 δ 2 ε · |Pi| |Pmin| ). Summing up over all the polygons, the total number of consistent samples is bounded by O( n φ 2 δ 2 ε · |Pmax| |Pmin| ), which is also the expected size of the summary.
For the time complexity we first note that the above procedure can be implemented such that iterations where no consistent samples are expected to be generated are omitted without consideration. Since at least a fraction of φ/2 of all consistent samples in the minimal bounding box of P + i (w i /2) is expected to lie within P + i (w i /2) (can be shown using a similar argument as in the proof of Lemma 15) the total number of generated consistent samples is expected to be at most a factor of 2/φ greater than the number of consistent samples in the summary. Each consistent sample requires at most O(log |P i |) time to generate, according to Theorem 4. If we assume that testing if a consistent sample lies inside a polygon can be done in time t then the expected time to build a summary of P is O( n φ 2 δ 2 ε · |Pmax| |Pmin| · (t + log |P max |)). A description of union and intersection queries can be found in the appendix. We can now summarize the results in this section: Theorem 16. . Given a set P = {P 1 , . . . , P n } of polygons and three constants ε, δ > 0 and 0 < φ ≤ 1. If φ · d(P i ) ≥ √ 8 for all P i ∈ P then, in the fuzzy model with respect to φ, there exists a summary of size O( n φ 2 δ 2 ε · |Pmax| |Pmin| · (t + log |P max |)) such that for any subset Q of P containing k ≤ n polygons an (ε, δ)-estimate of ∪Q can be computed in O(k/δε 2 ) expected time and an (ε, δ)-estimate of ∩Q can be computed in O( k φ 2 δε 2 ) expected time.

Conclusion and open problems
We have investigated efficient methods for consistent sampling and locality-sensitive hashing of 2-dimensional point sets. Though the methods are simple, it is not clear if they are as useful in practice as, say, minwise hashing. In addition to practicality, some theoretical questions remain, for example whether the additive constant ε in our theorems can be avoided. Further, our measure of similarity among point sets is by no means the only possible one -it would be interesting to consider notions of similarity that are invariant under rotations and translations of the point set. Proof. Let us check that our hash function is in fact 2-independent. Let x 1 , x 2 , y 1 , y 2 ∈ U and t 1 , t 2 ∈ F p s.t. q 1 = (x 1 , y 1 ) = q 2 = (x 2 , y 2 ). Let q −1 ∈ F p be the unique multiplicative inverse of q. Note that this is guaranteed to exist if and only if q is non-zero. What is the probability that h(q 1 ) = t 1 and h(q 2 ) = t 2 ? We have (ax 1 + by 1 + c) mod p = t 1 and (ax 2 + by 2 + c) mod p = t 2 .
Since q 1 = q 2 we may assume without loss of generality that x 1 = x 2 . Now fix b. We get: For every b there exists exactly one pair a, c such that the above equality holds. Since a and c are drawn uniformly and independently from F p , this probability is 1/p 2 .

B
Omitted material from Section 5

B.1 Proof of Lemma 12
Proof. We use Pick's theorem [25]. Let i(P ) be the number of integer coordinates in the interior of P and let b(P ) be the number of integer coordinates on the boundary of P . Pick's theorem states: where h is the number of holes in P . Since A(P ) < i(P ) + b(P ) = |P | the lemma follows.

B.2 Proof of Lemma 13
Proof. The first inequality is immediate and the second inequality follows from Lemma 12. For the third inequality we note that any point in the plane within distance √ 2 from an integer coordinate within P + (w/2) will lie within P + (w), hence |P + (w/2)| ≤ A(P + (w)).
To see this let a and b be two points on the boundary of P + min with largest inter-point distance among all points in P + min (w/2). The distance between a and b is at most (1 + φ) · d min . Note that P + min (w/2) is enclosed in the intersection of the two disks of radius |ab| centered at a and b, hence, (5) follows.
Next consider a point p in the non-empty set ∩Q − (w). By definition p must lie in P − i (w) for every P i ∈ Q. As a result the ball of radius 3 2 φ · d min and center at p must lie in ∩Q, thus A(∩Q + (w/2)) ≥ π( 3 2 · φ · d min ) 2 .