Relevant, yet Hard to Find: Directional Queries to the Rescue

Abstract

This paper introduces directional queries, a novel approach that addresses the limitations of traditional linear top-k queries. Linear top-k queries often fail to retrieve relevant results, particularly those with balanced attribute values or those not located on the convex hull of the dataset. Directional queries enhance linear scoring functions by incorporating a term that accounts for the distance of a tuple from a preference line determined by the user-specified weights. This enables the retrieval of more balanced and relevant results without imposing additional burden on the user. The paper discusses the shortcomings of linear top-k queries, introduces new indicators to quantify these limitations, and demonstrates the efectiveness of directional queries through extensive experiments on real and synthetic datasets.

Keywords

• eol>scoring functions
• skylines
• user preferences
• balanced results

1. Introduction

Linear top- queries rank tuples using a weighted sum of the attribute values and return the best-scoring tuples. Although they are the most common way to obtain relevant results from large, multi-attribute datasets (they can limit the cardinality of the result, can incorporate user preferences using weights, and eficient indexing and processing methods are available [ 1 ]), they exhibit several shortcomings, including the dificulty in specifying exact values for the weights (a hard task with many attributes [ 2, 3, 4 ]). In this paper, we focus on further, so far neglected, limitations of linear top- queries. First, the best result according to any of such queries is an element of the convex hull of the dataset [ 5 ], which can lead to missing relevant results, even if large values of are used. Second, depending on data distribution, tuples with somehow balanced attribute values might be hard to retrieve.

Example 1. Ana is looking for a room and aims to minimize both the price and the distance from the city center. Hotels still available for reservation mainly concentrate in two clusters: luxury hotels located at most a few hundred meters from the center, and budget hotels, further away from the center (see Figure 1a). Hotels , , and are more balanced alternatives, with intermediate prices and not too far from the center – this could be a good trade-of for Ana. If hotels are ranked by a linear function combining (normalized) price and distance, i.e., · /3000 + · /330 , 200 irp

c 150 (e€

) 100 50 distance (m) 500 1000 1500 2000 2500 3000 (a) Dataset hotel ranks weights 0.3 0.7 11 7 6 0.5 0.5 10 8 13 0.7 0.3 6 7 9 (b) Ranks of , , and no matter how Ana specifies the weights, the best result will be a hotel in one of the two clusters. Furthermore, for any choice of the weights, the top-5 set will never include any of , , or , whose ranks are shown in Figure 1b for several combinations of and .

As the example highlights, a dataset might contain interesting results that are hardly retrievable by any linear top- query. Points like , , or in Example 1 could be obtained by computing the skyline of the dataset [ 6 ] – a point belongs to the skyline if is undominated ( dominates if it is no worse than on all attributes and strictly better for at least one). The basic motivation underlying the introduction of skylines was indeed that of providing users with all relevant results, the rationale being that all other points are dominated, thus worse [ 6 ]. However, since skyline queries have major shortcomings (they cannot accommodate user preferences, are unable to limit the cardinality of the result, and have a higher computational cost), in this paper we use the skyline concept only for assessing the relevance of results returned by top- queries.

To analyze the efectiveness of top- queries, we introduce two indicators, aiming to quantify the dificulty of retrieving skyline points, 1 and experimentally observe that the existence of hard-to-retrieve yet relevant results is the rule rather than the exception. Then, to overcome the limits of linear top- queries, we introduce an original type of scoring functions, which give rise to what we call directional queries. Besides considering a weighted sum of the attribute values, directional queries also include a term accounting for how much a point is balanced with respect to the stated user preferences. 1.1. Background We consider a relational schema (1, . . . , ), with ≥ 1 numeric attributes whose domains are, respectively, 1, . . . , . A tuple = ⟨1, . . . , ⟩ over is an element of = 1 × . . . × ; each is denoted by []. Without loss of generality, in the following we assume = [ 0, 1 ], unless otherwise specified. An instance over is a set of tuples over ; in the following, we refer to an instance over with || = tuples.

Let , be tuples over . Then, dominates , written ≺ , if (i) ∀. 1 ≤ ≤ → [] ≤ [] , and (ii) ∃. 1 ≤ ≤ ∧ [] < [] . The skyline of , denoted by Sky(), is defined as 1The full paper [ 7 ] also considers two “robustness” indicators that we do not discuss here.

