TL;DR
This paper introduces a dynamic faceted search system designed for "discovery-driven analysis" on mixed structured and unstructured data. It tackles the challenge of guiding users through large, complex datasets by automatically identifying and presenting the most "interesting" facets and their aggregated values, moving beyond static, count-based facet selection.
What Problem Does This Paper Address?
Modern data is increasingly a blend of structured attributes (like dates, categories, authors) and unstructured text (like descriptions, reports). Analyzing this data for insights, especially when users don't know exactly what they're looking for (discovery-driven analysis), is difficult. Traditional faceted search systems, common in e-commerce, present static facets based on simple counts, which can be uninformative for deeper analysis. They often fail to highlight less obvious but potentially more interesting patterns or correlations between facets. This paper aims to bridge this gap by creating a system that dynamically surfaces "surprising" or "unexpected" facets and their aggregations, guiding users towards valuable insights.
Methods
The core of the proposed system lies in its novel approach to defining and measuring "interestingness."
- Dynamic Facet Selection: Instead of relying on static, pre-defined facets or simple counts, the system dynamically selects a small set of facets and their values that are most "interesting" to the user based on their query.
- "Navigational" Expectation: A key contribution is a new way to define user expectations. This "navigational" method adapts the expectation based on how the user has previously interacted with the data (e.g., drilling down into specific facets). This allows the system to identify patterns that are surprising relative to the user's evolving understanding, rather than just absolute counts.
- P-value Based Interestingness Measure: The paper proposes a novel measure of "interestingness" using p-values derived from a hypergeometric distribution. This metric quantifies how surprising an observed facet count is under a random sampling scenario, providing a normalized and intuitive way to compare interestingness across facets with different domain sizes.
- Efficient Implementation: To handle the computational demands, the system builds upon the Solr search engine. It introduces two key optimizations:
- Compressed Bitmaps (WAH Code): Posting lists in the inverted index are compressed using Word-Aligned Hybrid (WAH) code, improving space utilization and speeding up bitset intersections.
- Bitset Trees: A novel directory structure called a "bitset tree" is used to organize bitsets of facet values. This structure prunes unnecessary bitset intersections, significantly reducing the overhead of computing facet summaries, especially for facets with large domains or when analyzing facet combinations.
Datasets
The system was evaluated on two real-world datasets:
- DBLP: A dataset of academic publications (13K documents, 14 facets). This dataset was used for the user survey.
- Patent: A collection of U.S. patents (up to 1.79 million documents, up to 815 facets). This dataset was used for performance evaluation.
The paper does not introduce new benchmark datasets but uses existing ones to demonstrate the effectiveness of their approach.
Key Insights and Ideas
- Subjectivity of "Interestingness": The paper highlights that what's "interesting" is subjective and context-dependent. A simple count-based approach is often insufficient.
- Navigational Context is Crucial: Allowing the system to learn from user navigation (e.g., drill-downs) provides a more powerful way to set expectations and uncover truly surprising insights.
- P-values as a Universal Interestingness Metric: Using p-values offers a statistically grounded and comparable measure of surprise across diverse facets, overcoming the challenges of domain size differences.
- Facet Combinations Reveal Deeper Insights: The ability to present facets in pairs (or more) is critical for discovering correlations, a capability often missing in traditional faceted search.
- Performance Bottlenecks in Faceted Search: The paper identifies facet summary computation as a significant bottleneck in existing systems and proposes concrete optimizations to address it.
Key Results
- User Survey: A user survey indicated that the proposed dynamic faceted search system, particularly with the "navigational" expectation, was overwhelmingly preferred over heuristic, count-based methods. Approximately 60% of user comparisons favored the dynamic approach. Users found the system effective in uncovering interesting patterns and correlations, especially when facets were presented in pairs.
- Performance Improvements: The optimized implementation (using WAH compression and bitset trees) achieved significant speedups. Compared to a baseline Solr implementation, the "compressed-tree" version performed 2 to 3 times faster on large datasets. The system was shown to be interactive for queries matching up to 5000 documents.
Limitations and Future Work
- User Interaction: The current system has limitations in handling user feedback for facet selection. Users found certain facets consistently uninteresting or always interesting, regardless of the query. The authors plan to improve facet selection by incorporating user feedback, allowing users to prune uninteresting facets or "pin" interesting ones.
- Aggregate Functions: The current system primarily focuses on count aggregations. Future work includes extending the system to support other aggregate functions like sum or average on numerical measures.
- Distributed Systems: For even larger datasets, the authors aim to explore how to support dynamic faceted search in a distributed environment.
- Ad Hoc Expectation: While the "Ad Hoc" expectation method was well-received by users, it was not fully implemented in the presented system.
- WAH Compression Performance: While WAH compression improves space efficiency, its performance benefits were less pronounced on smaller datasets where bitsets were not very dense. The authors suggest investigating byte-aligned encoding for future work.
Summary updated