A proposal for tag hierarchy on Stack Exchange sites

Question

Executive summary

Introduction of sparse hierarchy (partial inheritance relation) into the set of tags on Stack Exchange sites, in order to allow more efficient question organization/filtering/tagging (especially via "Interesting"/"Ignored" mechanism).

The proposal is designed to achieve its goals while adhering to two principles:

• As much backwards compatible as possible - e.g., all work-flows/GUIs not related to tags should remain 100% identical; and any work-flows related to tags should remain very similar (with exception of new tag creation for lower-rep users).

• As far as data population, this is intended to be a gradual incremental process - e.g. instead of one-time massive hierarchical classification, it is intended as an incremental addition/improvement of relationships.

Why bother? (aka use cases)

• As a use case #1, take a fictitious user "Larry Ceiling" . He is a Perl expert, and would like to ensure that every Perl question has good, complete and accurate answer. To do so, he will need to either use "Interesting Tags" mechanism, or to employ a search by tags.

  Currently, "Larry Ceiling" needs to use between 15 frequent Perl-related tags to ensure "good enough" coverage and at least 40 all perl-related tags to ensure full Perl coverage.

  Searching for "perl*" isn't good enough (because many Perl-related tags do not contain the word "Perl" - for example autovivification or moose or dancer).

  In addition, due to new tag additions, this list needs to be maintained by virtue of monitoring for new Perl-related tags.

  What Larry wishes is a way to simply say that he's interested in perl tag, and achieve the correct result.

• A mirror use case is user named "Jon Biathlon", who would like to never see another C#, or .net question for whatever reason. I estimate the amount of C#/.net tags far exceeds Perl ones, and "Jon" will need to add every single one of them to "Ignored Tags" list or exclude from searches.

• More use cases are in the examples in Benefits section.

Solution

Add an ability for a many-to-many transitive relation "contained in" (aka "sub-tag") between some tags.

Just to be clear - the relationship will be sparse. NOT every tag will need to have a parent.

• This relation would only be applied to completely contained tags. For example, stl tag would be contained in c++ tag; but oop and c++ tags would be completely independent. garbage-collection would be independent of java.

• The relation could be many-to-many, for example visual-c++ tag would be contained in both c++, and, if such exists, visual-ms-languages tag. However, I don't envision too many cases where multiple ancestors would exist - see next bullet point for the reason.

• Some composite tags should be split up. For example, all of perlre, boost-regex and apache-regex need to be changed to regex + specialized tag (Perl, boost or apache correspondingly). This is the reason I believe multiple ancestors would be rare.

• Tag relationships can be specified by either a creation of a new tag, or via a special "relate tags" management screen.

• When tagging a question; the GUI allows "searching" for tags by sub-string via auto-complete drop-down (as we do now), or by browsing a tag hierarchy, e.g. typing "C++>" will bring up a drop-down of all children of [C++] tag.

