HIEDS: A Generic and Efficient Approach to Hierarchical Dataset Summarization

Gong Cheng, Cheng Jin, Yuzhong Qu

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.

Hierarchical summary structure example

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:

  1. Coverage: Maximizing the representation of the total data.
  2. Height: Maintaining a shallow hierarchy (typically 2–5 levels) to prevent navigational fatigue.
  3. Cohesion: Ensuring entities within a group are meaningfully related, measured via information theory.
  4. Overlap: Allowing entities to belong to multiple categories, reflecting real-world data complexity.
  5. 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).

Cohesion vs. Coverage on LinkedMDB

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

Abstract

The rapid growth of open data on the Web promotes the development of data portals that facilitate finding useful datasets. To help users quickly inspect a dataset found in a portal, we propose to summarize its contents and generate a hierarchical grouping of entities connected by relations. Our generic approach, called HIEDS, considers coverage of dataset, height of hierarchy, cohesion within groups, overlap between groups, and homogeneity of groups, and integrates these configurable factors into a combinatorial optimization problem to solve. We present an efficient solution, to serve users with dynamically configured summaries with acceptable latency. We systematically experiment with our approach on real-world RDF datasets.
BibTeX
@inproceedings{cheng2016hieds,
  author = {Gong Cheng and Cheng Jin and Yuzhong Qu},
  title = {{HIEDS: A Generic and Efficient Approach to Hierarchical Dataset Summarization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure