Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

If I have n rows in a database, and I want to compare every row against each other, how many loops (or processes) would I need to do.

Is it n2? (so if I have 30,000 rows then it would be 900,000,000)

Or is it:

for (i = 0; i < 30000; i++) {
    for (j = i + 1; j < 30000; j++) [
         // Process
    }
}

If it is the later, then how many processes is that (and is there an equation to work it out, given n)?

Also if I have to process each row y times, how does that affect the calculations?

I need to check a database of companies for possible duplicates. To check, they want to do a similarity check on common fields like business name, phone number, etc. If a field difference is under a certain percentage threshold, then mark it as a possible duplicate. I can code this fine by my self, but I am curious about he performance ramifications.

share|improve this question
2  
Please mark your homework with the [homework] tag. And, also, please read up on the definitions for O in en.wikipedia.org/wiki/Big_O_notation. This kind of thing is pretty well-defined. If you read the wikipedia article first, you might be able to clarify your question to point to the specific part of the definition you don't understand. –  S.Lott Jun 3 '11 at 11:48
    
@S.Lott, this is not homework, I need to check a database of companies for possible duplicates. To check, they want to do a similarity check on common fields like business name, phone number, etc. If a field difference is under a certain percentage threshold, then mark it as a possible duplicate. I can code this fine by my self, but I am curious about he performance ramifications. –  Petah Jun 3 '11 at 11:52
4  
@S.Lott, please don't be so aggressive. I come to this site to seek insight into complicated problems, before I dive into writing a gigantic SQL loop. I reply to comments, and follow advice, so help is appreciated, arrogance is not. –  Petah Jun 3 '11 at 12:05
3  
@Petah: "aggressive"? Your problem is non-trivial, but your description (here) is vague. Your problem is very, very complex. I'm trying to make that clear. I apologize if you have feelings of aggressive. I can't really control your feelings. I'm striving for clarity. Your problems is very complex. –  S.Lott Jun 3 '11 at 12:08
1  
@Petah, Is it SQL database ? If yes I suggest you inner join the table with itself, retrieve the result paged (20 records at a time for ex.) to the client and have only one loop. It will perform better this way IMO and you will not have to have all the data in memory while processed. –  M.Sameer Jun 3 '11 at 14:23
show 4 more comments

4 Answers 4

up vote 11 down vote accepted

It's O(n2) by definition.

The distinction between n2 and your n*(n-1)/2 algorithm doesn't matter.

You need to work out a far, far better algorithm for locating "duplicates". This "similarity check" business is probably the kind of thing that requires a much smarter algorithm than a SQL query.

You need to read about fuzzy hashing and metaphone and related techniques. You need to very clearly define "similar" and finding a way to detect similar. Doing billions of database operations will take days of run-time.


A good rule of thumb is that your RDBMS can fetch about 5000 rows per second.

That's 180,000 seconds (50 hours) to do one of these O(n2) queries.


A few attributes (let's say a dozen) from 30,000 rows is 360,000 objects. That fits in memory in any computer larger than iPhone.

Here's your algorithm.

  1. Read all 30,000 rows into memory.

  2. Compute hashes or summaries or whatevers for your dozen or so fields, creating hashmaps or treemaps or whatever makes sense.

    for x in object_list:
        name_map[soundex(x.name)].append(x)
        other_map[transformatioN(x.other)].append(x)
    
  3. Write statistical summary reports to be sure your similarity measurements make some kind of rational sense.

    print( len(name_map), "similar names out of", len(object_list) )
    
  4. When you have results you like, update the database with the results.

    for n in name_map:
        similar_set = [ s.primary_key for s in name_map[n] ]
        c.execute( "UPDATE SOMETHING SET NAME_KEY=n WHERE ID IN ( %0 )", similar_set )
    

This is not a good fit for SQL. But it is a good fit for "all-in memory".

share|improve this answer
    
So My big O computation was right :) thanks –  dwarfy Jun 3 '11 at 12:06
add comment

I think it's ((n*(n-1))/2)

Your code loop is correct, It's (n*n-1) because you don't have to compare each row to himself and divided by 2 because row X compared to row Y is the same as row Y compared to row X

Looking at the following it should be clear (if you see it as table with n rows and n columns) :

 123
1-xx
2 -x
3  -

3*2/2 = 3

 1234
1-xxx
2 -xx
3  -x
4   -

4*3/2 = 6

By the way I think it's still in O(n^2) because O((n*(n-1))/2) = O((n*(n-1))) = O((n*n)) = O(n^2) BUT I might be wrong ! Anybody to correct me ?

share|improve this answer
    
Did you mean (n*(n-1))/2?, Also, if I had to process each row 4 times, would it be (n*(n-1))/2*4? –  Petah Jun 3 '11 at 11:59
    
Yep I meant that. And why would you want to process each row 4 times ? –  dwarfy Jun 3 '11 at 12:01
1  
You should go over the rows only ONCE and compare multiple variables if necessary at each time –  dwarfy Jun 3 '11 at 12:03
    
Sorry, what I mean by process a row 4 times, is process 4 different columns in each row. So if 1 column process takes x time, and I have to do that 4 times per row. Then the time taken will be (n*(n-1))/2*4? –  Petah Jun 3 '11 at 12:11
1  
@Petah, Sorry I'm lost ... But Computationally speaking I think that doing 1 operations or 4 operations is still in O(1) so I mean doing 4 operations doesn't cost more than doing one operation. I know it sounds strange but it's true.. The cost of looping and fetching the rows in memory is far more than the cost of primitive operations .. –  dwarfy Jun 3 '11 at 12:16
show 2 more comments

Depending in the actual parameters of your problem, this may not actually be O(n^2). If you can write a query in a way that the database can use indexes , then it may not need to actually compare every row. In this case you could be looking at a O(n*Log(n)) solution.

share|improve this answer
    
+1, there's likely no need to process each row 30,000 times. Take advantage of what databases do best. –  GrandmasterB Jun 3 '11 at 18:43
add comment

Similar to the answer provided by WuHoUnited, you can significantly reduce the number of comparisons needed by creating clusters or match codes. Basically you create a cluster field that contains some salient feature of the record and compare only records where the cluster field matches. For example you might create a cluster field that contains the first 5 characters of the Company Name. Now you only need to match the records that fall into that cluster. Depending on your data and the accuracy you require you can add other data, such as postal code or partial phone number number to the cluster.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.