Sky() = { ∈ | ∄ ∈ . ≺ } . A scoring function is a function : → R+. For a tuple = ⟨1, . . . , ⟩ over , the value () is called the score of .2 The rank rank(; , ) of a tuple ∈ according to is 1 plus the number of tuples with a better score than , i.e., rank(; , ) = 1 + |{ ∈ | () < ()}|. We refer to a family ℒ = { | () = (∑︀=1 [])1/}, ≥ 1 , of scoring functions with a weight vector = ⟨1, . . . , ⟩ whose components are normalized, i.e., ∑︀

=1 = 1 ∧ ∀. ∈ [ 0, 1 ]. The vast majority of cases considered in the literature refer to top- queries using a scoring function in ℒ1, i.e., linear top- queries.

By interpreting the tuples of a relation as points in a -dimensional space, we can define the convex hull of as the intersection of all convex sets containing . As is well known [ 5 ], a prominent limitation of linear top- queries is that they can never rank as first any skyline tuple not in the convex hull of . Following this geometric view, using a scoring function in ℒ1 corresponds to moving from the origin and sweeping the data space with a hyperplane orthogonal to the weight vector [ 8 ];3 the order in which the points are intercepted determines their ranking. Similar considerations apply to ℒ, in which case we have “curved” fronts (one such example is shown in Figure 2b for ℒ2).

2. Indicators

Best rank. The first indicator we introduce to quantify the dificulty that linear top- queries might have in retrieving skyline tuples considers how well a skyline tuple can perform when a set of possible scoring functions ℱ is in use. The best rank of is the minimum of rank(; , ) when all functions in ℱ are considered:

For example, brank(; , ℒ1) is the best rank that can achieve when using a linear top- query. Larger values thus indicate a higher dificulty in retrieving . For ease of notation, we shall write brank(; ) to indicate brank(; , ℒ).4 Since with linear functions the set of 2We conventionally consider lower attribute values to be better than higher ones, as would be appropriate for attributes representing “cost” and similar characteristics (but the opposite convention would also be possible); consequently, lower score values are also preferred over higher ones. 3Clearly, hyperplanes are planes in 3D and lines in 2D. 4Note that brank1 coincides with the MaxRank operator of [ 9 ]. However, we prefer to qualify it as “best rank”, since one is indeed looking for the minimum (i.e., best) possible rank of a tuple. possible top-1 results is the intersection of Sky() and the vertices of the convex hull of , we say that a skyline tuple ∈ Sky() is convex if brank1(; ) = 1, concave otherwise.

Figure 2a shows a dataset whose skyline consists of 1, 2, and 3. We have brank1(1; ) = 1 (as can be seen, e.g., by increasing the values obtained via a linear scoring function of the form () = 23 [ 1 ] + 13 [ 2 ], i.e., scanning the dataset with lines perpendicular to the weight vector ⟨ 3 , 13 ⟩, as the blue line, which meets 1 first). Similarly, brank1(3; ) = 1 (following the purple 2 line). Yet, 2 never ranks first with any linear top- query, since brank 1(2; ) = 3. Concavity degree. The second indicator we introduce is called cdeg (for concavity degree), and it provides a way to measure the amount of non-linearity needed so that also a concave skyline tuple can become top-1 for some scoring function. Indeed, as a major result useful for defining cdeg, we can prove that every skyline tuple is the top-1 result for some function in ℒ, for a suficiently large . We call the smallest integer such that brank(; ) = 1 the concavity degree of : cdeg(; ) = min{ | brank(; ) = 1}. For instance, Figure 2b shows that 2 ∈N is concave and any linear top- query would rank as first either 1 or 3 (which are convex). However, consider the scoring function 2() = √︀0.5[ 1 ]2 + 0.5[ 2 ]2 in ℒ2, where the red arc corresponds to the points with the same score as 2. Since 2 is the first tuple to be met using this function, we have cdeg(2; ) = 2. Results. We have computed the indicators on 20 real and synthetic datasets of various sizes and distributions. Table 1 shows a small excerpt of our study (datasets are described in Section 4). There is always a significant number of non-convex skyline tuples, with extremely high brank1 values, i.e., impossible to find with a linear top- query with a reasonable . This is common to all datasets in Table 1 with large cardinality and dimensionality (last 4 rows), in each of which more than 95% of skyline tuples are concave, with very high values of brank1 and cdeg.

