{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:13:54Z","timestamp":1768108434334,"version":"3.49.0"},"reference-count":41,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T00:00:00Z","timestamp":1454284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T00:00:00Z","timestamp":1581465600000},"content-version":"vor","delay-in-days":1472,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1016\/j.jcss.2015.06.008","type":"journal-article","created":{"date-parts":[[2015,7,16]],"date-time":"2015-07-16T11:22:12Z","timestamp":1437045732000},"page":"23-44","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":12,"special_numbering":"PA","title":["Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs"],"prefix":"10.1016","volume":"82","author":[{"given":"Fang","family":"Wei-Kleiner","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.jcss.2015.06.008_br0010","series-title":"ICDE","first-page":"360","article-title":"Efficient creation and incremental maintenance of the HOPI index for complex XML document collections","author":"Schenkel","year":"2005"},{"key":"10.1016\/j.jcss.2015.06.008_br0020","series-title":"ICDE","article-title":"Top-k exploration of query candidates for efficient keyword search on graph-shaped (rdf) data","author":"Tran","year":"2009"},{"key":"10.1016\/j.jcss.2015.06.008_br0030","series-title":"SIGMOD","article-title":"Blinks: ranked keyword searches on graphs","author":"He","year":"2007"},{"key":"10.1016\/j.jcss.2015.06.008_br0040","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"10.1016\/j.jcss.2015.06.008_br0050","series-title":"Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data","first-page":"99","article-title":"Tedi: efficient shortest path query answering on graphs","author":"Wei","year":"2010"},{"key":"10.1016\/j.jcss.2015.06.008_br0060","series-title":"Proceedings of the Joint EDBT\/ICDT 2013 Workshops","article-title":"Finding nearest neighbors in road networks: a tree decomposition method","author":"Wei-Kleiner","year":"2013"},{"key":"10.1016\/j.jcss.2015.06.008_br0070","series-title":"Proceedings of the 29th International Conference on Very Large Data Bases, vol. 29","first-page":"802","article-title":"Query processing in spatial network databases","author":"Papadias","year":"2003"},{"key":"10.1016\/j.jcss.2015.06.008_br0080","series-title":"SIGMOD'08: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data","article-title":"Scalable network distance browsing in spatial databases","author":"Samet","year":"2008"},{"key":"10.1016\/j.jcss.2015.06.008_br0090","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","article-title":"Graph minors iii: planar tree-width","volume":"36","author":"Robertson","year":"1984","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.jcss.2015.06.008_br0100","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender","year":"1993","journal-title":"Acta Cybern."},{"issue":"1\u20132","key":"10.1016\/j.jcss.2015.06.008_br0110","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.artint.2005.04.004","article-title":"Unifying tree decompositions for reasoning in graphical models","volume":"166","author":"Kask","year":"2005","journal-title":"Artif. Intell."},{"key":"10.1016\/j.jcss.2015.06.008_br0120","series-title":"PODS","first-page":"124","article-title":"Tractable database design through bounded treewidth","author":"Gottlob","year":"2006"},{"key":"10.1016\/j.jcss.2015.06.008_br0130","series-title":"Fourth International IEEE Computer Society Computational Systems Bioinformatics Conference","first-page":"223","article-title":"Tree decomposition based fast search of RNA structures including pseudoknots in genomes","author":"Song","year":"2005"},{"key":"10.1016\/j.jcss.2015.06.008_br0140","series-title":"Proceedings of the 6th International Conference on Algorithms in Bioinformatics","first-page":"262","article-title":"Rapid ab initio RNA folding including pseudoknots via graph tree decomposition","author":"Zhao","year":"2006"},{"issue":"2","key":"10.1016\/j.jcss.2015.06.008_br0150","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"10.1016\/j.jcss.2015.06.008_br0160","series-title":"Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence","first-page":"201","article-title":"A complete anytime algorithm for treewidth","author":"Gogate","year":"2004"},{"key":"10.1016\/j.jcss.2015.06.008_br0170","series-title":"EDBT","article-title":"Efficiently indexing shortest paths by exploiting symmetry in graphs","author":"Xiao","year":"2009"},{"issue":"5439","key":"10.1016\/j.jcss.2015.06.008_br0180","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barabasi","year":"1999","journal-title":"Science"},{"key":"10.1016\/j.jcss.2015.06.008_br0190","series-title":"SODA","article-title":"Computing the shortest path: A* search meets graph theory","author":"Goldberg","year":"2005"},{"key":"10.1016\/j.jcss.2015.06.008_br0200","series-title":"ALENEX","article-title":"Reach-based routing: a new approach to shortest path algorithms optimized for road networks","author":"Gutman","year":"2004"},{"key":"10.1016\/j.jcss.2015.06.008_br0210","series-title":"SOFSEM (1)","article-title":"Point-to-point shortest path algorithms with preprocessing","author":"Goldberg","year":"2007"},{"key":"10.1016\/j.jcss.2015.06.008_br0220","series-title":"Proceedings of the 10th International Conference on Experimental Algorithms","first-page":"230","article-title":"A hub-based labeling algorithm for shortest paths in road networks","author":"Abraham","year":"2011"},{"issue":"4","key":"10.1016\/j.jcss.2015.06.008_br0230","doi-asserted-by":"crossref","first-page":"45:1","DOI":"10.1145\/2530531","article-title":"Shortest-path queries in static networks","volume":"46","author":"Sommer","year":"2014","journal-title":"ACM Comput. Surv."},{"issue":"5","key":"10.1016\/j.jcss.2015.06.008_br0240","doi-asserted-by":"crossref","first-page":"1338","DOI":"10.1137\/S0097539702403098","article-title":"Reachability and distance queries via 2-hop labels","volume":"32","author":"Cohen","year":"2003","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2015.06.008_br0250","series-title":"Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data","first-page":"445","article-title":"A highway-centric labeling approach for answering distance queries on large sparse graphs","author":"Jin","year":"2012"},{"issue":"6","key":"10.1016\/j.jcss.2015.06.008_br0260","doi-asserted-by":"crossref","first-page":"457","DOI":"10.14778\/2536336.2536346","article-title":"Is-label: an independent-set based labeling scheme for point-to-point distance querying","volume":"6","author":"Fu","year":"2013","journal-title":"Proc. VLDB Endow."},{"issue":"12","key":"10.1016\/j.jcss.2015.06.008_br0270","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.14778\/2732977.2732993","article-title":"Hop doubling label indexing for point-to-point distance querying on scale-free networks","volume":"7","author":"Jiang","year":"2014","journal-title":"Proc. VLDB Endow."},{"key":"10.1016\/j.jcss.2015.06.008_br0280","series-title":"Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data","first-page":"349","article-title":"Fast exact shortest-path distance queries on large networks by pruned landmark labeling","author":"Akiba","year":"2013"},{"key":"10.1016\/j.jcss.2015.06.008_br0290","series-title":"Proceedings of the 15th International Conference on Extending Database Technology","first-page":"144","article-title":"Shortest-path queries for complex networks: exploiting low tree-width outside the core","author":"Akiba","year":"2012"},{"key":"10.1016\/j.jcss.2015.06.008_br0300","series-title":"SIGMOD","article-title":"Efficient management of transitive relationships in large data and knowledge bases","author":"Agrawal","year":"1989"},{"key":"10.1016\/j.jcss.2015.06.008_br0310","series-title":"ICDE","article-title":"Dual labeling: answering graph reachability queries in constant time","author":"Wang","year":"2006"},{"key":"10.1016\/j.jcss.2015.06.008_br0320","series-title":"VLDB","article-title":"Stack-based algorithms for pattern matching on DAGs","author":"Chen","year":"2005"},{"key":"10.1016\/j.jcss.2015.06.008_br0330","series-title":"SIGMOD","article-title":"Fast and practical indexing and querying of very large graphs","author":"Trissl","year":"2007"},{"key":"10.1016\/j.jcss.2015.06.008_br0340","series-title":"SIGMOD","article-title":"Efficiently answering reachability queries on very large directed graphs","author":"Jin","year":"2008"},{"key":"10.1016\/j.jcss.2015.06.008_br0350","series-title":"SIGMOD","article-title":"3-hop: a high-compression indexing scheme for reachability query","author":"Jin","year":"2009"},{"key":"10.1016\/j.jcss.2015.06.008_br0360","series-title":"Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems","article-title":"Nearest neighbor queries in road networks","author":"Jensen","year":"2003"},{"key":"10.1016\/j.jcss.2015.06.008_br0370","series-title":"Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems","article-title":"Processing in-route nearest neighbor queries: a comparison of alternative approaches","author":"Shekhar","year":"2003"},{"issue":"1","key":"10.1016\/j.jcss.2015.06.008_br0380","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1145\/102782.102788","article-title":"Planar graph decomposition and all pairs shortest paths","volume":"38","author":"Frederickson","year":"1991","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/j.jcss.2015.06.008_br0390","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1109\/69.687976","article-title":"Hierarchical encoded path views for path query processing: an optimal model and its performance evaluation","volume":"10","author":"Jing","year":"1998","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"10.1016\/j.jcss.2015.06.008_br0400","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1287\/trsc.32.1.65","article-title":"Shortest path algorithms: an evaluation using real road networks","volume":"32","author":"Zhan","year":"1998","journal-title":"Transp. Sci."},{"key":"10.1016\/j.jcss.2015.06.008_br0410","series-title":"Proceedings of the 20th International Conference on Advances in Geographic Information Systems","first-page":"339","article-title":"Hldb: location-based services in databases","author":"Abraham","year":"2012"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000015000707?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000015000707?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T02:15:42Z","timestamp":1581473742000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000015000707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["S0022000015000707"],"URL":"https:\/\/doi.org\/10.1016\/j.jcss.2015.06.008","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2016,2]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2015.06.008","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2015 Elsevier Inc. All rights reserved.","name":"copyright","label":"Copyright"}]}}