Abstract
Faceted search systems often struggle with queries that return either an overwhelming number of categories or too few to be useful. This paper introduces the "Subtree Density Model," a novel approach to dynamically summarize or expand search facets by analyzing the spatial distribution of results within a hierarchical taxonomy. By identifying dense clusters of relevant topics and selecting central "medoid" nodes to represent them, the system provides a more diverse and relevant set of categories. Experimental results on Wikipedia and real-world query sets demonstrate that the model significantly outperforms baseline methods in both precision and diversity.
Introduction
Faceted search is a cornerstone of modern information discovery, allowing users to filter search results by categories such as price, brand, or topic. However, it faces two primary challenges: summarization and expansion. A broad query may trigger hundreds of relevant facets, creating excessive cognitive load (the summarization problem). Conversely, a highly specific query might trigger too few facets, leaving users with limited navigation options if the initial results are not perfectly aligned with their intent (the expansion problem). This research aims to address these issues by optimizing for both relevance and diversity through the analysis of search result distribution within a pre-defined hierarchy.
Methodology
The proposed Subtree Density Model operates in several stages to identify the $k$ best facets to display:
- Mapping: Search results are mapped to nodes in a hierarchical taxonomy (e.g., the DMOZ hierarchy), "activating" nodes that contain relevant documents.
- Subtree Extraction: For each activated node, the model examines its entire subtree of descendants.
- Medoid Selection: Within each subtree, the model identifies a "medoid" — the node with the minimum average distance to all other nodes in that subtree. This medoid serves as a representative "ambassador" for the topic cluster.
- Distance Metric: A hierarchy-aware distance formula is employed, where the weight of parent-child connections decreases exponentially with depth ($2^{-l}$). This ensures that broad, top-level category distinctions are prioritized over niche, low-level subcategory differences.
- Ranking: Medoids are ranked based on a combination of Density (the concentration of relevant documents measured via Discounted Cumulative Gain) and Representativeness (the medoid's centrality within its subtree).
For summarization, the top $k$ medoids are selected. For expansion, the model identifies related ancestor nodes to broaden the search scope.
Experimental Setup
The model was evaluated using the DMOZ "Kids and Teens" subdirectory as the underlying taxonomy. Two query sets were utilized: Q1 (1,200 Wikipedia article titles) and Q2 (1,200 real-world user queries). Initial search results were retrieved via the Bing Search API. Human judgments on relevance and diversity were collected through Crowdflower, with a strict requirement for at least 80% evaluator agreement to ensure data robustness.
Results and Discussion
The Subtree Density Model was benchmarked against baseline (BL) models that selected top-ranked categories or immediate siblings.
- Precision: The proposed model consistently achieved higher precision across the top 9 ranked facets for both summarization and expansion tasks on both query sets. As shown in the performance graphs, the Subtree Density Model maintains a high level of relevance even as more facets are presented.
- Diversity: The model significantly improved diversity. For query set Q1, the top-ranked facet cluster was judged as diverse 79.86% of the time, compared to 63.80% for the baseline. Similar improvements were observed for Q2 (94.84% vs 90.93%).
The "medoid" approach proves advantageous by providing specific, descriptive labels without descending into overly granular "leaf" nodes. Furthermore, the hierarchy-aware distance metric effectively captures the intuitive difference in significance between high-level and low-level category jumps.
Conclusion
The Subtree Density Model offers a robust solution for managing facet density in search interfaces. While the current evaluation relies on a static batch process and a high-quality taxonomy, it demonstrates clear advantages in providing relevant and diverse navigation options. Future work will focus on testing the model in live, interactive environments to observe how real users engage with these dynamically generated facets.
Summary updated