Decomposition Optimization for Minimizing Label Overflow in Prime Number Graph Labeling

Jaehoon KIM  Seog PARK  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.7   pp.1889-1899
Publication Date: 2010/07/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.1889
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Dependable Computing
Keyword: 
graph labeling,  prime number,  graph decomposition,  access control,  query processing,  

Full Text: PDF(1.1MB)
>>Buy this Article


Summary: 
Recently, a graph labeling technique based on prime numbers has been suggested for reducing the costly transitive closure computations in RDF query languages. The suggested prime number graph labeling provides the benefit of fast query processing by a simple divisibility test of labels. However, it has an inherent problem that originates with the nature of prime numbers. Since each prime number must be used exclusively, labels can become significantly large. Therefore, in this paper, we introduce a novel optimization technique to effectively reduce the problem of label overflow. The suggested idea is based on graph decomposition. When label overflow occurs, the full graph is divided into several sub-graphs, and nodes in each sub-graph are separately labeled. Through experiments, we also analyze the effectiveness of the graph decomposition optimization, which is evaluated by the number of divisions.