3

I am designing a DSL (in clojure, specifically; though this question is more general than that) in which 'entities' are tracked as immutable hashes/maps, and where the 'concept' membership of an entity is dynamically determined by the keys and values of the maps. A toy example of how this would appear:

(defconcept AnnotatedEntity :contains [annotations meta-data])
(defconcept PointCloud      :contains vertices)
(defconcept Polygon         :contains [vertices edges])
(defconcept Triangle
  :isa       Polygon
  :condition (= (count vertices) 3))
(defconcept Rectangle
  :isa       Polygon
  :condition (= (count vertices) 4))
(concepts {:vertices [[0 0], [0 1], [1 0]] :edges [[0 1] [1 2] [2 0]]})

#{PointCloud Polygon Triangle}

(concepts {:vertices [[0 0] [0 1] [1 1] [1 0]]
           :annotations {:name "unit-rectangle point-cloud"}
           :meta-data {}})

#{PointCloud AnnotatedEntity}

Since the :condition of a concept is just a function that gets run on the map, we can ignore this part of the test (and thus any requirements on the values) for now; my interest is in efficiently identifying all of the possible concepts in which a given map might hold membership based on its keys. I.e., let's simplify the above to just this:

(defconcept AnnotatedEntity :contains [annotations meta-data])
(defconcept PointCloud      :contains [vertices])
(defconcept Polygon         :contains [vertices edges])
(defconcept Triangle        :contains [vertices edges])
(defconcept Rectangle       :contains [vertices edges])
(possible-concepts {:vertices [[0 0], [0 1], [1 0]]
                    :edges [[0 1] [1 2] [2 0]]})

#{PointCloud Polygon Triangle Rectangle}

(possible-concepts {:vertices [[0 0] [0 1] [1 1] [1 0]]
                    :annotations {:name "unit-rectangle point-cloud"}
                    :meta-data {}})

#{PointCloud AnnotatedEntity}

Currently, I perform this by brute force, which is plenty efficient for toy examples, but which is not efficient enough for a core piece of a library that will sometimes be called many many times per millisecond with arbitrarily large maps and arbitrarily many concepts.

One simple example of an optimization that improves this process is to keep track of a map of all keys included in any concept such that the values are sets of concepts containing the key; for the above example:

(def concepts-of-keys {:annotations #{AnnotatedEntity}
                       :meta-data   #{AnnotatedEntity}
                       :vertices    #{PointCloud Polygon Triangle Rectangle}
                       :edges       #{Polygon Triangle Rectangle}})
(defn possible-concepts [ent]
  (set (filter #(every? (partial contains? ent) (.getKeys %))
               (apply clojure.set/union (map concepts-of-keys (keys ent))))))

This is quite a bit better than simply testing against every possible concept, but only if concepts have fairly unique keys. If every concept depends on a single key like :meta-data or :id or something very common (or all concepts inherit from a single base concept) then this is basically as inefficient as checking every concept.

Accordingly I don't believe that either of these are the best solution. For example, one might imagine building a decision tree (which would, in practice, be wrapped in a ref or atom and updated as concepts are defined):

(def concept-decision-tree
  "
  Each element of the decision tree is [test-keys if-every if-not-every] where
  test-keys is a key or set of keys that should be tested for membership in a
  given entity; if the entity contains all these keys, descend along the
  if-every element and along the if-not-every otherwise. These values are sets
  if the membership of the entity has been deduced by the most recent
  decision.
  "
  [#{:annotations :meta-data} ;; if the entity has all of these elements...
   ;; descend into this subtree
   [:vertices [:edges #{AnnotatedEntity PointCloud Polygon Triangle Rectangle}
                      #{AnnotatedEntity PointCloud}]
              #{AnnotatedEntity}]
   ;; otherwise, descend into this subtree...
   [:vertices [:edges #{PointCloud Polygon Triangle Rectangle}
                      #{PointCloud}]
              #{}]])
(defn possible-concepts [ent]
  (loop [[test-keys if-every if-not-every] concept-decision-tree]
    (if (every? (partial contains? ent)
                (if (set? test-keys) test-keys [test-keys]))
        (if (set? if-every)     if-every     (recur if-every))
        (if (set? if-not-every) if-not-every (recur if-not-every)))))

This is better yet, assuming we can maintain the decision tree; what I'm wondering is what is the best way to do that, or, alternately, what is an alternative that is equally/more efficient? It is not obvious to me how one would balance such a decision tree as concepts were added.

My intuition is that this problem has a theory that is is widely understood and that I just don't know the formal name for the problem; for that matter I should mention that I'm intellectually interested in the most optimal answer and not in the answer that can be written fastest or that a project manager would most approve of.

In other words, what I'm looking for in an answer:

  • A solution to the decision-tree updating problem, either conceptually with enough details to implement, or a simple example implementation
  • An alternative solution to this problem that is equally/similarly/more efficient
  • A pointer to a the computer science literature on this topic
  • A formal/standard name for this problem
  • Examples of libraries or languages that implement this form of typing dynamically

What I'm not looking for in an answer:

  • a brute-force solution (I already have one!)
  • "<something something> premature optimization is the root of all evil, <something something> so just brute force it."

One other thing I should mention: though I've written these examples using standard maps, I'm not opposed to a solution that involves a special subclass of the persistent map class that tracks its keys and annotates newly created maps with their types as they are created. E.g., a special type that imiates maps but knows that when it encounters (dissoc ent-map :vertices) the new map should have concepts like PointCloud, Polygon, etc. removed from its concept list.

Thanks in advance!

1

You might have a look at a RETE algorithm.

Let's use a working definition of rule as something that pairs a match expression with an action expression, and where success of the former triggers the latter. The match expression is usually a conjunction of subexpressions, i.e. (has attribute x AND has attribute y AND has attribute z), though disjunction can also be supported.

Though I find the description of RETE algorithms somewhat tedious, fundamentally, what they can do is collect a bunch of rules together, determine the common sub-expressions among the match expressions of the entire rule set, and search for any and all rule matches more or less concurrently over all the rules, over some series of input, thus performing the common matching parts only once and raising efficiency.

Essentially, such an engine creates or precomputes internal state regarding the match conditions' subexpressions across all the rules, keeping only one copy of each common match subexpression, while arranging the memory structure such that it knows when a full match for an originally independent rule is satisfied.

The engine looks at information across multiple inputs to see if there is a match for any rule, tracking the state of match of any given rule in the overall combined data structure.

Essentially, it's like the compiler optimization common subexpression elimination though for the matching expressions of rules instead of program source code expressions.

There's also a lot of stuff in RETE for adjusting the search graph if criteria dynamically changes, which can happen in various circumstances, perhaps one of which is if the action triggered for a rule alters the input as might be the case in a reasoning engine where a rule triggers the establishment of new information to be considered as additional input rather than triggering wholly external action.

RETE, or RETE-like concepts might apply toward your situation in the following:

Precompute all the common match subexpressions from all the types you want to recognize, where the match expressions are essentially the set of attributes to match that will result in recognition of a given type of entity.

Feed the loaded engine with attributes, each as one input, from an existing object, and the engine will basically try to match all possible rules more or less concurrently.

It shouldn't matter the order of the attributes you feed the engine, though I can imagine the theoretical potential for some further optimization if they were provides in some sorted order when the match subexpressions are always of a particular shape.

| improve this answer | |
  • Thanks! This was a helpful pointer! Looking around, the clara-rules (clara-rules.org) library seems to be a pretty nice implementation of this (or a close variant, see here:github.com/cerner/clara-rules/wiki/…), and looks pretty easy to adapt it to maps. – nben Jun 6 '17 at 23:34
  • A few other thoughts came to mind, parsing, and regular expressions. What they all have in common is looking at a bunch of rules as a group and precomputing some structure to make a large number of rules more efficient to handle than one at a time, especially when there's overlap between rules. A state machine might also work if the number of states doesn't go out of control; state count might be reduced by sorting input. – Erik Eidt Jun 7 '17 at 15:08

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.