2

I am currently planning an upcoming project and am looking for an algorithm for searching a database.

The search is as follows; There will be some specifically labelled criteria (or fields) and I would like to find any objects in which its fields match the specified criteria. As well as this it needs to rank partial results based on the number matches for each field.

Heres an example -

Person 1
Name: John
Occupation: Developer
Favourite Colour: Blue

Person 2
Name: John
Occupation: Manager
Favourite Colour: Blue

Person 3
Name: John
Occupation: Developer
Favourite Colour: Green

Person 4
Name: Larry
Occupation: Mailman
Favourite Colour: Red

Search Criteria
Name: John
Occupation: Developer
Favourite Colour: Blue

Results

Rank 1
Person 1

Rank 2
Person 2
Person 3

The ranks would not be visible but would handle the order of the result list.

I could do this quite easily for a small data set, for example, JavaScript;

results = [];
for(var i = 0; i < objects.length; i++) {
  var result = _.intersection(criteria, object[i]);
  if(result.length > 0) {
    object[i].rank = result.length;
    results.push(object[i])
  }
}
return results (and order by rank)

Obviously this won't work when querying a db but I am hoping someone much smarter than me can point me in the right direction. I feel like there must be a solution to this out there and it's probably simple but my Google-fu is failing me.

Improve this question

1 Answer 1

Reset to default
3

Well, do you or don't you have the data in a normal database? If you do, there is no way around querying all possible matches from the data base (with a long query full of OR operators) and then sorting the result however you see fit. In other words, you're not looking for a search algorithm, but for sorting functions.

You can only solve this problem with special algorithms if you are willing to adapt the format in which you store data to your requirements. For instances data warehouses are frequently denormalized so that you can query individual sales, but also aggregate sales, and even find months with total sales in a particular range.

It's possible to do something similar for your problem by precomputing scores that express how well a record matches a query and then querying that index for good scores rather than all records for their individual fields. However, that only works well when you have particular queries that you will pose again and again, because each query defines its own particular match score. Your example looks as if you can generate many different, in fact arbitrary queries. That will probably require more effort in indexing than you save in retrieving.

Improve this answer
1
  • Well since it is very much conceptual at this point, I have full control over the data. I see what you are saying with the pre-computation but I feel calculating such a thing for so many permutation on each object would be extremely difficult. When you say all possible matches, is there a good way to specify what constitutes a match? The only thing that springs to mind is to get all results from the db and for each through them checking each criteria against its associated field. I worry that this would be very slow for even a medium sized data set Commented Jul 16, 2015 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.