3. Directional queries

Above results show that many skyline tuples are hard to retrieve with linear top- queries (high values of the brank1 indicator). The cdeg values in Table 1, and the brank values (not shown in the table) obtained with low values of also suggest that the alternative of using non-linear queries would require much higher values of to easily retrieve many concave skyline tuples.5 5Besides adding an excessive cognitive burden for the users, who would also have to come up with a suitable value for , the higher is, the less preferences can influence the result, since when tends to infinity any ℒ function

Linear top- queries may fail to discover tuples that are well balanced across the various dimensions when the dataset contains tuples that are extremely good in one attribute but poor in the others. In order to give the user the opportunity to retrieve also these hard-to-find results, we propose to enrich (linear) scoring functions with a term explicitly favoring balanced results. The key observation is that, when a user specifies the weights, these already include an indication of the relative importance of the attributes, and, thus, what parts of the data space may contain the tuples corresponding to the best compromise of the diferent attributes. Thus, with no need of introducing new parameters, the weight vector itself may be used to determine a direction, that we call preference line, in the data space: the closer to the preference line, the better a tuple matches the original user’s intentions. When all weights are equal, the preference line coincides with the main diagonal of the data space, where all attribute values are equal. A consistent generalization to the case of unequal weights is to consider the requirement of weighted balance, which can be expressed by stating that weighted attribute values should now be equal, i.e., for any point on the preference line, we should have [] = [] for all , . This immediately leads to define the preference line PL() for the weight vector = ⟨ 1, . . . , ⟩ as the set:

PL() = {⟨¯1, . . . , ¯⟩ | ≥ 0}, where ¯ = 1/ for 1 ≤ ≤ .

In order to determine how much a tuple is balanced, we compute its (Euclidean) distance, Dist(, PL()), from PL(), which requires standard geometric techniques.

Since being close to the preference line is not suficient to characterize a good tuple (e.g., ⟨1, 1⟩ lies on the preference line PL(⟨0.5, 0.5⟩), but can hardly be preferred to any other tuple at all!), being as close as possible to the origin continues to matter. Our proposal, called directional query, is a top- query whose scoring function combines a weighted sum of the attribute values through a weight vector , i.e., a function in ℒ1 using , and the distance from the preference line determined by . The family Dir of scoring functions of directional queries is defined as: Dir = {︃

| () = ∑︁ [] + (1 − ) Dist(, PL()) =1 }︃ where ∈ [ 0, 1 ] expresses the trade-of between mean and distance (clearly, = 1 yields the linear functions). Directional queries have query fronts shaped like an “arrowhead”, whose width is determined by (the larger the value of , the wider the shape), as shown in Figure 3 for several combinations of and , where darker colors indicate better (lower) scores. 0.8A2 0.6 0.4 0.2 () tends to max{[ 1 ], . . . , []}, regardless of the weight vector.

4. Experiments

In this section we assess the efectiveness and eficiency of Dir queries and compare them to Lin and other kinds of top- queries. The relevant parameters are shown in Table 2. Datasets. The real datasets we use include NBA (all-time stats for 4832 NBA players from nba.com), RES (real estate data from zillow.com, with 3,569,678 6D tuples), and SEN (sensor data with 7 attributes and 2,049,280 tuples [ 10 ]). For synthetic datasets, we used the generator in [ 6 ] to produce, for any value of and mentioned in Table 2, a -dimensional anti-correlated dataset (ANT) of size . When ambiguity may arise, we indicate the number of dimensions and size as subscripts (e.g., ANT2;5 ). For readability, in the following we use Dir to refer to directional queries and Lin for linear queries. Due to space constraints, we focus on the SEN and ANT datasets, but the results we show extend to the other datasets introduced above. Algorithms. Dir queries can be implemented sequentially using a heap-based algorithm, resulting in a worst-case complexity of ( log ). For indexed datasets, Dir queries can use an R-tree [ 11 ] with a branch-and-bound algorithm [ 12, 13 ]. In order to minimize the number of visited nodes, a tight lower bound on the score of tuples reachable from any node can be determined by minimizing (1) through a non-linear programming solver [ 14 ]. Precision and recall. In order to assess the ability of Lin and Dir queries to retrieve relevant (skyline) tuples we start with classical precision and recall measures, where precision is the fraction of skyline tuples in the top- result, and recall is the fraction of retrieved skyline tuples. Results show that, on the average, Lin queries have, for any recall value, the worst precision. Cumulative recall. A major motivation underlying the introduction of directional queries is to allow more relevant tuples to be retrievable by top- queries. To this end, we introduce a measure of cumulative recall, r̂e︂c(, ℱ ), defined as the fraction of skyline tuples collectively retrieved by the functions in ℱ . This gives us an indication of how many tuples in the skyline have a chance to appear in the result of at least one top- query. Figure 4a shows that, for lll.rcceauum000001......024680 ◇○△⛌1 ◇○△⛌5 k◇△○⛌10 ◇○△⛌50 1◇○△⛌00 ◇○△⛌ ββββ====1211///332 lll.rcceauum00000.....02468 ◇○△⛌2 ◇○△⛌3 ◇○△d⛌4 ◇△○⛌5 ◇○△⛌6 ◇○△⛌ ββββ====1211///323 lll.rccaeuum000000......0123451◇○△⛌0K 5◇○△⛌0K1◇0○△⛌0K N5◇0○△⛌0K1◇△○⛌M (a) r̂e︁c on ANT3;1 as varies (b) r̂e︁c on ANT1 as varies (c) r̂e︁c on ANT3 as varies △ △ ○⛌ ββ==11//32 ○ ○ ◇⛌ ◇⛌ ◇△ ββ==21/3 5M10M ANT3;1 , the value = 2/3 entails a rec consistently larger than the one obtained with other ̂︂ values, reaching almost 80% of the skyline (1022 tuples). The relative performance of the diferent values of is confirmed also on ANT1 as varies (Figure 4b) and on ANT3 as varies (Figure 4c), with = 10. Lin queries are almost always the worst choice.

Balance. The distance Dist(, PL()) of a tuple from the preference line gives an indication of how balanced is with respect to the user requirements. Figure 5 shows that the average distance grows as grows (Figures 5a and 5b), or as grows (Figure 5c). Clearly, the lower the value of , the lower the average distance, but, as shown in the figure, all considered values of < 1 yield comparable performance, whereas Lin queries show a much poorer behavior.

Another measure of efectiveness is to consider how the skyline tuple closest to PL() is ranked by a query. Here, the diference between Lin and Dir queries is very substantial: for example, with = 100 queries on ANT3;1 , the median rank of the skyline tuple closest to PL() was 1 for ∈ {1/3, 1/2}, 2 for = 2/3, and 4724 for = 1.

Choice of . In order to choose an appropriate value for , we probe the dataset at hand with various values of , checking how they afect rec and average Dist. Our results show that rec ̂︂ ̂︂ is maximized when ∈ [0.6, 0.8] for all scenarios described in Table 2. In particular, = 0.7 consistently determines at least a 64% improvement in terms of r̂e︂c with respect to the case = 1 , while being at most 10% of the maximum r̂e︂c value obtained with any . Additionally, the choice = 0.7 grants an improvement of at least 79% in terms of average Dist with respect to = 1 in all tested scenarios. For these reasons, we set = 0.7 in our next experiments. Eficiency. We report CPU times only (all our datasets fit into main memory) averaged out over 10 executions using a 1.80GHz 4-core Intel processor with 16 GB of RAM.

Results of a sequential evaluation of top- queries show that in all tested scenarios Dir queries incur a slight computational overhead (about 15% more CPU time than Lin queries), due to the increased cost required for computing the score through non-linear function (1). Yet, CPU times are largely sub-second in all configurations up to 1M tuples.

Figure 6 reports execution times on the ANT dataset indexed by an R-tree.6 Besides CPU times (shown as dotted lines), the figure also accounts for the time spent for accessing the R-tree nodes, where we assume that each node access requires approximately 0.1ms. This is to highlight the diferences between the two query types in terms of node accesses. In lower dimensionalities, Dir queries incur a small overhead in terms of CPU time, but benefit from a reduced number of accesses to nodes. Such benefits are more visible as increases (Figure 6a). 6We adopted the implementation in [ 15 ] and extended it to support top- queries.

7 isem()4 6 5 m itt3 n o ue21 ○⛌ c x e0 1 ○⛌ ○⛌ 5 10 50 100

k (a) ANT3;1 as varies

