Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs

作者：

Highlights：

• We propose an indexing scheme for efficient graph query processing.

• We introduce a decomposition algorithm which works for all graphs.

• We design query answering algorithms for shortest path and kNN.

摘要

•We propose an indexing scheme for efficient graph query processing.•We introduce a decomposition algorithm which works for all graphs.•We design query answering algorithms for shortest path and kNN.

论文关键词：Graphs algorithms,Graph indexing,Shortest path,Tree decomposition,k Nearest Neighbors problems

论文评审过程：Received 31 October 2014, Revised 20 April 2015, Accepted 15 June 2015, Available online 15 July 2015, Version of Record 19 October 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.06.008