Abstract
The rapid growth of the Web of Data has created a significant hurdle for researchers and engineers: understanding the contents of large Resource Description Framework (RDF) datasets without the need for exhaustive downloads. We present HIEDS, a generic and efficient approach to hierarchical dataset summarization. Unlike traditional flat partitioning methods, HIEDS constructs a navigable "map" of the data, allowing users to drill down from broad overviews to specific details. By formulating summarization as a combinatorial optimization problem, HIEDS balances data coverage, group cohesion, and processing speed, facilitating interactive exploration of complex datasets.
Introduction
When encountering a new dataset, users are typically provided with basic metadata and an abstract schema. However, schema-based summaries often fail to capture the actual data distribution; for instance, two movie datasets might share a similar "Actor/Director" schema but contain vastly different content. Existing partition-based methods often produce flat, disjoint lists that struggle with multi-faceted entities, such as an individual who is both an actor and a director.
HIEDS addresses these limitations by providing multi-granular abstraction. It organizes large datasets into a hierarchy of overlapping groups based on their properties, preserving structural connections and utilizing human-readable labels for ease of browsing.
The HIEDS Framework
The core of HIEDS is a top-down, iterative subdivision process that repeatedly splits a dataset into subgroups based on five pillars of quality:
- Coverage: Maximizing the representation of the total data.
- Height: Maintaining a shallow hierarchy (typically 2–5 levels) to prevent navigational fatigue.
- Cohesion: Ensuring entities within a group are meaningfully related, measured via information theory.
- Overlap: Allowing entities to belong to multiple categories, reflecting real-world data complexity.
- Homogeneity: Using consistent property types for subgroups to reduce cognitive load.
HIEDS treats the selection of these groups as a Multidimensional Knapsack Problem (MKP), seeking to maximize a "profit" function—a combination of group size and cohesion—while adhering to constraints on subgroup count ($k$) and maximum overlap ($\delta$).
Implementation and Efficiency
To handle millions of triples in real-time, HIEDS avoids iterating over every entity. Instead, it utilizes Lucene-based inverted indexes, treating entities as "documents" and property-value pairs as "terms." This allows for high-performance search queries to calculate group metrics on the fly. For massive datasets, PageRank is employed to prioritize "important" entities, ensuring acceptable latency for interactive use.
Experimental Evaluation
The authors evaluated HIEDS on two datasets: the Semantic Web Dog Food (SWDF) dataset (~200,000 triples) and LinkedMDB (~6 million triples).
The results demonstrate that HIEDS produces groups with significantly higher cohesion than the baseline (LODeX). While the baseline may achieve higher raw coverage, it often results in overly broad, less descriptive groups. In terms of performance, HIEDS generated a full hierarchy for the 6-million-triple LinkedMDB dataset in approximately 163 seconds. Crucially, individual "drill-down" steps took only about 7 seconds, supporting a "compute-as-you-browse" user experience.
Conclusion
HIEDS offers a robust solution for navigating the data deluge by providing structured, hierarchical overviews of RDF datasets. By prioritizing cohesion and allowing for natural category overlap, it creates more intuitive summaries than traditional flat partitioning. Future work includes exploring more complex group characterizations and developing index-free versions that can operate directly against standard SPARQL endpoints.
This paper is based on "HIEDS: A Generic and Efficient Approach to Hierarchical Dataset Summarization" by Gong Cheng et al., presented at IJCAI-16.
Summary updated