⛌ ⛌ ○ ○ ⛌ lin ○ dir ○ ⛌ lin

○ dir d d (b) ANT1 as varies ( = 10) (c) ANT1 as varies ( = 10) This phenomenon is generally also present in the real datasets. Although the overall times are always largely sub-second in all tested scenarios, we also observe that the focus of Dir queries on the preference line more clearly distinguishes it from the Lin query when the weight vector is balanced. Figure 6c refers to queries with weights at most 20% of the perfectly balanced value 1/. Here the advantage of Dir queries becomes more evident, and even in the most adverse scenarios ( = 6, = 1 , = 10) the higher CPU times are compensated by the diference in accessed nodes (15,799 nodes for the Lin query vs only 4845 for the Dir query). Other methods. We also compared Dir queries with (i) SkyTop, which first computes the skyline and then selects from it the top- tuples according to a linear function, (ii) ORD [ 4 ], and (iii) non-linear queries using ℒ functions ( = 2..5). In all cases Dir queries were better both in terms of rec and average Dist. In particular, for non-linear queries increasing the value ̂︂ of leads to worsening both rec and average Dist. This confirms what was observed at the ̂︂ beginning of Section 3, since the higher is, the less weights can influence the result of a query.

5. Related Work and Conclusions

Based on the observation that linear top- queries can fail to obtain several relevant results and that they also have dificulties in returning balanced results respecting user preferences, we have first quantified this problem through the introduction of two indicators, and found that hard-to-retrieve skyline tuples occur very frequently in all the datasets we considered. Then, to obviate such limitations, we have introduced a novel type of scoring functions, leading to what we call directional queries. Experimental results show the efectiveness of directional queries, with nearly no computational overhead with respect to the classical linear queries.

Several lines of research are somehow related to our work. In particular, -regret queries [ 2 ] aim to return a set of tuples such that, for each function in a family ℱ , the ratio between the best score of a tuple in and the best score in the dataset is minimized. However, -regret queries are unable to accommodate user preferences, a main ingredient of directional queries. With the common idea of extending the notion of dominance, both the works in [ 16, 17, 18, 3 ] and the one in [ 4 ] consider regions in the space of weights instead of a single weight vector. Works in the former group of papers are unable to explicitly control the cardinality of the result, whereas [ 4 ] ofers cardinality control, yet it is limited to linear scoring functions.

Acknowledgments

The authors wish to thank A.P. Arbasino, S. Fumagalli, L. Lampariello, M. Somaschini, and L. Ruberto for implementations of some of the ideas developed here.

This work was supported by the Italian Ministry of University and Research (MUR) PRIN 2022 grant 2022XERWK9 “S-PIC4CHU - Semantics-based Provenance, Integrity, and Curation for Consistent, High-quality, and Unbiased data science”.

Declaration on Generative AI

The authors have not employed any Generative AI tools.

References

[1] I. F. Ilyas , G. Beskales, M. A. Soliman , A survey of top-k query processing techniques in relational database systems , ACM Comput. Surv . 40 ( 2008 ). URL: http://doi.acm. org/10 . 1145/1391729.1391730. doi: 10 .1145/1391729.1391730.

[2] D. Nanongkai , A. D. Sarma , A. Lall , R. J. Lipton , J. J. Xu , Regret-minimizing representative databases , PVLDB 3 ( 2010 ) 1114 - 1124 . URL: http://www.comp.nus.edu.sg/%7Evldb2010/ proceedings/files/papers/R99.pdf. doi:10.14778/1920841 .1920980.

[3] P. Ciaccia , D. Martinenghi , Flexible skylines: Dominance for arbitrary sets of monotone functions , ACM Trans. Database Syst . 45 ( 2020 ) 18 : 1 - 18 : 45 . URL: https://doi.org/10.1145/ 3406113. doi: 10 .1145/3406113.

[4] K. Mouratidis , K. Li , B. Tang , Marrying top-k with skyline queries: Relaxing the preference input while producing output of controllable size , in: G. Li , Z. Li , S. Idreos , D. Srivastava (Eds.), SIGMOD '21: International Conference on Management of Data , Virtual Event, China, June 20-25, 2021 , ACM, 2021 , pp. 1317 - 1330 . URL: https://doi.org/10.1145/3448016. 3457299. doi: 10 .1145/3448016.3457299.

