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 am really struggling with a problem where I need to "prune" down available scenarios to those that a user has defined as valid. Below is a small example of the problem I am trying to solve in .Net (C#). Given the levels / values shown below, the user could pick that there are only a few valid combinations, but if you imagine the levels below being 30-40 levels of data instead of the 5 I have shown, you could see my dilemma. I could need to go through millions to billions of NOT VALID combinations to get to the Valid combinations. There will be cases where all values in the level are applicable and some where only those combinations that the user has specified are.

Current Levels / Values of data:

enter image description here

Users have said that the valid combinations are:

*Notice all from level 4 are valid
Receiver -> Sony -> 500 -999 -> Retail
Receiver -> Sony -> 1000 - Up -> Retail  

Results expected from the given 5 levels of information:

Receiver -> Sony -> 500-999 -> Open -Box -> Retail
Receiver -> Sony -> 500-999 -> New -> Retail
Receiver -> Sony -> 1000-Up -> Open -Box -> Retail
Receiver -> Sony -> 1000-Up -> New -> Retail

The things I have tried are performant with small sets, but if I was to have a lot of levels and big gaps in the combinations which wouldn't allow me to prune the valid combinations until I was deep into the levels, I am running into major performance problems. I am obviously not tackling the problem incorrectly.

Any other views or suggestions on tackling the problem would be greatly appreciated.

share|improve this question

2 Answers 2

What you're doing is called faceted search. There is a lot of research in that area about how to do it efficiently, but I would recommend starting with an existing solution like Apache Solr.

share|improve this answer
    
The conciseness here is good, but a little bit of description from the "Faceted Search" link that describes it to show that what he refers to above is "Faceted Search", it would improve the quality of this answer. +1 all the same; looks correct (I don't know anything about faceted Search) and good advice. Is lucene.net an equivalent or separate project from Solr? He tagged it C# so if Lucene.NET is the .NET version of Solr, he might want that. –  Jimmy Hoffa Aug 9 '13 at 18:06

I assume you have some sort of algorithmic way of determining what valid combinations are (otherwise, you'll have edge cases galore)?

Assuming that's the case, this sounds like a job for a tree. The root node is some arbitrary, empty node that represents the store. Child nodes of the root are each item in your first column. Child nodes of those will be valid nodes from column 2, etc.

I would expect that the tree values would be indexed into the actual db rows (ie. each node in the tree merely contains the primary key of the db element it represents).

That describes something in-memory, but because you mention that there is a size constraint, you will likely have to encode this structure in the DB. A join table that represents the parent/child relationship between items should be sufficient (though, if your "levels" are split across multiple tables, then this would become more difficult).

share|improve this answer

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.