Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The best tutorial I have seen for LSH is in the book: Mining of Massive Datasets. Check Chapter 3 - Finding Similar Items <a href="http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf" rel="noreferrer">http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf</a></p> <p>Also I recommend the below slide: <a href="http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf" rel="noreferrer">http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf</a> . The example in the slide helps me a lot in understanding the hashing for cosine similarity.</p> <p>I borrow two slides from <a href="http://www.cs.jhu.edu/~vandurme/papers/VanDurmeLallACL10-slides.pdf" rel="noreferrer">Benjamin Van Durme &amp; Ashwin Lall, ACL2010</a> and try to explain the intuitions of LSH Families for Cosine Distance a bit. <img src="https://i.stack.imgur.com/xYCSJ.png" alt="enter image description here"></p> <ul> <li>In the figure, there are two circles w/ <strong>red</strong> and <strong>yellow</strong> colored, representing two two-dimensional data points. We are trying to find their <a href="http://en.wikipedia.org/wiki/Cosine_similarity" rel="noreferrer">cosine similarity</a> using LSH.</li> <li>The gray lines are some uniformly randomly picked planes.</li> <li>Depending on whether the data point locates above or below a gray line, we mark this relation as 0/1. </li> <li>On the upper-left corner, there are two rows of white/black squares, representing the signature of the two data points respectively. Each square is corresponding to a bit 0(white) or 1(black). </li> <li>So once you have a pool of planes, you can encode the data points with their location respective to the planes. Imagine that when we have more planes in the pool, the angular difference encoded in the signature is closer to the actual difference. Because only planes that resides between the two points will give the two data different bit value. </li> </ul> <p><img src="https://i.stack.imgur.com/27nSY.png" alt="enter image description here"></p> <ul> <li>Now we look at the signature of the two data points. As in the example, we use only 6 bits(squares) to represent each data. This is the LSH hash for the original data we have.</li> <li>The hamming distance between the two hashed value is 1, because their signatures only differ by 1 bit.</li> <li>Considering the length of the signature, we can calculate their angular similarity as shown in the graph.</li> </ul> <p>I have some sample code (just 50 lines) in python here which is using cosine similarity. <a href="https://gist.github.com/94a3d425009be0f94751" rel="noreferrer">https://gist.github.com/94a3d425009be0f94751</a></p>
    singulars
    1. This table or related slice is empty.
    1. POHow to understand Locality Sensitive Hashing?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USgreeness
    1. USgreeness
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow to understand Locality Sensitive Hashing?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COwhy it is called locality sensitive ?because the assignement of each bit is depend on the locality of the data point towards each plan ?
      singulars
      1. PO
      1. USnawara
    2. COlocality sensitive -- data points that are located close to each other are mapped to similar hashes (in same bucket with high probability).
      singulars
      1. PO
      1. USgreeness
    3. COSorry I am late in this topic but I had a question about the cosine. The presentation says that the bit value is one if the dot product between the actual vector and the plane vector >= 0 or else it is 0. What is the direction of the plane vector because angles between 90 degrees and 180 degrees also will give a cosine which is negative. I suppose each plane is composed of two vectors and we take the smaller angle that is made with the actual vector.
      singulars
      1. PO
      1. USvkaul11
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload