Is there a formalism for this data structure?

Question

I'm looking for a mathematical formalism for a data structure I'm working with, so that I can track down relevant theorems and algorithms.

Suppose you have the following:

• A directed acyclic graph of topics.
• At each topic, there are one or more relations between the topic, items in a set of documents and items in a set of groups.
• The groups may be a simple set or they may end up as a DAG. They are used to manage the visibility of the association of a document with a topic.

Only recently have I come across hypergraphs, which seem relevant but too general. Is there a formalism for this data structure? If not, can it be described more succinctly in mathematical terms?

Psilomelane

I don't really understand what you mean. What do the edges in the DAG of topic mean? What does that have to do with document or items, sets and groups (of what?)? I think the best way to explain that would be some example. Also, why are you looking for theorems? What kind of problems are you having? – Neurovascular

@svick, I'm using an edge from one topic to another to model "is a subtopic". So "physics" is a subtopic of "science", and there's an arrow from "science" to "physics". But this detail shouldn't matter for the purpose of the question. – Psilomelane

I'd like to do set intersections over the documents associated with the ideals and filters of given topics in the DAG, filtered by a specific set of groups. The reason I need theorems and algorithms is because working with a DAG gives rise to some tricky space and memory constraints, and working with more than a DAG makes the constraints even more subtle. – Psilomelane

Is there any connection between the documents or groups pertaining to a topic, and that topic's ancestors/descendents in the topic DAG? You should try to give a full example like you were doing with Physics and Science, but with documents and groups in there too. For instance, if "Principia Mathematica" is a Physics document, then it's also a Science document. – Ruzich

@Edmund, I think your example is a good one. So it might be something like Science (T) <- Physics (T) <- "Principia Mathematica" (D, public) and Science <- Physics <- "Some Proprietary Invention" (D, internal). – Psilomelane

So "public" and "internal" are groups? Is each item assigned to a fixed set of groups, or does the assignment of groups depend on the item AND the topic? – Ruzich

That's right -- "public" and "internal" are groups. For the present purpose, the relation would be a tuple: (Physics, Principia Mathematica, public), (Physics, Principia Mathematic, internal), (Physics, Some Proprietary Invention, internal). There's more sophisticated ways to model the relationships, but I think this captures the main idea. – Psilomelane

You should google "Pachinko Allocation". – Griffey

Answer 1

This looks like http://en.wikipedia.org/wiki/Formal_concept_analysis , especially Galois lattice.

A lattice has more constraints than what you describe, but maybe you can adopt this formalism in your application, or start from here to see if there are related works closer to your needs.

I guess you already know http://en.wikipedia.org/wiki/Ontology_%28information_science%29 , which is also the starting point of a lot of resources.

Deborahdeborath