CODEWITHSUNDEEP
sqldatabasealgorithmweb-applications
Ben
Ben

Reputation: 2578

Find Similar Rows in Database

I try to design my app to find database entries which are similar.

Let's for example take the table car (Everything in one table to keep the example simple):

CarID  |  Car Name  | Brand | Year | Top Speed | Performance | Displacement | Price
1         Z3          BMW     1990    250          5.4           123           23456
2         3er         BMW     2000    256          5.4           123           23000
3         Mustang     Ford    2000    190          9.8           120           23000

Now i want to do Queries like that:

"Search for Cars similar to Z3 (all brands)" (ignore "Car Name")

Similar in this context means that the row where the most columns are exactly the same is the most similar.

In this example it would be "3er BMW" since 2 columns(Performance and Displacement are the same)

Can you give me hints how to design database queries/application like that. The application gonna be really big with a lot of entries.

Also I would really appreciate useful links or books. (No problem for me to investigate further if i know where to search or what to read)

Upvotes: 8

Views: 5441

Answers (5)

Albin Sunnanbo
Albin Sunnanbo

Reputation: 47038

Not really an answer to your question, but you say you have lot of entries, you should consider normalizing your car table, move Brand to a separate table and "Car name"/model to a separate table. This will reduce the amount of data to compare during the lookups.

Upvotes: 1

Skarab
Skarab

Reputation: 7141

To solve your problem, you have to use a cluster algorithm. First, you need define a similarity metric, than you need to count the similarity between your input tuples (all Z3) and the rest of the database. You can speed up the process using algorithms, such as k-means. Please take a look on this question, there you will find a discussion on similar problem as yours - Finding groups of similar strings in a large set of strings.

This link is very helpful as well: http://matpalm.com/resemblance/.

Regarding the implementation if you have a lot of tuples (and more than several machines) you can use http://mahout.apache.org/. It is machine learning framework based on hadoop. You will need a lot of computation power, because cluster algorithms are complex.

Upvotes: 2

Gimly
Gimly

Reputation: 6175

The methods of finding relationships and similarities in data is called Data Mining, in your case you could already try clustering and classify your data in order to see what are the different groups that show up.

I think this book is a good start for an introduction to data mining. Hope this helps.

Upvotes: 2

Aaron Digulla
Aaron Digulla

Reputation: 328594

Have a look at one of the existing search engines like Lucene. They implement a lot of things like that.

This paper might also be useful: Supporting developers with natural language queries

Upvotes: 1

vc 74
vc 74

Reputation: 38179

You could try to give each record a 'score' depending on its fields

You could weigh a column's score depending on how important the property is for the comparison (for instance top speed could be more important than brand)

You'll end up with a score for each record, and you will be able to find similar records by comparing scores and finding the records that are +/- 5% (for example) of the record you're looking at

Upvotes: 4

Related Questions