The Space Complexity of Inner Product Filters
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Pagh, Rasmus
Sivertsen, Johan
Motivated by the problem of filtering candidate pairs in inner product similarity joins we study the following inner product estimation problem: Given parameters d∈ℕ, α>β≥0 and unit vectors x,y∈ ℝ^d consider the task of distinguishing between the cases ⟨x,y⟩≤β and ⟨x,y⟩≥α where ⟨x,y⟩ = ∑_{i=1}^d x_i y_i is the inner product of vectors x and y. The goal is to distinguish these cases based on information on each vector encoded independently in a bit string of the shortest length possible. In contrast to much work on compressing vectors using randomized dimensionality reduction, we seek to solve the problem deterministically, with no probability of error. Inner product estimation can be solved in general via estimating ⟨x,y⟩ with an additive error bounded by ε = α - β. We show that d log₂ (√{1-β}/ε) ± Θ(d) bits of information about each vector is necessary and sufficient. Our upper bound is constructive and improves a known upper bound of d log₂(1/ε) + O(d) by up to a factor of 2 when β is close to 1. The lower bound holds even in a stronger model where one of the vectors is known exactly, and an arbitrary estimation function is allowed.
 My name is Rasmus Pei and I'm going to talk about the space complexity of inner product fillers. This is joint work with my former student and postdoc Johan C. Wilson. Traditional databases store things like integers, booleans, dates and text. But in recent years there's been a new kid on the block, the feature vector. So a feature vector is a succinct vector representation or an embedding, if you like, of some kind of high-dimensional vector object. So examples include representations like word to veck and glove that encode word semantics. This has evolved in recent years into contextual semantics like word, feature vectors like sift, serve and orb that encode information about image contents and more modern neural network-based representations like decaf for recognizing what kind of object is in an image. We have feature vectors from used in recommended systems based on so-called two towers, neural network architecture and the discos on and on. So feature vectors are important these days and in a database system context one way of handling feature vectors is to do a so-called similarity join. So here we have two tables with the feature attribute and what we want to do in a similarity join is to combine the the troubles from the two tables that have feature vectors that are similar in some way. So the similarity measure that we're going to consider in this talk is inner product similarity. So if we have two D-dimensional real vectors, the inner product similarity is simply the sum over all dimensions of the product of the i-th coordinates of the two vectors. So for unit vectors, this also has a geometric interpretation. So we can think about the inner product as the length of the projection of one vector onto the other. So the larger inner product, the more similar the vectors are. So in order to do a similarity join, we need to set a threshold alpha and then the goal of the join is to find all pairs of vectors that have inner product of at least alpha. We're going to assume that alpha is strictly positive. And furthermore, we're going to restrict the attention to unit vectors, which is the most important case. There's a lot of things you can do if you have this primitive. And in particular, Rakhimean Rech showed in 2008 that there's a lot of similarity measures that can be reduced to inner product similarity of unit vectors. It's the most common approach to implementing similarity join. And I think this goes back to at least to Indic and Watwani 98. It's a candidate generation and filtering approach. So you take the two relations, you take the feature vectors x1, x2 and so on from one relation and y1, y2 and so on from the other one and you somehow generate candidates. The trivial way of doing this would be Cartesian product, but there are smarter ways to get a shorter candidate list in general. So we're going to assume this is some kind of black box. And then once you have all the candidate pairs, x, i, y, j, that are potentially something that needs a pair of tables that needs to be combined in the joint result, we simply go ahead and check the condition in this case, whether the inner product is alpha or more, and you output the joint result. So the issue with this is that there's a computational bottleneck. So in general, there's going to be a lot of candidate pairs, and these are all high dimensional vectors, so both from a memory transfer point of view and a computational point of view, this is pretty compute intensive operation. So the good news or the observation one can make in practice is that most of the candidate pairs actually are pretty far from fulfilling the condition. We'll formalize this in terms of a gap. So most of the candidate pairs actually have an inner product that is below alpha minus epsilon, for some epsilon that is not too small. And this we can exploit. So by inserting an extra face. So instead of immediately computing the inner product, we can do an approximate computation where we approximate the inner product. Well enough that we can identify most of the candidate pairs with an inner product less than alpha. And in particular, we are going to want to identify all of those that have an inner product less than alpha minus epsilon. And we can do this by simply approximating the inner product up to an additive error of epsilon and filtering away only the the pairs that have an inner product estimate of less than alpha minus epsilon. In this case, we are sure that we are not removing anything that actually has satisfies the joint condition. So the question that we asked a while back is how many bits of information do you actually need to store about the vectors? Do you really really need to store about the vectors? Do you really need the d dimensional real vectors or can you store some kind of succinct representation or sketch that allows you to do this estimation? So this focuses just on the on the information theoretical aspects of this. And so the notation just as a reminder, so d is the number of dimensions, alpha is the threshold of the similarity join and epsilon is the additive estimation error that we are going to allow. So this is not a new type of question. So there's lots of past work in particular on randomized approaches. So you can do things like Johnson-Linton-Strauss random projections or sim hash or feature hashing and you can get estimates of inner products. So one issue with randomized approaches is that they introduce false negative so that is candidate pairs where the estimate is well below alpha, even though the dot product or inner product is actually above alpha. Another issue is that all these randomized approaches are not robust against adversarial data. So if some kind of adversary in some way gains insight into our information about the random choices made in our method, it's possible to choose vectors that actually make it make it fail miserably. So for that reason, it's attractive to have the deterministic approaches. And again, there is quite some previous work starting with Fisher in 86, who introduced a method called pyramid quantization and more recently along and Clark-Tuck in 2017, presented as solution to the epsilon nets that gets down to the log one over epsilon bits. So this is our starting point. And the main result is a very precise upper and lower bound on the number of bits of information. So you can see it here. So it's d, the number of dimensions times the logarithm of a fraction, which I'm not going to read. And this is exactly the number of bits that you need up to an additive term of theta d. This is both necessary and sufficient. And just to help you pass this a little bit. So this this expression is somewhere between d log one over epsilon and half of that. And this is the one over epsilon and half of that. Okay, so if alpha is close to one, we're going to save a factor of two compared to d log one over epsilon. And if if alpha is small, it's going to be d log one over epsilon. Let me tell you a little bit about both the upper and the lower bound. So the upper bound is actually using techniques that are pretty well known. It's just that our analysis, our calculations are more precise than what was in the literature. So in particular, what we are going to do is to consider the dimensional grid with a suitable distance between points. And this turns out it turns out that epsilon over four square root of dimension is small enough. So we take a vector x and we find the nearest grid point x prime in that. So x prime is basically going to be our representation. You can also write that as a formula like this for the Ith coordinate of x prime. So this is really simple to implement. And then because we're dealing with unit vectors, we normalize x prime. It's not necessarily a unit vector. That actually represent this. What we need to store are the integers that are based on the coordinates of x. So it's enough to store these integers to reconstruct the grid point, in particular the normalize grid point. And you can argue pretty straightforwardly using standard information theory to really bounce on how much space do you need to store these integers that is going to be bounded by the expression on the previous slide. All right. So the lower bound is based on a packing argument. So we show that there's a large set C of vectors that actually require different encodings. So in particular, if you take two different vectors x and y from C, there exists some vector such that the inner product of that vector, cesa, is with x is more than alpha and the inner product with y is y and set is less than alpha minus epsilon. Okay. And this basically means that x and y cannot have the same representation because then we would get in trouble if we tried to compute the inner product with cesa. And what this means in turn is that since we have at least the size of C different representations, the encoding length must be at least the binary logarithm of the size of C. And if you do this carefully, so this includes integrals, the gamma function, trigonometric identities and lots of explicit computation, you end up with the bound claimed.
 My name is Rasmus Pei and I'm going to talk about the space complexity of inner product fillers.  This is joint work with my former student and postdoc Johan C. Wilson.  Traditional databases store things like integers,  booleans, dates and text. But in  recent years there's been a new kid on the block, the feature vector. So a feature vector is a  succinct vector representation or an embedding, if you like, of some kind of high-dimensional vector object.  So examples include  representations like word to veck and glove that encode word semantics.  This has evolved in recent years into contextual semantics like word,  feature vectors like sift, serve and orb that encode information about image contents and  more modern  neural network-based representations like decaf for recognizing what kind of object is in an image.  We have  feature vectors from used in recommended systems based on so-called two towers, neural network architecture and  the discos on and on. So feature vectors are important these days and  in a database system context one way  of handling feature vectors is to do a so-called similarity join. So here we have two  tables with the feature attribute and  what we want to do in a similarity join is to  combine the the troubles from the two tables that have feature vectors that are similar in some way.  So the similarity measure that we're going to consider in this talk is inner product similarity.  So if we have two  D-dimensional real vectors, the inner product similarity is simply the sum over all dimensions of  the product of the i-th coordinates of the two vectors.  So for unit vectors, this also has a geometric interpretation. So we can think about the inner product as the length of the  projection of one vector onto the other.  So the larger inner product, the more similar the vectors are.  So in order to do a similarity join, we need to set a threshold alpha  and then the goal of the join is to find all pairs of vectors that have inner product of at least alpha.  We're going to assume that alpha is strictly positive.  And furthermore, we're going to restrict the attention to unit vectors, which is the most important case.  There's a lot of things you can do if you have this primitive.  And in particular, Rakhimean Rech showed in 2008 that there's a lot of similarity measures that can be  reduced to inner product similarity of unit vectors.  It's the most common approach to implementing similarity join.  And I think this goes back to at least to Indic and Watwani 98.  It's a candidate generation and filtering approach.  So you take the two relations, you take the feature vectors x1, x2 and so on from one relation and y1, y2  and so on from the other one and you somehow generate candidates.  The trivial way of doing this would be Cartesian product, but there are smarter ways to get  a shorter candidate list in general.  So we're going to assume this is some kind of black box.  And then once you have all the candidate pairs, x, i, y, j, that are potentially something that needs a pair of  tables that needs to be combined in the joint result, we simply go ahead and check the condition in this case,  whether the inner product is alpha or more, and you output the joint result.  So the issue with this is that there's a computational bottleneck.  So in general, there's going to be a lot of candidate pairs, and these are all high dimensional vectors, so both from a  memory transfer point of view and a computational point of view, this is pretty compute intensive  operation.  So the good news or the observation one can make in practice is that most of the candidate pairs actually are pretty far from  fulfilling the condition.  We'll formalize this in terms of a gap. So most of the candidate pairs actually have an inner product that is below alpha minus epsilon, for some epsilon that is not too small.  And this we can exploit.  So by inserting an extra face.  So instead of immediately computing the inner product, we can do an approximate computation where we approximate the inner product.  Well enough that we can identify most of the candidate pairs with an inner product less than alpha.  And in particular, we are going to want to identify all of those that have an inner product less than  alpha minus epsilon.  And we can do this by simply  approximating the inner product up to an additive error of epsilon and  filtering away only the  the pairs that have an inner product estimate of less than alpha minus epsilon. In this case, we are sure that we are not  removing anything that  actually has  satisfies the joint condition.  So the question that we  asked a while back is how many bits of information do you actually need to store about the vectors? Do you really really need to store about the vectors?  Do you really need the d dimensional real vectors or can you store some kind of succinct representation or sketch that allows you to do this estimation?  So this focuses just on the on the information theoretical aspects of this.  And so the notation just as a reminder, so d is the number of dimensions, alpha is the threshold  of the similarity join and epsilon is the additive estimation error that we are going to allow.  So this is not a new type of question. So there's lots of past work in particular on randomized approaches.  So you can do things like Johnson-Linton-Strauss random projections or sim hash or feature hashing and you can get estimates of  inner products.  So one issue with  randomized approaches is that they introduce false negative  so that is candidate pairs where the estimate is  well below alpha, even though the dot product or inner product is actually above alpha.  Another issue is that all these randomized approaches are not robust against adversarial data. So if  some kind of adversary in some way gains insight  into our information about the random choices made  in our method, it's possible to choose vectors that actually make it make it fail miserably.  So for that reason, it's attractive to have  the deterministic approaches. And again, there is quite some previous work starting with  Fisher in 86, who introduced a method called pyramid quantization and  more recently along and Clark-Tuck  in 2017, presented as solution to the  epsilon nets that gets down to the log one over epsilon bits.  So this is our starting point. And the main result is a very precise  upper and lower bound on the number of bits of information.  So you can see it here. So it's d, the number of dimensions times the logarithm of  a fraction,  which I'm not going to read.  And this is exactly the number of  bits that you need up to an additive term of theta d.  This is both necessary and sufficient.  And just to help you pass this a little bit. So this  this expression is somewhere between d log one over epsilon  and half of that.  And this is the  one over epsilon and half of that.  Okay, so if alpha is close to one, we're going to  save a factor of two compared to d log one over epsilon.  And if if alpha is small, it's going to be d log one over epsilon.  Let me tell you a little bit about both the upper and the lower bound.  So the upper bound is actually using  techniques that are pretty well known. It's just that our  analysis, our calculations are more precise than what was in the literature.  So in particular, what we are going to do is to consider  the dimensional grid with a suitable distance between points.  And this turns out it turns out that epsilon over four square root of dimension is  small enough.  So we take  a vector x and we find the nearest grid point x prime in that.  So x prime is basically going to be our representation.  You can also write that as a formula like this for the Ith coordinate of x prime.  So this is really simple to implement.  And then because we're dealing with unit vectors, we normalize x prime.  It's not necessarily a unit vector.  That actually represent this.  What we need to store are the integers that are based on the coordinates of x.  So it's enough to store these integers to reconstruct the grid point,  in particular the normalize grid point.  And you can argue pretty straightforwardly using standard information theory  to really bounce on how much space do you need to store these integers that is going to be bounded by the expression on the previous slide.  All right.  So the lower bound is based on a packing argument.  So we show that there's a large set C of vectors that actually require different encodings.  So in particular, if you take two different vectors x and y from C,  there exists some vector such that the inner product of that vector,  cesa, is with x is more than alpha and the inner product with y is y and set is less than alpha minus epsilon.  Okay.  And this basically means that x and y cannot have the same representation because then we would get in trouble if we tried to compute the inner product with cesa.  And what this means in turn is that since we have at least the size of C different representations,  the encoding length must be at least the binary logarithm of the size of C.  And if you do this carefully, so this includes integrals, the gamma function, trigonometric identities and lots of explicit computation,  you end up with the bound claimed.
PaghSivertsen_0_395.png PaghSivertsen_396_611.png PaghSivertsen_612_779.png PaghSivertsen_780_959.png PaghSivertsen_960_2123.png PaghSivertsen_2124_2891.png PaghSivertsen_2892_3767.png PaghSivertsen_3768_4799.png PaghSivertsen_4800_6911.png PaghSivertsen_6912_7595.png PaghSivertsen_7596_8915.png PaghSivertsen_8916_9503.png PaghSivertsen_9504_9683.png PaghSivertsen_9684_9743.png PaghSivertsen_9744_10055.png PaghSivertsen_10056_10463.png PaghSivertsen_10464_11627.png PaghSivertsen_11628_12275.png PaghSivertsen_12276_13103.png PaghSivertsen_13104_13799.png PaghSivertsen_13800_14843.png PaghSivertsen_14844_16367.png PaghSivertsen_16368_17903.png PaghSivertsen_17904_18201.png