{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,9]],"date-time":"2025-11-09T07:43:59Z","timestamp":1762674239814,"version":"3.41.0"},"publisher-location":"New York, New York, USA","reference-count":41,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NIH","award":["R01 NS091421"],"award-info":[{"award-number":["R01 NS091421"]}]},{"name":"NSF","award":["CAREER III-1762268"],"award-info":[{"award-number":["CAREER III-1762268"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1145\/3178876.3186115","type":"proceedings-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T15:53:48Z","timestamp":1523634828000},"page":"489-498","source":"Crossref","is-referenced-by-count":10,"title":["Any-k"],"prefix":"10.1145","author":[{"given":"Xiaofeng","family":"Yang","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"given":"Deepak","family":"Ajwani","sequence":"additional","affiliation":[{"name":"Nokia Bell Labs, Dublin, Ireland"}]},{"given":"Wolfgang","family":"Gatterbauer","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"given":"Patrick K.","family":"Nicholson","sequence":"additional","affiliation":[{"name":"Nokia Bell Labs, Dublin, Ireland"}]},{"given":"Mirek","family":"Riedewald","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"given":"Alessandra","family":"Sala","sequence":"additional","affiliation":[{"name":"Nokia Bell Labs, Dublin, Ireland"}]}],"member":"320","reference":[{"unstructured":"2017. Yelp data set. (2017). https:\/\/www.yelp.com\/dataset_challenge\/dataset","key":"key-10.1145\/3178876.3186115-1"},{"unstructured":"2018. Any-k: anytime top-k pattern retrieval in labeled graphs (code). (2018). https:\/\/github.com\/northeastern-datalab\/Any-k-KARPET","key":"key-10.1145\/3178876.3186115-2"},{"unstructured":"2018. Flickr. (2018). http:\/\/www.flickr.com\/","key":"key-10.1145\/3178876.3186115-3"},{"unstructured":"2018. Vitrage. (2018). https:\/\/wiki.openstack.org\/wiki\/Vitrage","key":"key-10.1145\/3178876.3186115-4"},{"doi-asserted-by":"crossref","unstructured":"Charu C. Aggarwal and HaixunWang. 2010. Graph Data Management and Mining: A Survey of Algorithms and Applications. Springer, 13--68.","key":"key-10.1145\/3178876.3186115-5","DOI":"10.1007\/978-1-4419-6045-0_2"},{"unstructured":"Reza Akbarinia, Esther Pacitti, and Patrick Valduriez. 2007. Best Position Algorithms for Top-k Queries. In Proc. VLDB. 495--506.","key":"key-10.1145\/3178876.3186115-6"},{"unstructured":"Gunes Aluc. 2015. Workload Matters: A Robust Approach to Physical RDF Database Design. Ph.D. Dissertation. University of Waterloo, Ontario, Canada.","key":"key-10.1145\/3178876.3186115-7"},{"doi-asserted-by":"crossref","unstructured":"L. J. Chen and Y. Papakonstantinou. 2010. Supporting top-K keyword search in XML databases. In Proc. ICDE. 689--700.","key":"key-10.1145\/3178876.3186115-8","DOI":"10.1109\/ICDE.2010.5447818"},{"unstructured":"James Cheng, Yiping Ke, and Wilfred Ng. 2009. Efficient processing of grouporiented connection queries in a large graph. In CIKM. ACM, 1481--1484.","key":"key-10.1145\/3178876.3186115-9"},{"unstructured":"Luigi Pietro Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2001. An improved algorithm for matching large graphs. In Proc. IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition. 149--159.","key":"key-10.1145\/3178876.3186115-10"},{"unstructured":"Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2004. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. on Pattern Analysis and Machine Intelligence 26, 10 (2004), 1367--1372.","key":"key-10.1145\/3178876.3186115-11"},{"unstructured":"Jérôme Euzenat, Pavel Shvaiko, et al. 2007. Ontology matching. Vol. 18. Springer.","key":"key-10.1145\/3178876.3186115-12"},{"doi-asserted-by":"crossref","unstructured":"Ronald Fagin, Amnon Lotem, and Moni Naor. 2003. Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66, 4 (2003), 614--656.","key":"key-10.1145\/3178876.3186115-13","DOI":"10.1016\/S0022-0000(03)00026-6"},{"doi-asserted-by":"crossref","unstructured":"Christos Faloutsos, Kevin S McCurley, and Andrew Tomkins. 2004. Fast discovery of connection subgraphs. In Proc. ACM SIGKDD. 118--127.","key":"key-10.1145\/3178876.3186115-14","DOI":"10.1145\/1014052.1014068"},{"doi-asserted-by":"crossref","unstructured":"Gang Feng. 2014. Finding k shortest simple paths in directed graphs: A node classification algorithm. Networks 64, 1 (2014), 6--17.","key":"key-10.1145\/3178876.3186115-15","DOI":"10.1002\/net.21552"},{"doi-asserted-by":"crossref","unstructured":"Jiawei Han, Yizhou Sun, Xifeng Yan, and Philip S Yu. 2010. Mining knowledge from databases: an information network analysis approach. In Proc. ACMSIGMOD. 1251--1252.","key":"key-10.1145\/3178876.3186115-16","DOI":"10.1145\/1807167.1807333"},{"doi-asserted-by":"crossref","unstructured":"Huahai He and Ambuj K Singh. 2008. Graphs-at-a-time: query language and access methods for graph databases. In Proc. ACM SIGMOD. 405--418.","key":"key-10.1145\/3178876.3186115-17","DOI":"10.1145\/1376616.1376660"},{"doi-asserted-by":"crossref","unstructured":"John Hershberger, MatthewMaxel, and Subhash Suri. 2007. Finding the K Shortest Simple Paths: A New Algorithm and Its Implementation. ACM Trans. Algorithms 3, 4, Article 45 (Nov. 2007).","key":"key-10.1145\/3178876.3186115-18","DOI":"10.1145\/1290672.1290682"},{"doi-asserted-by":"crossref","unstructured":"Katja Hose and Ralf Schenkel. 2013. WARP: Workload-aware replication and partitioning for RDF. In Proc. ICDE Workshops. 1--6.","key":"key-10.1145\/3178876.3186115-19","DOI":"10.1109\/ICDEW.2013.6547414"},{"unstructured":"Jiewen Huang, Daniel J. Abadi, and Kun Ren. 2011. Scalable SPARQL Querying of Large RDF Graphs. PVLDB 4, 11 (2011), 1123--1134.","key":"key-10.1145\/3178876.3186115-20"},{"unstructured":"Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman. 2008. A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40, 4 (2008), 11:1--11:58.","key":"key-10.1145\/3178876.3186115-21"},{"doi-asserted-by":"crossref","unstructured":"Gjergji Kasneci, Shady Elbassuoni, and Gerhard Weikum. 2009. Ming: mining informative entity relationship subgraphs. In Proc. CIKM. ACM, 1653 1656.","key":"key-10.1145\/3178876.3186115-22","DOI":"10.1145\/1645953.1646196"},{"doi-asserted-by":"crossref","unstructured":"Naoki Katoh, Toshihide Ibaraki, and Hisashi Mine. 1982. An efficient algorithm for k shortest simple paths. Networks 12, 4 (1982), 411--427.","key":"key-10.1145\/3178876.3186115-23","DOI":"10.1002\/net.3230120406"},{"unstructured":"Ioannis Koutis and Ryan Williams. 2016. LIMITS and Applications of Group Algebras for Parameterized Problems. ACM Trans. Algorithms 12, 3 (2016), 31:1-- 31:18.","key":"key-10.1145\/3178876.3186115-24"},{"unstructured":"Robert Krauthgamer and Ohad Trabelsi. 2017. Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern. Technical Report. https:\/\/arxiv.org\/abs\/1708.07591","key":"key-10.1145\/3178876.3186115-25"},{"doi-asserted-by":"crossref","unstructured":"Jinsoo Lee,Wook-Shin Han, Romans Kasperovics, and Jeong-Hoon Lee. 2012. An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases. PVLDB 6, 2 (2012), 133--144.","key":"key-10.1145\/3178876.3186115-26","DOI":"10.14778\/2535568.2448946"},{"doi-asserted-by":"crossref","unstructured":"Jiongqian Liang, Deepak Ajwani, Patrick K Nicholson, Alessandra Sala, and Srinivasan Parthasarathy. 2016. What Links Alice and Bob? Matching and Ranking Semantic Patterns in Heterogeneous Networks. In Proc. WWW. 879--889.","key":"key-10.1145\/3178876.3186115-27","DOI":"10.1145\/2872427.2883007"},{"doi-asserted-by":"crossref","unstructured":"Anna Lubiw. 1981. Some NP-complete problems similar to graph isomorphism. SIAM J. Comput. 10, 1 (1981), 11--21.","key":"key-10.1145\/3178876.3186115-28","DOI":"10.1137\/0210002"},{"unstructured":"Apostol Natsev, Yuan-Chi Chang, John R. Smith, Chung-Sheng Li, and Jeffrey Scott Vitter. 2001. Supporting Incremental Join Queries on Ranked Inputs. In Proc. VLDB. 281--290.","key":"key-10.1145\/3178876.3186115-29"},{"doi-asserted-by":"crossref","unstructured":"Thomas Neumann and Gerhard Weikum. 2010. The RDF-3X engine for scalable management of RDF data. The VLDB Journal 19, 1 (2010), 91--113.","key":"key-10.1145\/3178876.3186115-30","DOI":"10.1007\/s00778-009-0165-y"},{"doi-asserted-by":"crossref","unstructured":"Cartic Ramakrishnan, William H Milnor, Matthew Perry, and Amit P Sheth. 2005. Discovering informative connection subgraphs in multi-relational graphs. ACM SIGKDD Explorations Newsletter 7, 2 (2005), 56--63.","key":"key-10.1145\/3178876.3186115-31","DOI":"10.1145\/1117454.1117462"},{"unstructured":"Liam Roditty. 2007. On the K-simple shortest paths problem in weighted directed graphs. In Proc. SODA. 920--928.","key":"key-10.1145\/3178876.3186115-32"},{"doi-asserted-by":"crossref","unstructured":"Haichuan Shang, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. 2008. Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism. PVLDB 1, 1 (2008), 364--375.","key":"key-10.1145\/3178876.3186115-33","DOI":"10.14778\/1453856.1453899"},{"unstructured":"Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S Yu, and Tianyi Wu. 2011. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. PVLDB 4, 11 (2011), 992--1003.","key":"key-10.1145\/3178876.3186115-34"},{"doi-asserted-by":"crossref","unstructured":"Hanghang Tong and Christos Faloutsos. 2006. Center-piece subgraphs: problem definition and fast solutions. In Proc. ACM SIGKDD. 404--413.","key":"key-10.1145\/3178876.3186115-35","DOI":"10.1145\/1150402.1150448"},{"unstructured":"Julian R Ullmann. 1976. An algorithm for subgraph isomorphism. JACM 23, 1 (1976), 31--42.","key":"key-10.1145\/3178876.3186115-36"},{"doi-asserted-by":"crossref","unstructured":"Fang Wei. 2010. Efficient graph reachability query answering using tree decomposition. In Int. Workshop on Reachability Problems. 183--197.","key":"key-10.1145\/3178876.3186115-37","DOI":"10.1007\/978-3-642-15349-5_13"},{"doi-asserted-by":"crossref","unstructured":"Xiaofeng Yang, Deepak Ajwani, Wolfgang Gatterbauer, Patrick K Nicholson, Mirek Riedewald, and Alessandra Sala. 2018. Any-k: anytime top-k pattern retrieval in labeled graphs. Technical Report. https:\/\/arxiv.org\/abs\/1802.06060","key":"key-10.1145\/3178876.3186115-38","DOI":"10.1145\/3178876.3186115"},{"unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Proc. VLDB. 82--94.","key":"key-10.1145\/3178876.3186115-39"},{"doi-asserted-by":"crossref","unstructured":"Jin Y. Yen. 1971. Finding the K Shortest Loopless Paths in a Network. Management Science 17, 11 (1971), 712--716.","key":"key-10.1145\/3178876.3186115-40","DOI":"10.1287\/mnsc.17.11.712"},{"doi-asserted-by":"crossref","unstructured":"Shijie Zhang, Shirong Li, and Jiong Yang. 2009. GADDI: distance index based subgraph matching in biological networks. In Proc. EDBT. 192--203.","key":"key-10.1145\/3178876.3186115-41","DOI":"10.1145\/1516360.1516384"}],"event":{"number":"2018","sponsor":["SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web","IW3C2, International World Wide Web Conference Committee"],"acronym":"WWW '18","name":"the 2018 World Wide Web Conference","start":{"date-parts":[[2018,4,23]]},"location":"Lyon, France","end":{"date-parts":[[2018,4,27]]}},"container-title":["Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178876.3186115","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3186115&ftid=1957443&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:28Z","timestamp":1750212688000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3178876.3186115"}},"subtitle":["Anytime Top-k Tree Pattern Retrieval in Labeled Graphs"],"proceedings-subject":"World Wide Web","short-title":[],"issued":{"date-parts":[[2018]]},"references-count":41,"URL":"https:\/\/doi.org\/10.1145\/3178876.3186115","relation":{},"subject":[],"published":{"date-parts":[[2018]]}}}