Size-l Object Summaries for Relational Keyword Search

Georgios John Fakas, Zhi Cai, Nikos Mamoulis

Searching a database shouldn't feel like drinking from a firehose. While web search engines like Google have mastered the art of the "snippet"—that concise preview that tells you exactly what a page is about—relational keyword search (R-KwS) has traditionally struggled with this.

In their paper, "Size-l Object Summaries for Relational Keyword Search," Georgios Fakas and his colleagues tackle the problem of "Object Summaries" (OS) that are simply too big to be useful. They propose a framework for generating concise, meaningful snapshots of data entities directly from relational databases.

Traditional relational keyword search returns "Object Summaries"—trees of related data rows (tuples) centered around a keyword. For example, searching for a famous researcher in a bibliographic database might return an OS containing every paper they’ve ever written, every co-author, and every conference they’ve attended.

An example Object Summary (OS) for researcher Christos Faloutsos, showing related papers, co-authors, and conferences.

For a prolific subject, this OS can contain thousands of tuples, making it "user-unfriendly." Users typically want a synoptic view—a highlight reel—before diving into the full details. The challenge is: how do you automatically select exactly $l$ tuples that are both highly important and semantically meaningful as a standalone summary?

Defining a "Good" Summary

The authors define a "good" summary as a connected subtree of size $l$ that maximizes a "Local Importance" score. This score is calculated as a product of two primary factors:

  1. Global Importance: How important is this tuple in the whole database? This is often determined using PageRank-style metrics like ObjectRank.
  2. Affinity: How closely related is this specific table to the root subject? For instance, in a bibliographic database, a "Paper" has higher affinity to an "Author" than a "Country" does.
A schema graph showing the affinity and importance scores used to calculate the local importance of different data types.

Algorithmic Approaches

To find the best summary, the researchers developed several strategies to balance mathematical optimality with computational speed:

  • The DP Algorithm: A Dynamic Programming approach that finds the mathematically optimal summary. While perfect, it has exponential time complexity, making it too slow for large datasets.
  • Bottom-Up Pruning: A greedy heuristic that starts with the full, massive OS and iteratively "chops off" the least important leaf nodes until only $l$ remain.
  • Update Top-Path-l: A greedy heuristic that builds the summary from the root up, repeatedly adding the "best" available path of tuples.
  • Top-l Prelim-l OS: A clever preprocessing step that uses "avoidance conditions" to skip joining tables that couldn't possibly contribute to the top-$l$ summary, significantly speeding up the initial data retrieval.

Evaluation and Key Results

The researchers evaluated their approach on two industry-standard benchmarks: DBLP (a real-world bibliographic database) and TPC-H (a synthetic business database).

One of the most significant findings was the Monotonicity of importance: local importance generally decreases as you move further away from the root subject. This observation explains why greedy pruning algorithms—which are much faster than DP—actually produce results that are nearly identical to the optimal solution.

Key performance metrics included:

  • Effectiveness: In human evaluations on DBLP, the system achieved 75% to 90% agreement with what authors considered their own "ideal" summaries for sizes $l=10$ to $30$.
  • Approximation Quality: The greedy algorithms (especially Update Top-Path-l) achieved nearly 100% of the importance score of the optimal DP algorithm while being orders of magnitude faster.
  • Efficiency: The "Prelim-l" optimization reduced the size of the initial data processed by about 90%, allowing summaries to be generated in fractions of a second.

Future Directions

While the paper successfully bridges the gap between structured database queries and the "glanceable" nature of web search, the authors acknowledge areas for growth. Currently, the user must provide the size $l$; future systems might automatically determine the "natural" size for a summary. Additionally, incorporating "diversity" into the importance metric could ensure summaries don't just focus on one heavy branch (like a researcher's most cited papers) but instead provide a balanced view of all facets of the data entity.

Summary updated

BibTeX
@article{fakas2011size,
  author = {Georgios John Fakas and Zhi Cai and Nikos Mamoulis},
  title = {{Size-l Object Summaries for Relational Keyword Search}},
  journal = {Proc. VLDB Endow.},
  year = {2011},
  doi = {10.14778/2078331.2078338},
}
Figure