Enhancing Taxonomies by Providing Many Paths

A taxonomy organizes concepts or topics in a hierarchical structure and can be created manually or via automated systems. One major drawback of taxonomies is that they require users to have the same view of the topics as the taxonomy creator. That is, when a user follows a top-down path to find the specific topic of her interest, she has to make choices along the constrained sequence that is present in the hierarchy. As a result, users who do not share that mental taxonomy are likely to have additional difficulties in finding the desired topic. Although this problem can be reduced by remedies like cross-topic links, such approaches break the hierarchical structure and greatly increase human editing cost. Faceted search/browsing has also been proposed to address this problem; however, identifying facets in large scale datasets is a significant challenge.

In this paper, we propose a new approach to taxonomy expansion which is able to provide more flexible views. Based on an existing taxonomy, our algorithm finds possible alternative paths and generates a new, expanded taxonomy with flexibility in user browsing choices. In experiments on the dmoz Open Directory Project, the rebuilt taxonomies show favorable characteristics (more alternative paths and shorter paths to information). User studies show that our expanded taxonomies are preferred compared to the original.

Technical Report LU-CSE-10-005, Dept. of Computer Science and Engineering, Lehigh University, October, 2010.

An abbreviated version of this report was published as X. Qi, D. Yin, Z. Xue and B. D. Davison. Choosing Your Own Adventure: Automatic Taxonomy Generation to Permit Many Paths. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management (CIKM), pages 1853-1856, Toronto, Canada, October 2010.

Back to Brian Davison's publications