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.

I find my self in a situation, where I need to program a service, that can determine if two object in a huge database are the same. For simplicity, let's say it's used cars, and I want to determine if they are the exact same, based on various attributes e.g. brand, model name, year, milage, price, color etc. The problem is, that some of the attributes are obversely more significant/critical/important than others e.g. brand/model name HAS to be the same, where as the seller might wrongly have typed in the milage a slight bit differently. Additionally some times information such as the color might even have been left out, an hence I must fall back to less "unique identifying" information such as for an example the engine size. Apart from the direct weight/importance of each attribute there is another dimension of complexity involved - the attributes' importance vary with each other. So let's say e.g. that the car I'm comparing against the rest is very old, then suddenly the importance of the milage it self increases since it's way more likely to be unique among similar cars, than compared to a younger car. This is obviously due to the fact, that the dispersion of milage on older cars are much wider than the one on younger cars.

As you might imagine, modeling this as a lot of nested if-then terms easily ends up in a complete mess, and completely unreadable afterwards, and even hard to model in the first place.

So my questions are:

What might this kind of problem be called in programming, and how do I deal with it? What solutions/algorithms might be good solutions? References, links? Good reading on the topic?

share|improve this question
add comment

2 Answers

Sounds like you're basically looking for an expert system. An expert system is often used for classifying objects, by comparing them against specific criteria. You could set your expert system up to classify cars based on your criteria (mileage, year, color and so on), and then verify whether there are any other cars in your collection with the same characteristics. If not, then you make a new entry for it, otherwise you would either throw an error or simply ignore the new data.

share|improve this answer
add comment

Basically, you're defining a framework for a "heuristic" that will be specified by the customer to power a "search engine".

Try using a numeric "relevance" metric, and weigh various attributes to determine how much a match or miss affects relevance. Some of these, like brand/model, will be static. Others, like milage range based on year, could be dynamic (the older the car is, the further outside the user's defined range the mileage could fall before it's not a good match). Some or all of these could be user-specified as to importance (some quirky user may want a car, any make/model/year/color/price, with exactly 111,111 miles on it, and will not consider a car with a mile more or less; if you want to humor this kind of weirdo, you can allow the user to specify that this specific mileage is of "critical" importance).

You can then plug this data in as conditions of a SQL WHERE clause, using whether the data matches the criteria and the relative importance of each criterion to calculate the "relevance" of the record to the query, and show only cars that meet a minimum relevance threshold (say 75% or better; again this can be user-configurable, so if the user thinks he's not getting enough results he can show more "outliers").

share|improve this answer
    
Thanks! I think you are definitely on to something with your suggestion on a numeric similarity measure. However I think I might not have explained myself good enough. My situation is more that I have database full of "cars" where there are duplicates among rather than the "search engine" scenario. So in my case I know that some of the cars in the database ARE in fact duplicates (even though the information is slightly different), and I want to find those duplicates by comparing them, so I in the last end can get rid of them. –  Niels Kristian Feb 6 '13 at 8:58
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.