BROAD

Feng Zhao, Xiaolong Zhang, Anthony K. H. Tung, Gang ChenPVLDB 2011 · DOI

TL;DR

This paper introduces BROAD, a system for diversified and hierarchical browsing of keyword search results in databases. It tackles the common problem of overwhelming and redundant results by intelligently partitioning and summarizing them, allowing users to efficiently discover relevant information.

What Problem Does This Paper Address?

Keyword search in databases is a powerful way to query information without needing to know the database schema. However, a major challenge is that these queries often return a massive number of results. While ranking helps, it frequently leads to redundancy, where many top results are very similar, obscuring potentially valuable but structurally different information. This makes it difficult for users to explore and understand the full spectrum of relevant data. The paper aims to solve this by providing a way to present diverse results and allow users to navigate them hierarchically.

Methods

BROAD employs a multi-pronged approach:

  • Kernel-Based Diversity Measure: The core of their diversification strategy is a novel "Answer Tree Kernel." This kernel measures the dissimilarity between answer trees (which represent query results) by considering both their textual content and structural relationships. It's an adaptation of subtree kernels, enhanced to incorporate fuzzy matching of node content and the semantic importance of shared keywords from the original query.
  • Cover Tree Based Diversification: To efficiently find diverse results, BROAD utilizes a Cover Tree index. This data structure, built on the computed answer tree distances, allows for efficient identification of a set of k diverse representative answer trees. The algorithm aims to select these representatives from the highest possible level in the cover tree to maximize diversity.
  • Hierarchical Browsing and Summarization: Once diverse results are identified, BROAD enables hierarchical browsing. Answer trees are grouped based on their similarity to the k diverse representatives. Users can then "drill down" into these groups, recursively applying the diversification process to subsets of results. To aid this exploration, a "circular view" (inspired by the Circos project) is used to summarize the structure and content of answer tree groups, highlighting shared elements and representative keywords.

Datasets

The paper uses the CiteSeerX dataset for demonstrating their keyword search query example ("skyline" and "rank"). No new benchmarks are introduced; rather, they leverage an existing dataset to illustrate their system's functionality.

Key Insights and Ideas

  • Beyond Top-K: The paper highlights that simply returning the "top-k" ranked results is insufficient for complex keyword searches, as it often leads to redundancy and misses diverse perspectives.
  • Structure + Content = Diversity: The Answer Tree Kernel's strength lies in its ability to combine structural similarity with textual relevance, providing a more nuanced measure of diversity than purely structural or content-based methods.
  • Hierarchical Exploration is Key: The concept of allowing users to "drill down" through diversified results is crucial for managing information overload. This iterative refinement process helps users navigate from a broad overview to specific, relevant details.
  • Visual Summarization for Clarity: The circular view is a clever way to condense complex answer tree structures into an easily digestible format, making it feasible to present multiple diverse results simultaneously.

Key Results

The paper is primarily a demonstration of the BROAD system. While specific quantitative results on accuracy or performance improvements are not detailed in this demo paper, the authors showcase the system's ability to:

  • Identify k diverse answer trees from a larger set.
  • Partition these results into k groups based on similarity to representatives.
  • Provide a hierarchical browsing interface that allows users to progressively refine their search.
  • Visually summarize groups of answer trees using a circular layout.

The demonstration with the "skyline" and "rank" query on the CiteSeerX dataset illustrates how the system can present distinct answer tree structures and content, enabling users to explore relationships they might otherwise miss.

Limitations and Future Work

  • Computational Complexity: While the Cover Tree index helps, the kernel computation and diversification process can still be computationally intensive, especially for very large result sets. The paper mentions that the kernel serves as an "effective method to map original answer trees to a kernel space," implying that further optimization might be needed.
  • User Preference Modeling: The current system relies on users to interactively drill down. Future work could explore incorporating more sophisticated user preference modeling to guide the diversification and browsing process.
  • Scalability: While the paper mentions the use of a Cover Tree for efficiency, the scalability to extremely large databases and result sets remains an area for further investigation.
  • Generalizability: The effectiveness of the kernel measure and summarization techniques might vary across different types of databases and query complexities.

The authors suggest that their work is the "first attempt to support interactive hierarchical browsing on keyword search in databases," indicating a promising direction for future research in this area.

Summary updated

Abstract

Keyword search in databases has received a lot of attention in the database community as it is an effective approach for querying a database without knowing its underlying schema. However, keyword search queries often return too many results. One standard solution is to rank results such that the "best" results appear first. Still, this approach can suffer from redundancy problem where many high ranking results are in fact coming from the same part of the database and results in other parts of the database are missed completely. In this demo, we propose the BROAD system which allows users to perform diverse, hierarchical browsing on keyword search results. Our system partitions the answer trees in the keyword search results by selecting k diverse representatives from the trees, separating the answer trees into k groups based on their similarity to the representatives and then recursively applying the partitioning for each group. By constructing summarized result for the answer trees in each of the k groups, we provide a way for users to quickly locate the results that they desire.
BibTeX
@article{zhao2011broad,
  author = {Feng Zhao and Xiaolong Zhang and Anthony K. H. Tung and Gang Chen},
  title = {{BROAD}},
  journal = {Proceedings of the VLDB Endowment},
  year = {2011},
  doi = {10.14778/3402755.3402769},
}
Figure