I am scanning Wikipedia's DB and retrieving topics (page names, mostly) and their relationships. I want to use it later to create a visual map.

A topic table stores the id and the label of each topic. A relationship table has an id, a weight, and the two ids of both topics it references. There are usually two rows in the relationship table for each topic pair (dog is more related to the wolf than the wolf is to the dog, for example.)

Now, each topic has a series of several (sometimes dozens) of other close topics (synonyms with a high weight, related terms with a lower but still high weight, etc.)

For example, Caffeine is a topic, and Theanine would be very closely related to it. Same for Coffee beans.

So Caffeine is a common parent but Theanine and Coffee beans aren't aware of their relatedness. The relatedness means that the both topics have a common ancestor (parent topic).

How can I store these various topics and their relations in order to accurately and efficiently (within 1s) get n-topics and compute their relatedness?

My thoughts are:
- Store additional pairs of rows in the relationship table for each cousin and brother topics? - Or, use the application code (Python, PHP, whatever) to deduce that relatedness by climbing the tree?

  • $\begingroup$ @Evil edited :) $\endgroup$ – Lazhar Jan 2 '17 at 1:37
  • 1
    $\begingroup$ Welcome to CS.SE! What do you mean by "get n-topics"? How do you want to define "relatedness"? How is that defined? It's not clear what you're trying to achieve, so it's going to be hard to suggest how to achieve it. Can you edit the question to clarify? Also, by the way, as a minor point, I suggest you avoid using backticks for emphasis; you might try using italics instead. Backticks are best reserved for code. $\endgroup$ – D.W. Jan 2 '17 at 3:06
  • $\begingroup$ I think that your question is about a data structure or idea to store parent topics, clustering or propagating the relations which are hierarchical but not stored explicitly with a topic. Is something like Union-Find similar to what you need? Have you considered augmenting every topic with parent topic? Or even all of them if there are more? It will improve access time and of course increase the memory usage, but it was not mentioned as the objective. It seems that the parent topic is fixed (coffee has parent caffeine, but it will never change), so it will be redundant information. $\endgroup$ – Evil Jan 2 '17 at 19:00
  • $\begingroup$ If you do not have any hidden questions (not visible in the question), your first idea is good (for efficiency) but will introduce redundancy. Also adding additional table of parent topics with all offsprings enumerated is good for efficiency (creating map will propably require that at some point) but creates a bit bad DB design (relations will not change, so this is not catastrophic). If you already use own DB try to avoid own traversal or non-atomic values. Currently there is nothing more to add. If this does not exhaust your question poease make an edit. $\endgroup$ – Evil Jan 2 '17 at 19:10

Your Answer

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

Browse other questions tagged or ask your own question.