Any-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs

Files in This Item:
File Description SizeFormat 
ajwani_www18.pdf1.74 MBAdobe PDFDownload
Title: Any-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs
Authors: Yang, Xiaofeng
Ajwani, Deepak
Gatterbauer, Wolfgang
et al.
Permanent link:
Date: 27-Apr-2018
Online since: 2019-04-10T11:21:34Z
Abstract: Many problems in areas as diverse as recommendation systems, social network analysis, semantic search, and distributed root cause analysis can be modeled as pattern search on labeled graphs (also called "heterogeneous information networks" or HINs). Given a large graph and a query pattern with node and edge label constraints, a fundamental challenge is to find the top-k matches according to a ranking function over edge and node weights. For users, it is difficult to select value k. We therefore propose the novel notion of an any-k ranking algorithm: for a given time budget, return as many of the top-ranked results as possible. Then, given additional time, produce the next lower-ranked results quickly as well. It can be stopped anytime, but may have to continue until all results are returned. This paper focuses on acyclic patterns over arbitrary labeled graphs. We are interested in practical algorithms that effectively exploit (1) properties of heterogeneous networks, in particular selective constraints on labels, and (2) that the users often explore only a fraction of the top-ranked results. Our solution, KARPET, carefully integrates aggressive pruning that leverages the acyclic nature of the query, and incremental guided search. It enables us to prove strong non-trivial time and space guarantees, which is generally considered very hard for this type of graph search problem. Through experimental studies we show that KARPET achieves running times in the order of milliseconds for tree patterns on large networks with millions of nodes and edges.
Type of material: Conference Publication
Publisher: ACM
Start page: 489
End page: 498
Copyright (published version): 2018 IW3C2 (International World Wide Web Conference Committee)
Keywords: Computation theory and mathematicsInformation systemsNetworking and information technology R&DHeterogeneous information networks
DOI: 10.1145/3178876.3186115
Other versions:
Language: en
Status of Item: Not peer reviewed
Is part of: WWW '18 Proceedings of the 2018 World Wide Web Conference
Conference Details: The International World Wide Web Conference Committee (IW3C2), Lyon, France, 23-27 April 2018
ISBN: 978-1-4503-5639-8
Appears in Collections:Computer Science Research Collection

Show full item record

Google ScholarTM



This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.