Name
Abstract | ||
|---|---|---|
Shortest distance query is a fundamental operation in large-scale networks. Many existing methods in the literature take a landmark embedding approach, which selects a set of graph nodes as landmarks and computes the shortest distances from each landmark to all nodes as an embedding. To answer a shortest distance query, the precomputed distances from the landmarks to the two query nodes are used to compute an approximate shortest distance based on the triangle inequality. In this paper, we analyze the factors that affect the accuracy of distance estimation in landmark embedding. In particular, we find that a globally selected, query-independent landmark set may introduce a large relative error, especially for nearby query nodes. To address this issue, we propose a query-dependent local landmark scheme, which identifies a local landmark close to both query nodes and provides more accurate distance estimation than the traditional global landmark approach. We propose efficient local landmark indexing and retrieval techniques, which achieve low offline indexing complexity and online query complexity. Two optimization techniques on graph compression and graph online search are also proposed, with the goal of further reducing index size and improving query accuracy. Furthermore, the challenge of immense graphs whose index may not fit in the memory leads us to store the embedding in relational database, so that a query of the local landmark scheme can be expressed with relational operators. Effective indexing and query optimization mechanisms are designed in this context. Our experimental results on large-scale social networks and road networks demonstrate that the local landmark scheme reduces the shortest distance estimation error significantly when compared with global landmark embedding and the state-of-the-art sketch-based embedding. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TKDE.2012.253 | IEEE Transactions on Knowledge and Data Engineering |
Keywords | Field | DocType |
retrieval technique,online query complexity,offline indexing complexity,local landmark indexing,global landmark embedding,local landmark close,traditional global landmark approach,query optimization,shortest distance query,query node,graph online search,local landmark scheme,approximate shortest distance computing,least common ancestor,distance estimation,query-dependent local landmark scheme,local search,local landmark embedding,graph theory,triangle inequality,graph compression,landmark embedding approach,large-scale network,query processing,query-independent landmark set,graph nodes,efficient local landmark indexing,landmark embedding,optimization technique,estimation,social network,embedded systems,data compression,relative error,accuracy,shortest path tree,approximation theory,indexing,indexation | Embedding,Lowest common ancestor,Computer science,Search engine indexing,Theoretical computer science,Triangulation (social science),Triangle inequality,Data compression,Landmark,Shortest-path tree | Journal |
Volume | Issue | ISSN |
26 | 1 | 1041-4347 |
Citations | PageRank | References |
20 | 0.72 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Miao Qiao | 1 | 90 | 5.04 |
| Hong Cheng | 2 | 3694 | 148.72 |
| Lijun Chang | 3 | 670 | 44.24 |
| Jeffrey Xu Yu | 4 | 7018 | 464.96 |