English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a directed acyclic graph (<italic>DAG</italic>), a <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-hop reachability query <inline-formula> <tex-math notation="LaTeX">${u}\xrightarrow {?k}{v}$ </tex-math></inline-formula> is used to answer whether there exists a path from <inline-formula> <tex-math notation="LaTeX">$u$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$v$ </tex-math></inline-formula> with length <inline-formula> <tex-math notation="LaTeX">$\leq k$ </tex-math></inline-formula>. Answering <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-hop reachability queries is a fundamental graph operation and has been extensively studied during the past years. Considering that existing approaches still suffer from inefficiency in practice when processing large graphs, we propose a novel labeling scheme, namely <italic>HT</italic>, to accelerate <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-hop reachability queries answering. <italic>HT</italic> uses a constrained 2hop distance label to maintain the length of shortest paths between a set of hop nodes and other nodes, and for the remaining reachability information, <italic>HT</italic> uses a novel topological level to accelerate graph traversal. Further, we propose to enhance <italic>HT</italic> by two optimization techniques. The experimental results show that compared with the state-of-the-art approaches, <italic>HT</italic> works best for most graphs when answering <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-hop reachability queries with small index size and reasonable index construction time.

$HT$ : A Novel Labeling Scheme for k-Hop Reachability Queries on DAGs