Method for enhancing search and browsing in collaborative tagging systems through learned tag hierarchies

A method for improving search and retrieval of resources in a collaborative tagging system, the method comprising:

• identifying, using a computing system in communication with a plurality of computer accessible resources, relationships among a plurality of tags in the collaborative tagging system, the plurality of tags associated by a plurality of users with the plurality of resources, and the relationships among the plurality of tags comprising sub-tag relationships between given pairs of tags based on co-occurrence of those pairs of tags at a given resource and associative semantics, the associative semantics comprising common association between tags in each given pair of tags by the plurality of users;
• using the identified tag relationships based on tag co-occurrence statistics to create a hierarchy of tags, the hierarchy comprising a directed acyclic graph where nodes in the directed acyclic graph comprise tags and edges in the directed acyclic graph comprise the identified tag relationships;
• and
• using the created hierarchy to infer additional tags for resources automatically, to increase a number of tags associated with each resource in order to increase a total number of resources uncovered by a tag-based search of the plurality of resources and to maximize the recall of a tag cloud comprising a plurality of tags by constructing the tag cloud as a set cover-based tag cloud by iteratively selecting an existing tag comprising a largest resource coverage and removing that existing tag and the covered resources from consideration until a total number of selected tags equals a fixed maximum size of the tag cloud.

A method for improving search and retrieval of resources in a collaborative tagging system, the method comprising:

• identifying using a computing system in communication with a plurality of computer accessible resources relationships between pairs of tags selected from a plurality of tags in the collaborative tagging system using sub-tag relationships between the pairs of tags based on co-occurrence of those pairs of tags at a given resource and associative semantics, the associated semantics comprising common association between tags in each given pair of tags by the plurality of users, by calculating a conditional probability for each pair of tags that if a first tag in a given pair of tags has been used to tag a given resource a second tag in the given pair of tags has also been used to tag that resource by determining a ratio, for each pair of tags, of a number of resources tagged by both first and second tags in a given pair to a number of resources tagged by the second tag in the given pair, the plurality of tags associated by a plurality of users with the plurality of resources;
• using the identified tag relationships based on tag co-occurrence statistics to create a hierarchy of tags comprising a directed acyclic graph having a plurality of nodes, each node comprising one of the plurality of tags, and a plurality of edges, each edge comprising one of the identified tag relationships;
• and
• using the created hierarchy to infer additional tags for resources automatically and to increase a number of tags associated with each resource in order to increase a total number of resources uncovered by a tag-based search of the plurality of resources.