• NOTE To increase backwards compatibility, we may want to only enable the "include descendant tags in searches" if the special form of the tag is used in Include/Exclude/Search (e.g. [perl] vs. [perl*]. Personally I don't think this is needed but may address the concerns by people that automated inclusion/exclusion of more questions may be disconcerting).

Proposed permissions

To shorten the post, I removed a detailed proposal for permissions required for creation of tags AND tag hierarchies - see edit history if you're genuinely interested. </Fermat>

Implementation - technical

Add 2 new tables (I don't know exact table structure of SE, so details may be off):

Table 1: *tag_contained* (parent-child relationship)
| parent_tag | tag | approved (could be >1 column) |

This table contains the relationship definitions. It is populated either when a new tag is created to be a child of an existing tag, or when a user with sufficiently high rep (say 250, or 3000 for "TOP" parent) proposes a new relationship, with "approved" value of false.

In addition it would contain newly proposed "top level" tags, with a special "TOP" parent tag value - but once approved, such records can probably be removed from the table.

When a user who can approve (10k? moderator?) approves it, "approved" is updated to true value.

This table is also used by the "tag population" GUI, by listing N-level drop-down menu instead of current 1-level auto-complete drop-down (better GUI approaches are welcome!)

Table 2: *tag_contained_expand*
| ancestor_tag | tag |

This table contains ALL transitively computed relationships. E.g. if the first table contains A->B, B->C, C->D, this table will contain A->B, A-C, A->D, B->C, B->D, C->D. This table is populated automatically based on all approved rows in the first table, either by a regular job or by a trigger. Since I do not anticipate an unduly high amount of tag relationships, this should not be overly intensive process.

The second table is actually used by search engine, include and ignore mechanisms - namely, a query of a type "where tag in (X,Y,Z)" will be expanded to join with tag_contained_expand.

It will also be used when tagging a question, by eliminating un-needed ancestor tags. E.g. a question with perl5.10 tag would not need perl tag due to "contained in" relationship between them, and thus the latter will be either automatically removed or suggested to be removed (I suggest automated + notification).

• NOTE One additional technical detail - for Google's permission, the ancestor tags of question need to be included (hidden or visible?) on the question.

Benefits

• Main benefit is, of course, much simplified searching and filtering as illustrated in use cases.

• Some of the 35000 tags (especially composite ones) could be removed, as their only reason for existence is to denote hierarchy. Examples. perlre, boost-regex, vc++-project-file.

• Overly-specialized rarely used tags - visual-studio-2008-sp1 - which are the main candidates for being something's child - no longer pose a problem for either searches/filtering, OR for finding them when tagging a question.

• Misspelled and differently-spelled tags pose less of a problem as well. Much easier to find assorted .net and dotnet related tags if they are all under a single [.net] hierarchy. I realize that tag-synonyms may solve this particular problem, but it's still a problem meanwhile.

• A problem of finding tags that are related to some topic but have nothing at all common as far as wording is removed. autovivification is a lot easier to find in a list of perl's children than on its own, especially for people who don't necessarily remember that word.

Potential issues and resolutions

• Issue: Tags that apply to multiple domains creating logistical nightmare. For example, C++/memory-allocations, Java/memory-allocation, etc...

  Solution: memory-allocations should be independent of either of those 2. The examples above should be 2 independent tags each.

• Issue: It is very hard to organize 35000 tags into a tree, never mind do it correctly.

  Solution: The 3 components of "hard" assessment are sheer volume, the fact that most tags are really independent of each other, and the difficulty in placing certain tags under just one parent.

  First of all, a vast majority of the tags will not be in a single tree. There will be many top level tags and the forest would for most part be rather flat and sparse.

  Second, this is meant to be a gradual incremental process. 10 tags related first day. 5 tags second day. All Perl tags within 2 weeks (I'll volunteer :). etc...

  Third, while rare, multiple parents are allowed, thus eliminating "but it belongs to both!" headaches. Although, as noted, most cases when it appears that the tag belongs to multiple parents, either it should be independent in the first place, or it is a composite tag which should be split into two.

• Issue: This proposal is too bloody long

  Solution: I should get more sleep.

Uniqueness

NOTE: this question is NOT a duplicate of this one, since it contains detailed proposal instead of a general idea. Some of the ideas are based on results of this discussion.

Answer 1

Sorry, but this sounds like a nightmare to use.

You basically hand-wave most of the issue away by saying that memory-management should be a top-level tag. Okay, great, let's use that as an example.

• Should memory-management be a subset of memory?
• Should memory-leaks be a subset of memory-management (keeping in mind that memory leaks are still possible in garbage-collected environments)? Should it be a subset of memory?
• What about memory-usage? outofmemoryexception?
• What about memory-allocation?
• What about malloc, which is specific to C/C++? Does it go under memory-allocation, which is a general tag, or one of the C tags?

You say you don't predict many multiple-ancestor issues; I submit that the vast majority of tags fall under this umbrella. Even seemingly-innocuous tags like c# could technically go under both .net and mono. apache can go under linux and windows.

Not only is the maintenance a nightmare, but managing the search results are completely non-intuitive. If I search for wcf, I don't need a bunch of questions tagged with wcf-data-services popping up. Some 10k user might rightly decide that it's a subset of wcf, but I never use it so it has very little relevance to me (and wcf-data-services questions are, thankfully, rarely tagged with wcf).

It's going to be an endless source of confusion and arguments.

It never ends.

You know what's a lot simpler? Tagging a perl question with perl. We get 5 tags per question, it shouldn't be that hard. If users can't be bothered to tag their questions correctly, then I don't think Larry should really be worrying about them.

Hyper-specialized tags like visual-studio-settings (2 questions!) should just be merged into their "parent" tags.

---

Fine, since "memory" is an abstract concept and you seem content to just fire off answers to those as though everybody in the world would agree, here's another, more targeted example. Take the following tags:

c# vb.net .net linq linq-to-sql entity-framework nhibernate linq-to-xml linq-to-objects linqdatasource linqpad

Let's seriously start thinking about how to organize these.

Linq is definitely part of .NET. It's technically part of C# and VB.NET as well, and is different for both of them.

Linq to SQL could be thought of as a subset of Linq. But its scope goes far beyond Linq, it's an entire ORM framework. If linq-to-sql goes under linq, so should entity-framework. Does that make sense?

linq-to-nhibernate is definitely about nhibernate. But it is also about linq. If I search for questions on nhibernate, I probably do want to see questions on linq-to-nhibernate. But if I search for general questions on linq, I almost certainly don't want to see the linq-to-nhibernate or linq-to-sql questions.

linqdatasource is technically a subset of linq, linq-to-sql, and asp.net (being a web server control). But what is the actual likelihood that I want to see questions on linqdatasource if I search for either linq or asp.net? Almost nil in both cases.

And what about linq-to-xml and linq-to-objects? Surely you aren't going to tell me that linq-to-xml should go under xml or that linq-to-objects should go under objects. Are you? Well, it's hard to say; if I happen to be looking for questions about XML, Linq to XML is the de facto way of working with it in .NET now. So I don't want to search for all questions about .NET, just questions about .net and xml, which is a fairly logical search parameter. Except, if I'm not looking for .NET XML questions specifically, it makes no sense whatsoever to show me Linq to XML questions.

And linqpad. Well, it's definitely linq related. It's all about Linq. But rest assured that I don't want to see questions about linqpad when I search for linq. It is a genuine "containment" relationship, but nevertheless a completely useless one, I'm usually not interested in giving tech support on a program based around Linq to SQL/EF.

I repeat: There is no end to the pain and anguish that a tag hierarchy would cause.

I will take this conclusion one step further: The lack of a hierarchy is the raison d'être of a tag system. Adding hierarchy semantics to a flat tagging system is creating the very problem that the tagging system was supposed to solve/circumvent; all in order to solve what is basically a non-problem (is it really that hard to find questions about Perl or .NET, and does it matter if your favorite/ignored tags occasionally pick up one or two false positives?)

Answer 2

Hierarchies are problematical. Heterarchies are less so.

What could work is a set of clustering tags -- eg:

[perl/] could mean [perl] and [perlmonks] and [mess-up-like-perl] and other tags.

[status/] could mean [status-complete], [status-norepro], [status-declined] etc

• A base tag can be in zero or more clustering tags.

• Members with over [5000?] rep points can edit/create the clusters.

• No question can be tagged with a clustering tag, only with base tags
  as now.

• No one needs to use clustering tags as all the base tags still work the same.

• Those who want unusual clusters (eg [1990s-technology]) can argue amongst themselves until they have a clear definition of what base tags that may include.

• Later, more nuanced searches could be built by allowing ANDing (etc) of
  base tags and clustering tags, eg:
  [perl/] and not [golf]

Answer 3

You definitely need a multi-parent hierarchy.

The what-should-be-a-child-of-what discussion is not really one for here. The bottom line is that it is possible to come up with a hierarchy. Given that this is a user-managed environment, the hierarchy should eventually stabilize at the most intuitive structure. If it's not clear where a tag belongs, just keep it on the top level; we're after a hierarchy, not the perfect one.

The hierarchy already exists, we just want to formalize it. Consider that some people will just tag something with sql-server-2008, while others will tag it sql-server and sql as well. A lot of discussion can go into which one is better, but the proposed hierarchy would cause the two to be combined.

There are consistently new tags popping up, and people need to favourite and ignore appropriately, having a proper hierarchy would reduce the need to do this.

Search engines consideration - It may be disadvantageous to tag something only with a tag at the lowest level, possibly losing a keyword indicating the language used which would decrease the rank of the results. Worth a thought.

Some thoughts on dealing with the problem of people getting results for things they don't want to get results for:

• You can have strong-inheritance (sql-server-2008 child of sql-server) and weak-inheritance (linq-to-sql child of linq). strong-inheritance automatically includes the child, weak-inheritance optionally includes the child. This default allows your new users to hit the ground running without knowing about inheritance, and they'll figure out that when they search for sql-server, sql-server-2008 also pops up. The inheritance structure explaining why a specific tag was included should probably also be displayed somewhere, with a link to an inheritance FAQ.

• Degree of inheritance. An extension of the above, allowing more than 2 choices when specifying how strong the inheritance is. This would probably allow for a better hierarchy, but this is a lot more complicated for everyone.

• You can specify whether you want to include children (strong/weak inheritance or both) when specifying a tag (as a favourite, ignored or in search), possibly using some affix.

• Ignoring linq and favouriting sql (both with weak inheritance) probably should cause linq-to-sql to be ignored, similar to the way it's working now with multi-tagging.

• Posting questions under certain tags (or tags high in the inheritance tree) should be demotivated (possibly with a warning when trying to use it) or disallowed. sql comes to mind, how many questions are there that fits under sql that wouldn't be better suited to be tagged under one of it's children? (I'm not saying there aren't any, just that there are few)

• Tagging something with a tag and it's parent should probably be disallowed (at least in the case of strong-inheritance, demotivated in the case of weak-inheritance).

Answer 4

I totally support hierarchies in the underlying implementation.

I see very little need for hierarchies in the basic user interface itself (except for moderators and people explicitly using the tag hierarchy).

In the SQL space, right now this is increasingly obvious. If I want to see all SQL questions, this should include t-sql and pl/sql dialects etc. If I want to see all sql-server questions, this should include sql-server-2000, sql-server-2005, sql-server-2008. This is especially important because of the 5 tag limit. You cannot expect people to tag correctly at the moment since there is still no way to stop people repeatedly using the incorrect tags.

What we did for our technical support knowledge base was allow things to be tagged, but that tags could be multi-parented. So if people were looking at a problem related to an HP 970 printer driver and margins, it would show up under printing, drivers, hp, hp-970, margins, etc. And they didn't have to worry about the fact that there were multiple mount points for a tag or anything like that. They didn't have to tag all the way up and the search would automatically find everything under whatever rollups because we cached the full traversal.

For improved performance, we cached the tree traversal up so that the data entry and management was normalized but the denormalized cached data could be used to ensure performance.

Answer 5

I think many-to-many hierarchies are too complicated to manage, and very complex tree-like hierarchies also may be problematic, but there are some cases where hierarchy is the only logical way.

As example, I had issues with LocalStorage and cache-manifest, both of them being part of HTML5 specification. I've tagged my post also html5, since this tag is more popular and tagging it so increases the chance of being answered, and also javascript, since problem is with AJAX application. There are even more tags that could be appropriate, such as offline, offline-cache.

Of course unnecessary tags are one case (offline-cache is, I think, often mistaken with cache-manifest). But another case is this HTML5, which contains of mechanisms such as Local Storage and cache-manifest, so it is logical that these both should be subtags of the tag html5.

The same, I think, should apply to the various jquery extensions, which have separate tags, but practically whoever asks such question will also use basic jquery tag.

So in my opinion it should be at least simple one-level hierarchy. Two levels would be even better, but the greater the hierarchy, the more important to manage this tags correctly. Very high reputation should be required to edit tag hierarchy.

Answer 6

Far too much complexity for the problems you propose to solve.

I went cross-eyed trying to read the whole post, but I was simply not convinced by the "problems" you posit with the current system: those may call for a better means of telling the system what we are and are not interested in. They don't call for a complete rewrite of the post sorting mechanism.

Remember that we're going to have to explain all this to the users who

• want to search
• want to set their interested and ignored subjects
• obtain the ability to create tags

and that if they don't get it they're going to be here on meta asking about it. Over and over again.

There may be issues surrounding tag approval. Stack Overflow currently has more than 500 10k+ users. Can any one approve a new tag? What if other high rep users disagree? Are we going to end up with a voting system?

Answer 7

Searching for "perl*" isn't good enough (because many Perl-related tags do not contain the word "Perl" - for example autovivification or moose or dancer).

Could this be solved by an effort to add tag synonyms for the above, such as perl-moose and perl-dancer? It looks like tag synonyms are supported by wildcard searches for the most part.