Reverse Engineering Google Sets

Have you taken a look in Google Labs - Google’s Sets? It’s quite fascinating
feature with wide ranging applications. The only thing that might be more interesting is the possible algorithm behind it.

The secrets are revealed in the properties

1. Google sets aren’t ordered
   


2. The sets are generic
   


3. Extremely large sample data similar to numbers and alphabet characters appear less logical, implying too many samples
   

Here’s an algorithm of how it could potentially be recreated

1. Scan and parse the web for simple html 'tables', and/or 'lists', filter using textual content only. This can be done by leveraging simple spidering techniques widely employed by search engines.
   


2. Break up each column into fields and store each field as a record, including a set id uniquely identifying the column.
   


3. Break up each row into fields and store each field as a record, including a set id uniquely identifying the row.
   


4. repeat continuously for different tables on different sites
   


5. Store the results for later use in a database table similar to
   

CREATE TABLE sets (
field_id int NOT NULL,
set_id int NOT NULL,
field varchar (255) NOT NULL
) 

For Example

If we had 2 tables to pares similar to

• Nick,Male


• John,Male

and

• Product,Cost


• Orange,5


• Banana,6

The sets dataset table would be

• field_id,set_id,Field


• 1,1,Nick


• 2,1,John


• 3,2,Male


• 4,2,Male


• 5,3,Nick


• 6,3,Male


• 7,4,John


• 8,4,Male


• 9,5,Product


• 10,5,Orange


• 11,5,Banana


• 12,6,Cost


• 13,6,5


• 14,6,6


• 15,7,Product


• 16,7,Cost


• 17,8,Orange


• 18,8,5


• 19,9,Banana


• 120,9,6

Notice

1. Header records are not treaded any differently
   

Getting the Sets

The Sybase ASE query that can be used to generate the desired set is then:

Select top 15
 field,  count(set_id)
From
 sets
where
 set_id in ( select set_id from sets where field in ("apple","Orange") )
group by
 field
order by
 count(set_id) DESC

Comments

The above SQL will generate sets whose members are centered on “apples” and “oranges”. We use the top 15 option to limit the results to only the top 15. If we were to take the entire list, you would see it get less and less accurate as the count goes to 1. The elegance is in the count function, and how it clusters popular results together.

Tips

1. To generate closer matched sets, favor scanning the web pages containing each field discovered.
   


2. To get results with similar accuracy to Google Sets, Try to collect about 2 million fields
   

Enhancements

1. Ordering the results by the average field_id


2. Adding the ability to subtract sets by removing set_id’s

Other Uses for similar algorithm

This algorithm could also be used to create sets of commonly related keywords by scanning web pages Meta keyword tags, Knowing that most of the keywords will be related to each other some how

Check it out first hand at questsin.net!!!