1
$\begingroup$

I need to develop algorithm for one task.

I have 500 types of object, each type is represented by a group of qualifiers (about 20 for each type, the same qualifier can be used for different types), where qualifier is a simple predicate (but calculation of the predicate can take some time, as you have to check data in data base). When all qualifiers for particular type return true then object has such type.

For now I just came up with idea to use cache and go through all types trying to do qualification. For each type firstly I go through predicates without calculation and check that no of them failed before if some failed I skip the type, otherwise I go through qualifiers and do calculations (for each predicate I take data from cache if I did the same qualifier before).

I think may be there are some data structures for such task, or common approaches how to do that better.

A small update to the question. The classification data I have, has special structure, like not all attributes of the object mentioned for each class.

For example Type European transaction:

  • Country one of DE, FR, ES
  • Color : Blue
  • Serial type: 2
  • Currency : EUR

Type UK transaction:

  • Country: UK
  • Serial type: 1

It just example out of my head, each object has much more attributes. The main point here that some attributes can present for some objects but not for others. So if we create data set on the objects to build qualification tree, the value of such attributes could be marked as ANY value, that way it's impossible to do qualification, since we can get to the branch where we have two ways to go.

Thanks.

Improve this question
$\endgroup$
6
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael♦ May 15 '18 at 13:49
  • $\begingroup$ Related (but I don't know whether any of these will meet your needs): cs.stackexchange.com/q/55607/755, cs.stackexchange.com/q/55434/755, stats.stackexchange.com/q/205414/2921. $\endgroup$ – D.W.♦ May 21 '18 at 21:26
  • $\begingroup$ What happens when you ask for the Color of a Type UK transaction? Do you get back "None"? More generally, what happens when you check whether an object matches a predicate, when the type of that object doesn't have the attribute mentioned in the predicate? $\endgroup$ – D.W.♦ May 21 '18 at 21:29
  • $\begingroup$ @D.W. When you ask for Color of a Type UK transaction you actually can get anything, any color at all (green, red, or None). If object doesn't have some attribute, then in terms of Java language that attribute equals to null(None). For case of color checking to be RED we can have something like this: if (obj.color != null) return color == "RED" else return false. To say generally, we get objects, they have many attributes not all of them can be specified. We know that each object can be classified to exactly one type. We know that a lot of required attributes overlap among types. $\endgroup$ – Sergey Luchko May 22 '18 at 19:16
  • $\begingroup$ I don't understand how to reconcile the first two sentences in your comment. The first sentence seems to say that if the attribute is missing, when you query it you might get back anything (including green). The second sentence seems to say that if the attribute is missing, when you query it you will get back null (None). So which is it? I'm confused. I encourage you to edit the question to specify the model clearly. $\endgroup$ – D.W.♦ May 22 '18 at 20:01
1
$\begingroup$

Sure. Caching is a standard optimization that can be applied in many situations. I'm not sure there's much more to say there.

The other optimization that might be useful here is to choose the order in which you test the predicates. I would suggest using ID3 to construct a decision tree that identifies which predicates you test, and in what order. This may reduce the number of predicate computations you need to do, to determine the type of an object.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your reply, I did a small investigation about the approach, and came to the idea that it's not fully applicable for my task. I updated question to clarify that, please look.) $\endgroup$ – Sergey Luchko May 21 '18 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.