Name
Abstract | ||
|---|---|---|
Given a relation that contains main products and a set of relations corresponding to accessory products that can be combined with a main product, the Exploratory Top-k Join query retrieves the k best combinations of main and accessory products based on user preferences. As a result, the user is presented with a set of k combinations of distinct main products, where a main product is combined with accessory products only if the combination has a better score than the single main product. We model this problem as a rank-join problem, where each combination is represented by a tuple from the main relation and a set of tuples from (some of) the accessory relations. The nature of the problem is challenging because the inclusion of accessory products is not predefined by the user, but instead all potential combinations (joins) are explored during query processing in order to identify the highest scoring combinations. Existing approaches cannot be directly applied to this problem, as they are designed for joining a predefined set of relations. In this paper, we present algorithms for processing exploratory top-k joins that adopt the pull-bound framework for rank-join processing. We introduce a novel algorithm (XRJN) which employs a more efficient bounding scheme and allows earlier termination of query processing. We also provide theoretical guarantees on the performance of this algorithm, by proving that XRJN is instance-optimal. In addition, we consider a pulling strategy that boosts the performance of query processing even further. Finally, we conduct a detailed experimental study that demonstrates the efficiency of the proposed algorithms in various setups. HighlightsWe propose a new exploration technique using eXploratory Top-k Join (XTJ) queries.We analyze the XTJ-query properties and we propose an efficient algorithm (XRJN).We provide strong theoretical guarantees on the performance of our algorithm.We introduce an improved pulling strategy that reduces the overall processing cost.We generalize XTJ queries to efficiently combinations organized in groups and to include various aggregation functions. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.is.2016.09.004 | Inf. Syst. |
Keywords | Field | DocType |
Exploratory search,Top-k queries,Join queries,Product combinations,Combination ranking | Data mining,Joins,Tuple,Computer science,If and only if,Database,Exploratory search,Bounding overwatch | Journal |
Volume | Issue | ISSN |
64 | C | 0306-4379 |
Citations | PageRank | References |
0 | 0.34 | 34 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Orestis Gkorgkas | 1 | 119 | 4.97 |
| Akrivi Vlachou | 2 | 751 | 39.95 |
| Christos Doulkeridis | 3 | 899 | 55.91 |
| Kjetil Nørvåg | 4 | 1311 | 79.26 |