Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Have a look at <a href="http://en.wikipedia.org/wiki/Locality-sensitive_hashing" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Locality-sensitive_hashing</a>. One very simple approach would be to divide up each address (or whatever) into a set of overlapping n-grams. This STACKOVERFLOW becomes the set {STACKO, TACKO, ACKOV, CKOVE... , RFLOW}. Then use a large hash-table or sort-merge to find colliding n-grams and check collisions with a fuzzy matcher. Thus STACKOVERFLOW and SXACKOVRVLOX will collide because both are associated with the colliding n-gram ACKOV.</p> <p>A next level up in sophistication is to pick an random hash function - e.g. HMAC with an arbitrary key, and of the n-grams you find, keep only the one with the smallest hashed value. Then you have to keep track of fewer n-grams, but will only see a match if the smallest hashed value in both cases is ACKOV. There is obviously a trade-off here between the length of the n-gram and the probability of false hits. In fact, what people seem to do is to make n quite small and get higher precision by concatenating the results from more than one hash function in the same record, so you need to get a match in multiple different hash functions at the same time - I presume the probabilities work out better this way. Try googling for "duplicate detection minhash"</p>
    singulars
    1. This table or related slice is empty.
    1. POFuzzy matching deduplication in less than exponential time?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USWalter Stabosz
    1. USmcdowella
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFuzzy matching deduplication in less than exponential time?
      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. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYes! I think this could be what I am looking for. I did some reading up on LSH, and I'm a little lost in terms of implementing it. The idea seems to be to calculate the hash of the values in such a way that similar values have a high probability of colliding hashes. Then you could run more precise algorithms on values with colliding hashes. Basically, reduce the dimensionality to reduce computational intensity. What I don't understand is what hashing function to use - aren't they designed to try to minimize collisions? Are we talking about hash functions like SHA or MD5?
      singulars
      1. PO
      1. USDave W.
    2. COGood hash functions - such as SHA - are defined to look like random functions, which do produce fewer collisions than some very bad hash function. But the calculations that justify LSH assume perfectly random hash functions as building blocks, so that is fine. Bad hash functions produces collisions by hashing similar inputs to the same output, but LSH doesn't rely on this at all. It just relies on the hash function being consistent, so that if h(ACKOV) = 13 in one place, h(ACKOV) = 13 in another place. If you find a good practical writeup of LSH, use the hash function in the writeup.
      singulars
      1. PO
      1. USmcdowella
    3. COI think that makes sense :) ... any chance you would know of such a writeup, or at least a direction to look? My attempts so far have been largely fruitless. I've turned up several highly technical resources, but they are more complex than I can handle given my current background.
      singulars
      1. PO
      1. USDave W.
 

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