Can I read Proceedings of the 2012 international conference on Management of Data - SIGMOD '12 - A highway-centric labeling approach for answering distance queries on large sparse graphs on EtoBox?

Proceedings of the 2012 international conference on Management of Data - SIGMOD '12 - A highway-centric labeling approach for answering distance queries on large sparse graphs by Jin, Ruoming; Ruan, Ning; Xiang, Yang; Lee, Victor is a scholarly article available to read on EtoBox.

What is Proceedings of the 2012 international conference on Management of Data - SIGMOD '12 - A highway-centric labeling approach for answering distance queries on large sparse graphs about?

The distance query, which asks the length of the shortest path from a vertex u to another vertex v, has applications ranging from link analysis, semantic web and other ontology processing, to social network operations. Here, we propose a novel labeling scheme, referred to as Highway-Centric Labeling, for answering distance queries in a large sparse graph. It empowers the distance labeling with a highway structure and leverages a novel bipartite set cover framework/algorithm. Highway-centric labeling provides better labeling size than the state-of-the-art 2-hop labeling, theoretically and empirically. It also offers both exact distance and approximate distance with bounded accuracy. A detailed experimental evaluation on both synthetic and real datasets demonstrates that highwaycentric labeling can outperform the state-of-the-art distance computation approaches in terms of both index size and query time.

Author

Jin, Ruoming; Ruan, Ning; Xiang, Yang; Lee, Victor

Publisher

ACM Press

Published

2012

Language

EN