The nearest neighbor \u00c2\u00a0(NN) and k<\/em>-NN problems<\/h3>\nThe nearest neighbor question is this: Given a large set of points (P<\/em>), pre-process it so that later, when you receive a new query point (q<\/em>), you can very quickly return the subset of original points P<\/em> which are within a fixed radius r<\/em> of q<\/em> (the desired output is the set near(q<\/em>, P<\/em>) = {p<\/em> in P<\/em> : ||p<\/em> – q<\/em>|| < r<\/em>}). \u00c2\u00a0The radius r<\/em> is chosen in advance and\u00c2\u00a0doesn’t change, although you can store different outputs of the pre-processing which can handle multiple radii. \u00c2\u00a0Technically speaking, the NN problem actually asks for the single point in P<\/em> closest to q<\/em>, and the k<\/em>-NN problem asks for the k<\/em> points in P<\/em> closest to q<\/em>; we introduce the different version with the radius because it is close enough for practical purposes, and is more directly solved by LSH algorithms.<\/p>\n![\"\"](\"http:\/\/bynomial.com\/blog\/wp-content\/uploads\/2010\/06\/File-KnnClassification.png\" "\\"File-KnnClassification\\"")
<\/p>\n
Stuff you can do with NN or k-NN<\/h3>\n
Unless you’re a quasi-academic algorithm junkie like me, your eyes probably glazed over a little in that last paragraph. \u00c2\u00a0Despite sounding abstract, these problems have a myriad of very real applications.<\/p>\n
Recommendations<\/h4>\n
For example, let’s say you have a user database with usage data per user, such as ratings from netflix or yelp users. \u00c2\u00a0Temporarily forgetting about missing fields (that’s a somewhat independent challenge), you could represent every user as a vector, and then quickly find each user’s 10 “nearest neighbors,” which in this case means the 10 other users most like the query user. \u00c2\u00a0From there, you can combine those 10 users to get a reasonable guess at what else the query user likes, and recommend the guessed-as-highly-rated items to the query user (excluding things they’ve already rated).<\/p>\n
Handwriting recognition<\/h4>\n
Written characters can be encoded as an image, and images can be further reduced in a way that allows for some rotations and skews to get a relatively small thumbnail – let’s say at 500 coordinates, each a float arrived at by some function of a small black & white image. \u00c2\u00a0If you made the thumbnails well, then slightly different ways of writing the number ‘7’ will result in slightly different – but mostly similar – thumbnails. \u00c2\u00a0As vectors, they will be close together.<\/p>\n
Later you get a new image as input, and your job is to figure out what character it is. \u00c2\u00a0You get the thumbnail in the same way, and now just do a quick lookup via LSH and return the most-common character in that set. \u00c2\u00a0(This general method can actually be used for any machine learning classification problem.)<\/p>\n
Duplicate detection<\/h4>\n
Suppose you’re a site like youtube with user-generated content and copyright lawyers at other companies who are feeling sue-happy. \u00c2\u00a0Your job is to quickly and efficiently find any user-uploaded videos that violate copyright. \u00c2\u00a0You have a database of known-copyright material, but the tricky part is that users will mess with these videos in small ways so that they are never exact copies.<\/p>\n
LSH to the rescue! \u00c2\u00a0Because any LSH-based lookup is automatically error tolerant, the copies don’t have to be exact matches. \u00c2\u00a0You can choose a meaningful threshold for what it means to be a “copy,” or perhaps simply flag a possible copy for further scrutiny with a slower algorithm.<\/p>\n
Fraud detection<\/h4>\n
This case is theoretically similar to handwriting recognition. \u00c2\u00a0Suppose you’re a bank or credit card company, and you want to figure out as quickly as possible\u00c2\u00a0when a credit or debit card is stolen. \u00c2\u00a0Just as in the handwriting case, you have a set of sample data (which would look like times, locations, and purchase prices with numerical categories), and you do an LSH lookup for the nearest usage cases; you might also want to use thumbnails that can better match the numerically-close scale with the fraud-valid scale.<\/p>\n
I could go on for a while. \u00c2\u00a0Basically anything with numeric data that also involves some error-tolerance, a lot of data to go through or large data points (like videos), and the need for speed.<\/p>\n
How it works<\/strong><\/h2>\nThe full details are left to other places, such as the paper and slides below; but here is the basic idea:<\/p>\n
An LSH approach is like asking a group of people to write down their zip codes. \u00c2\u00a0You keep a zipcode\/name table sorted by zip code. \u00c2\u00a0When a new person arrives, you ask their zip code, and do a quick look in the table and can tell them who lives near them.<\/p>\n
The zip code function is a real-life locality sensitive hash. \u00c2\u00a0It has these properties:<\/p>\n
\n- It’s a mapping from data to a discrete (non-continuous) set<\/li>\n
- Data points (people) with the same hash value (zip code) tend to live close together<\/li>\n<\/ul>\n
This is nice because it allows for fast lookups. \u00c2\u00a0So far this describes the general LSH idea, which is not new.<\/p>\n
What is new in this algorithm is how it computes the hash values. \u00c2\u00a0Instead of relying on dimension reduction, it relies on using a tessellation (tiling) of d<\/em>-dimensional space with one shape. \u00c2\u00a0First imagine this shape is a hypercube (d<\/em>-dimensional cube), so we have a fixed grid of cubes in space. \u00c2\u00a0If we turn every corner into a hash table bin, then each hypercube will be thought of as a neighbor of each adjacent cube. \u00c2\u00a0In other words, every corner of every cube gets its own zip code, and we call two people neighbors if any<\/em> of their many zip codes match.<\/p>\nBut this idea by itself is very bad for high dimensions – it is attacked by the curse of dimensionality<\/a>. \u00c2\u00a0The number of corners is 2d<\/em><\/sup>, and the number of neighboring hypercubes is 3d<\/em><\/sup>-1. \u00c2\u00a0So the cost for us is exponentially-many hash outputs of every point, and the gain is that we can match exponentially-many neighboring shapes (hypercubes).<\/p>\nThe new algorithm solves this by using a simplex<\/a> to tile space. \u00c2\u00a0A simplex is a d<\/em>-dimensional triangle; so it has d<\/em>+1 corners in d<\/em> dimensions. \u00c2\u00a0Now we pay the cost of having linearly-many hash outputs of every point with the gain of super-exponentially-many neighboring shapes! \u00c2\u00a0Compared to the hypercube approach, it is a clear win.<\/p>\nThe iPad app<\/h2>\n
The iPad app demonstrates the 2d version of the algorithm. \u00c2\u00a0It generates a set of random points, and plots these on the screen. \u00c2\u00a0When you touch the screen, it connects your fingertip to the neighbors found by the LSH algorithm. \u00c2\u00a0It also can display the proximity graph found during preprocessing, and allow you to switch on\/off the skew correction component of the algorithm (it’s generally more accurate while on).<\/p>\n
![\"\"](\"http:\/\/bynomial.com\/blog\/wp-content\/uploads\/2010\/06\/LSH-demo-screenshot.png\" "\\"LSH")
<\/p>\n
The code for this app is open source under the Apache 2 license, and currently hosted as ipadlocalityhash on google code<\/a>.<\/p>\nSource & References<\/h2>\n
The official open-source version of the demo code can be found here:<\/p>\n
http:\/\/code.google.com\/p\/ipadlocalityhash\/<\/a><\/p>\nIf you want to skip a couple links, you can also download the xcode project source (for v1.0) right here:<\/p>\n
ipadlocalityhash.tar.gz<\/a><\/p>\nFinally, here are links to the original paper describing the algorithm, and some slides I recently used to present it (with the help of this demo app):<\/p>\n
https:\/\/www.siam.org\/proceedings\/soda\/2010\/SODA10_094_neylont.pdf<\/a><\/p>\n
<\/p>\n
Stuff you can do with NN or k-NN<\/h3>\n
Unless you’re a quasi-academic algorithm junkie like me, your eyes probably glazed over a little in that last paragraph. \u00c2\u00a0Despite sounding abstract, these problems have a myriad of very real applications.<\/p>\n
Recommendations<\/h4>\n
For example, let’s say you have a user database with usage data per user, such as ratings from netflix or yelp users. \u00c2\u00a0Temporarily forgetting about missing fields (that’s a somewhat independent challenge), you could represent every user as a vector, and then quickly find each user’s 10 “nearest neighbors,” which in this case means the 10 other users most like the query user. \u00c2\u00a0From there, you can combine those 10 users to get a reasonable guess at what else the query user likes, and recommend the guessed-as-highly-rated items to the query user (excluding things they’ve already rated).<\/p>\n
Handwriting recognition<\/h4>\n
Written characters can be encoded as an image, and images can be further reduced in a way that allows for some rotations and skews to get a relatively small thumbnail – let’s say at 500 coordinates, each a float arrived at by some function of a small black & white image. \u00c2\u00a0If you made the thumbnails well, then slightly different ways of writing the number ‘7’ will result in slightly different – but mostly similar – thumbnails. \u00c2\u00a0As vectors, they will be close together.<\/p>\n
Later you get a new image as input, and your job is to figure out what character it is. \u00c2\u00a0You get the thumbnail in the same way, and now just do a quick lookup via LSH and return the most-common character in that set. \u00c2\u00a0(This general method can actually be used for any machine learning classification problem.)<\/p>\n
Duplicate detection<\/h4>\n
Suppose you’re a site like youtube with user-generated content and copyright lawyers at other companies who are feeling sue-happy. \u00c2\u00a0Your job is to quickly and efficiently find any user-uploaded videos that violate copyright. \u00c2\u00a0You have a database of known-copyright material, but the tricky part is that users will mess with these videos in small ways so that they are never exact copies.<\/p>\n
LSH to the rescue! \u00c2\u00a0Because any LSH-based lookup is automatically error tolerant, the copies don’t have to be exact matches. \u00c2\u00a0You can choose a meaningful threshold for what it means to be a “copy,” or perhaps simply flag a possible copy for further scrutiny with a slower algorithm.<\/p>\n
Fraud detection<\/h4>\n
This case is theoretically similar to handwriting recognition. \u00c2\u00a0Suppose you’re a bank or credit card company, and you want to figure out as quickly as possible\u00c2\u00a0when a credit or debit card is stolen. \u00c2\u00a0Just as in the handwriting case, you have a set of sample data (which would look like times, locations, and purchase prices with numerical categories), and you do an LSH lookup for the nearest usage cases; you might also want to use thumbnails that can better match the numerically-close scale with the fraud-valid scale.<\/p>\n
I could go on for a while. \u00c2\u00a0Basically anything with numeric data that also involves some error-tolerance, a lot of data to go through or large data points (like videos), and the need for speed.<\/p>\n
How it works<\/strong><\/h2>\nThe full details are left to other places, such as the paper and slides below; but here is the basic idea:<\/p>\n
An LSH approach is like asking a group of people to write down their zip codes. \u00c2\u00a0You keep a zipcode\/name table sorted by zip code. \u00c2\u00a0When a new person arrives, you ask their zip code, and do a quick look in the table and can tell them who lives near them.<\/p>\n
The zip code function is a real-life locality sensitive hash. \u00c2\u00a0It has these properties:<\/p>\n
\n- It’s a mapping from data to a discrete (non-continuous) set<\/li>\n
- Data points (people) with the same hash value (zip code) tend to live close together<\/li>\n<\/ul>\n
This is nice because it allows for fast lookups. \u00c2\u00a0So far this describes the general LSH idea, which is not new.<\/p>\n
What is new in this algorithm is how it computes the hash values. \u00c2\u00a0Instead of relying on dimension reduction, it relies on using a tessellation (tiling) of d<\/em>-dimensional space with one shape. \u00c2\u00a0First imagine this shape is a hypercube (d<\/em>-dimensional cube), so we have a fixed grid of cubes in space. \u00c2\u00a0If we turn every corner into a hash table bin, then each hypercube will be thought of as a neighbor of each adjacent cube. \u00c2\u00a0In other words, every corner of every cube gets its own zip code, and we call two people neighbors if any<\/em> of their many zip codes match.<\/p>\nBut this idea by itself is very bad for high dimensions – it is attacked by the curse of dimensionality<\/a>. \u00c2\u00a0The number of corners is 2d<\/em><\/sup>, and the number of neighboring hypercubes is 3d<\/em><\/sup>-1. \u00c2\u00a0So the cost for us is exponentially-many hash outputs of every point, and the gain is that we can match exponentially-many neighboring shapes (hypercubes).<\/p>\nThe new algorithm solves this by using a simplex<\/a> to tile space. \u00c2\u00a0A simplex is a d<\/em>-dimensional triangle; so it has d<\/em>+1 corners in d<\/em> dimensions. \u00c2\u00a0Now we pay the cost of having linearly-many hash outputs of every point with the gain of super-exponentially-many neighboring shapes! \u00c2\u00a0Compared to the hypercube approach, it is a clear win.<\/p>\nThe iPad app<\/h2>\n
The iPad app demonstrates the 2d version of the algorithm. \u00c2\u00a0It generates a set of random points, and plots these on the screen. \u00c2\u00a0When you touch the screen, it connects your fingertip to the neighbors found by the LSH algorithm. \u00c2\u00a0It also can display the proximity graph found during preprocessing, and allow you to switch on\/off the skew correction component of the algorithm (it’s generally more accurate while on).<\/p>\n
<\/p>\n
The code for this app is open source under the Apache 2 license, and currently hosted as ipadlocalityhash on google code<\/a>.<\/p>\nSource & References<\/h2>\n
The official open-source version of the demo code can be found here:<\/p>\n
http:\/\/code.google.com\/p\/ipadlocalityhash\/<\/a><\/p>\nIf you want to skip a couple links, you can also download the xcode project source (for v1.0) right here:<\/p>\n
ipadlocalityhash.tar.gz<\/a><\/p>\nFinally, here are links to the original paper describing the algorithm, and some slides I recently used to present it (with the help of this demo app):<\/p>\n
https:\/\/www.siam.org\/proceedings\/soda\/2010\/SODA10_094_neylont.pdf<\/a><\/p>\n
This is nice because it allows for fast lookups. \u00c2\u00a0So far this describes the general LSH idea, which is not new.<\/p>\n
What is new in this algorithm is how it computes the hash values. \u00c2\u00a0Instead of relying on dimension reduction, it relies on using a tessellation (tiling) of d<\/em>-dimensional space with one shape. \u00c2\u00a0First imagine this shape is a hypercube (d<\/em>-dimensional cube), so we have a fixed grid of cubes in space. \u00c2\u00a0If we turn every corner into a hash table bin, then each hypercube will be thought of as a neighbor of each adjacent cube. \u00c2\u00a0In other words, every corner of every cube gets its own zip code, and we call two people neighbors if any<\/em> of their many zip codes match.<\/p>\n But this idea by itself is very bad for high dimensions – it is attacked by the curse of dimensionality<\/a>. \u00c2\u00a0The number of corners is 2d<\/em><\/sup>, and the number of neighboring hypercubes is 3d<\/em><\/sup>-1. \u00c2\u00a0So the cost for us is exponentially-many hash outputs of every point, and the gain is that we can match exponentially-many neighboring shapes (hypercubes).<\/p>\n The new algorithm solves this by using a simplex<\/a> to tile space. \u00c2\u00a0A simplex is a d<\/em>-dimensional triangle; so it has d<\/em>+1 corners in d<\/em> dimensions. \u00c2\u00a0Now we pay the cost of having linearly-many hash outputs of every point with the gain of super-exponentially-many neighboring shapes! \u00c2\u00a0Compared to the hypercube approach, it is a clear win.<\/p>\n The iPad app demonstrates the 2d version of the algorithm. \u00c2\u00a0It generates a set of random points, and plots these on the screen. \u00c2\u00a0When you touch the screen, it connects your fingertip to the neighbors found by the LSH algorithm. \u00c2\u00a0It also can display the proximity graph found during preprocessing, and allow you to switch on\/off the skew correction component of the algorithm (it’s generally more accurate while on).<\/p>\n The code for this app is open source under the Apache 2 license, and currently hosted as ipadlocalityhash on google code<\/a>.<\/p>\n The official open-source version of the demo code can be found here:<\/p>\n http:\/\/code.google.com\/p\/ipadlocalityhash\/<\/a><\/p>\n If you want to skip a couple links, you can also download the xcode project source (for v1.0) right here:<\/p>\n ipadlocalityhash.tar.gz<\/a><\/p>\n Finally, here are links to the original paper describing the algorithm, and some slides I recently used to present it (with the help of this demo app):<\/p>\n https:\/\/www.siam.org\/proceedings\/soda\/2010\/SODA10_094_neylont.pdf<\/a><\/p>\nThe iPad app<\/h2>\n
<\/p>\nSource & References<\/h2>\n