[5] Y. Chang , L. D. Bergman , V. Castelli , C. Li , M. Lo , J. R. Smith , The onion technique: Indexing for linear optimization queries , in: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, May 16-18 , 2000 , Dallas, Texas, USA., 2000 , pp. 391 - 402 . URL: https://doi.org/10.1145/342009.335433. doi: 10 .1145/342009.335433.

[6] S. Börzsönyi , D. Kossmann , K. Stocker , The skyline operator , in: Proceedings of the 17th International Conference on Data Engineering, April 2-6 , 2001 , Heidelberg, Germany, 2001 , pp. 421 - 430 . URL: http://dx.doi.org/10.1109/ICDE. 2001 . 914855 . doi: 10 .1109/ICDE. 2001 . 914855 .

[7] P. Ciaccia , D. Martinenghi , Directional queries: Making top-k queries more efective in discovering relevant results , Proc. ACM Manag. Data 2 ( 2024 ) 232 : 1 - 232 : 26 . URL: https://doi.org/10.1145/3698807. doi: 10 .1145/3698807.

[8] P. Tsaparas , T. Palpanas , Y. Kotidis , N. Koudas , D. Srivastava , Ranked join indices , in: U. Dayal, K. Ramamritham , T. M. Vijayaraman (Eds.), Proceedings of the 19th International Conference on Data Engineering, March 5-8 , 2003 , Bangalore, India, IEEE Computer ICDE. 2003 . 1260799 .

[9] K. Mouratidis , J. Zhang , H. Pang, Maximum rank query , PVLDB 8 ( 2015 ) 1554 - 1565 . URL: http://www.vldb.org/pvldb/vol8/p1554-Mouratidis.pdf.

[10] G. Hebrail , A. Berard , Individual household electric power consumption , https://archive. ics.uci.edu/dataset/235/individual+household+electric+power+consumption, 2012 . Last accessed March 4 , 2024 .

[11] A. Guttman , R-trees: A dynamic index structure for spatial searching , in: B. Yormark (Ed.), SIGMOD'84, Proceedings of Annual Meeting , Boston, Massachusetts, USA, June 18-21, 1984 , ACM Press, 1984 , pp. 47 - 57 . URL: https://doi.org/10.1145/602259.602266. doi: 10 .1145/602259.602266.

[12] S. Berchtold , C. Böhm , D. A. Keim , H. Kriegel , A cost model for nearest neighbor search in high-dimensional data space , in: A. O. Mendelzon , Z. M. Özsoyoglu (Eds.), Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14 , 1997 , Tucson, Arizona, USA, ACM Press, 1997 , pp. 78 - 86 . URL: https://doi.org/10.1145/263661.263671. doi: 10 .1145/263661.263671.

[13] Y. Tao , V. Hristidis , D. Papadias , Y. Papakonstantinou , Branch- and -bound processing of ranked queries , Inf. Syst . 32 ( 2007 ) 424 - 445 . URL: https://doi.org/10.1016/j.is. 2005 . 12 .001. doi: 10 .1016/J.IS. 2005 . 12 .001.

[14] S. G. Johnson , The NLopt nonlinear-optimization package , https://github.com/stevengj/ nlopt, 2007 .

[15] Y. Barkan , Rtree, https://github.com/nushoin/RTree, 2009 .

[16] P. Ciaccia , D. Martinenghi , Reconciling skyline and ranking queries , PVLDB 10 ( 2017 ) 1454 - 1465 . URL: http://www.vldb.org/pvldb/vol10/p1454-martinenghi.pdf. doi:10. 14778/3137628 .3137653.

[17] K. Mouratidis , B. Tang , Exact processing of uncertain top-k queries in multi-criteria settings , PVLDB 11 ( 2018 ) 866 - 879 . URL: http://www.vldb.org/pvldb/vol11/p866-mouratidis.pdf. doi:10.14778/3204028 .3204031.

[18] P. Ciaccia , D. Martinenghi , FA + TA < FSA: Flexible score aggregation , in: Proceedings of the 27th ACM International Conference on Information and Knowledge Management , CIKM 2018 , Torino, Italy, October 22-26 , 2018 , 2018 , pp. 57 - 66 . URL: http://doi.acm. org/10 . 1145/3269206.3271753. doi: 10 .1145/3269206.3271753.