Any-k Algorithms for Exploratory Analysis with Conjunctive Queries

We recently proposed the notion of any-k queries , together with the KARPET algorithm, for tree-pattern search in labeled graphs. Any- k extends top- k by not requiring a pre-specified value of k . Instead, an any- k algorithm returns as many of the top-ranked results as possible, for a given time budget. Given additional time, it produces the next-highest ranked results quickly as well. It can be stopped anytime, but may have to continue until all results are returned. In the latter case, any-k takes times similar to an algorithm that first produces all results and then sorts them. We summarize KARPET and argue that it can be extended to support any- k exploratory search for arbitrary conjunctive queries.