BiG-index: Accelerating Keyword Search on Massive Graphs via Ontology-Driven Summarization
A Generic Ontology Framework for Indexing Keyword Search on Massive Graphs (Extended Abstract)
The paper introduces BiG-index (Bisimulation of Generalized Graph Index), a generic ontology-based framework designed to accelerate keyword search on massive graphs. It employs a hierarchical structure of graph generalization and bisimulation-based summarization to significantly reduce query processing time for existing search algorithms like Blinks and r-clique.
TL;DR
Keyword search on massive graphs like DBpedia or YAGO is often a "needle in a haystack" problem. The BiG-index framework introduces a hierarchical approach that leverages ontology information to "shrink" the search space. By generalizing labels and summarizing equivalent structures, it reduces the runtime of state-of-the-art algorithms like Blinks and r-clique by up to 50.5%, without changing the underlying search semantics.
Problem & Motivation
Knowledge graphs (KGs) are notoriously unstructured. When a user searches for keywords like "Massachusetts" and "Ivy League," a search engine must traverse millions of nodes to find a compact subgraph connecting them.
The authors observed a critical inefficiency: many subgraphs are structurally identical but treated as unique because of their specific labels (e.g., different "University" nodes). If we could group these similar structures using an Ontology (GOnt), we could perform the heavy lifting on a much smaller summary graph and then "zoom in" on the actual results.
Methodology: The Core of BiG-index
The BiG-index framework operates through a cyclical process of Generalization and Summarization.
1. Hierarchical Construction
The index is built as a set of graphs .
- Graph Generalization (Gen): Using the ontology, specific labels (e.g., "Harvard", "Yale") are replaced by their common super-type (e.g., "University").
- Graph Summarization (Bisim): The framework applies Maximal Bisimulation. Nodes that have the same generalized label and lead to the same types of neighboring nodes are collapsed into a single "supernode."
2. The Cost Model for Query Processing
Searching on the smallest (most summarized) graph is fast, but "specializing" the results back to the original graph takes time. BiG-index uses a Cost Model to determine the "sweet spot"—the optimal layer in the hierarchy to execute the query.
3. Answer Generation
Once a generalized answer is found in the summary graph, a Specialization Function () maps the supernodes back to real data vertices, pruning any branches that don't match the original specific query constraints.
Experiments & Results
The authors tested the framework using two popular search semantics: Blinks (ranked partition) and r-clique.
- Efficiency Gains: On the YAGO3 dataset, BiG-index achieved a 50.5% reduction in runtime for Blinks.
- Scalability: As shown in the performance charts, the index consistently outperforms baseline algorithms across varying query sizes.
The cost model proved highly effective, predicting the most efficient layer for query execution with 75% accuracy, ensuring that the overhead of indexing never outweighs the benefits of summarization.
Critical Insight & Conclusion
The brilliance of BiG-index lies in its label- and path-preserving properties. By ensuring that the summarization (bisimulation) doesn't "break" the paths between nodes, the framework remains generic—meaning any keyword search algorithm that relies on graph traversal can be plugged into BiG-index with minimal modification.
Takeaway: As knowledge graphs grow to billions of edges, flat indexing is no longer enough. Hierarchical, ontology-aware summarization is the key to maintaining sub-second query response times in large-scale relational discovery.