In the field of the multifeature querying it is possible to use many heuristics to retrieve top k objects to became low number of accesses to the sources. When the sources have many equal values, it is often hard to choose which source should be accessed next. In this paper we compare previous random approach with the parallel approach to the set of actual candidate sources.
Many times we want to find the best object or top k objects in the possible huge set of objects. The reason of which object is better than the other, is based on the properties of the objects. Such properties are typically fuzzy. For example, when we want to find top k hotels, we can look at a distance from the beach, price per night, number of stars, travel expenses, etc. We need is to specify, how to compute the overall score of each object to became the order of the objects. Moreover all these particular data can be accessible by different sources (web services).
There are several algorithms in this area, solving this problem. Ronald Fagin
introduced ”Fagin’s algorithm”, which solves this problem first time [
The ”quick-combine” algorithm was originally developed over multimedial
data. Such a data are typically continuous i.e. it is very unusual to have two
objects with the same value of a property. The experimental comparison of the
heuristics [
In chapter 2 we describe a formal model of data. In chapter 3 we present a generalized version of all mentioned algorithms and compare three different heuristics. The experimental comparison of the heuristics is showed in chapter 4. Chapter 5 concludes our paper. 2
Assume we have a finite set of objects. Cardinality of this set is N . Every object x has m attributes x1, . . . , xm. All objects (or identificators of objects) are in lists L1, . . . , Lm, each of length N . Objects in list Li are ordered descending by values of attribute xi. We can define two functions to access objects in lists. Let x be an object. Then si(x) is a grade (or score, rank) of object x in list the Li and ri(j) is an object in list the Li in the j-th position. Using the function si(x) we can realize the random access1 to the lists. The second type of access we will use, is the sorted access2. Using this type of access the grades of objects are obtained by proceeding through the list sequentially from the top.
We have also monotone aggregation function F , which combine grades of object x from lists L1, . . . , Lm. The overall value of an object x we denote as S(x) and it is computed as F (s1(x), . . . , sm(x)).
Our task is to find top k objects with highest overall grades. We also want to minimize time and space. That means we want to use as low sorted and random accesses as possible. 3
For each list Li, let ui = si(ri(zi)) be the value of the attribute of the last
object seen under sorted access, where zi is the number of that possition. Define
the threshold value τ to be F (u1, . . . , um). Because we assume that we have
a monotone aggregation function F and the lists are sorted descend by their
values, the threshold τ is the value, which none of still unseen objects can reach
[
Let z = (z1, . . . , zm) be a vector, which assigns for each i = 1, . . . , m the position in list Li last seen under sorted access. Let H be a heuristic that decides which list (or lists) should be accessed next under sorted access (notice that 1 Random access - direct access via an indexing mechanism. Please do not confuse this term with the term ”random approach”. The random approach to a set means, that we choose one element of this set randomly. 2 Sorted access - sequential access to a sorted list. heuristics can change during the computation). Moreover, assume that H is such, that for all j ≤ m we have H(z)j = zj or H(z)j = zj +1 and there is at least one i ≤ m such that H(z)i = zi+1. The set {i ≤ m : H(z)i = zi + 1} we call the set of candidate lists (or simply candidates) for the next sorted access.
In this paper we use three types of heuristics.
First heuristic (denote H1) does the sorted access in all m lists parallelly.
It means, that for each i ≤ m holds H(z)i = zi+1. This heuristic was firstly
presented by Fagin et al. [
The use of the ((δF/δx)∗Δx) heuristic (H2) was firstly presented by Gu¨ntzer
et al. [
S(x) = F (s1(x), . . . , sm(x)) ≥ τ (1)
Hence, when we can say, that this non-equality holds, we have the final top k list. Obviously, there are two ways to make (1) hold: to increase the left side or to decrease the right side. Heuristic H2 tries to decrease τ as fast as possible. As a criterion for a list Li, i ≤ m to be given to the set of candidates for the next sorted access, is to have Δi maximal. Δi is defined as: δF δxi Δi = (s1(ri(zi)), . . . , sm(ri(zi))) − ∗ (si(ri(zi − p)) − si(ri(zi))) (2)
The constant p is some suitable (small) natural number. Hence Δi is the multiplication of the partial derivative of aggregation function F from the left in the point (s1(r1(z1)), ..., sm(rm(zm))) and the expected change of values in p steps (Δx factor) of the i-th list. When we have Δi for each i ≤ m, we can set the value of H(z)i. Heuristic H2 sets H(z)i=zi+1 if Δi =max{Δj ; j ≤ m}. Otherwise H(z)i=zi. The only necessary condition we required from F is the continuity from the left.
The (δF/δx) ∗ x) heuristic (H3) is a variation of the last one. This heuristic
was presented by Gursky´ et al.[
The criterion (3) computes the partial derivation of F from the left in the point (s1(r1(z1)), ..., sm(rm(zm))) and multiply it with value in the point si(ri(zi)) in Li. This heuristic sets H(z)i=zi+1 if χi = max{χj ; j ≤ m}. Otherwise H(z)i=zi. We need the continuity from the left for the function F again. 163,65% When the aggregation function is the simple weighted mean, the derivation used by these heuristics is a constant, more precise it is the weight of the attribute.
Now we can describe the generalized Threshold algorithm: 0. z:=(0,. . . ,0), in case of algorithms ((δF/δx) ∗ Δx) or Δx/x, set the suitable small natural p. 1. Set the heuristic H: • ((δF/δx) ∗ x): H:=H3 • ((δF/δx) ∗ Δx): if any zi < p then H:=H1; otherwise H:=H2 • Δx/x: if any zi < p then H:=H1; otherwise if H=H1 then H:=H2; if
H=H2 then H:=H3; and if H=H3 then H:=H2. 2. • parallel approach: Do the sorted access in parallel to each of the sorted lists to all positions where H(z)i = zi+1. Put zi = H(z)i . • random approach: Do the sorted access to randomly chosen sorted list Li where H(z)i = zi+1. Put zi = zi + 1 and for each j ≤ m, j 6= i do nothing. 3. First control: Compute the threshold value τ . As soon as at least k objects have been seen whose grade is at least equal to τ , then go to step 6. 4. For every object x that was seen under sorted access in the step 2, do the random access to the other lists to find the grade si(x) of object in every list. Then compute the grade S(x) = F (s1(x), . . . , sm(x)) of object x. If this grade is one of the k highest ones we have seen, then remember object x and its grade S(x). 149,84% 120,00% 108,92%
191,94% 181,24%
180,78% 165,47% 158,96% 204,23% 134,57% 99,88% 99,88% 99,88% 99,91% 99,93% 99,94% 99,96% 1 5 10 50
100 88,04%
91,19% 76,06% 20 k 74,33% 30 5. Second control: As soon as at least k objects have been seen whose grade is at least equal to τ , then go to step 6, otherwise go to step 1. 6. Let Y be a set containing the k objects that have been seen with the highest grades. The output is then the graded set {(x, S(x)) : x ∈ Y }.
Individual algorithms differ in the steps 2 and 3. Shortly the (δF/δx)∗x) algorithm use heuristic H3 directly on beginning. The Quick-combine (or ((δF/δx) ∗ Δx)) algorithm use for the first p steps in each list the heuristic H1 and than the heuristic H2. The Δx/x algorithm use for first p steps in each list the heuristic H1, too. After that it switches between the heuristics H2 and H3.
Original algorithms choose the random approach in the step 3. All mentioned algorithms can have their ”parallel variant” too. In our experiments we compare all 6 possible variants. 4 4.1
Benchmark data The first sort of data are real data that come from randomly generated queries in information retrieval system with support of relational database. We used different combinations of local and global weights as different ways for weighting of occurrences of terms in documents to generate 6 sets of benchmark data. Each set include over 25 000 objects (documents) with 50 different attributes (terms). To measure all particular experimental results we 1000000 900000 800000 700000 A 600000 R + A S 500000 400000 300000 200000 100000 compare the average values from 6 sets of these benchmark data with the use of aggregation functions with randomly chosen weights for each list. Histograms of data are exponential - there is very low number of objects with high values and a lot of objects with low values. Such distribution is typical in the information retrieval area but in many other areas too.
Artificial data The second sort of data were generated with various distribution of values. We used 2 exponential and 2 logarithmic distributions with 10000 objects and 6 types of aggregation functions. The values of the attributes was rounded to 10 discrete values. Such a discretisation is quite common in real data e.g. number of stars of hotels, rating classes of companies, and other human produced ratings. Finest discretisation can be e.g. prices of some product or a guess for the length of a trip. Continuous data are typical for some physical experiments, precise measurements or multimedial data. In this paper we focus on the discrete data. Using different combination of the source data and aggregation functions we became 16 different inputs for algorithms. In the final results we use the averages of the particular results. 4.2
In our experiments we wanted to compare the random and parallel approach to the set of candidates. On the figure 1 and 2 we take as the base the random approach (=100%). We can see the performance of the parallel approach compared 14000 12000 10000 A R + A S 8000 6000 4000 2000 0 with the random approach for each heuristic. Both artificial and benchmark data shows, that different approach to the candidates does not change anything for the (δF/δx) ∗ x heuristic. For the x/Δx heuristic the random approach seems to be better in most cases.
In our results, the new parallel approach positively improved the performance of the (δF/δx)∗Δx heuristic over discretised values. This heuristics was originally developed for multimedial data. Using our improvement this heuristic can be quite efficient over discretized data too, but as we can see in figures 3 and 4 when we work over discretized values the new approach to the (δF/δx) ∗ Δx heuristic is still not better than quite stable x/Δx heuristics.
Why we have such a results? The parallel version of the (δF/δx)∗x algorithm has almost same results as its random variant maybe because there was almost none situation in which we had more than one candidate in the candidate set. On the other side the (δF/δx) ∗ Δx algorithm had many such a situations. The reason of this situation is the fact, that the expression (si(ri(zi − p)) − si(ri(zi))) almost always equals to zero for small p and discrete values in the lists. As experiments show, for this heuristic when we don’t know to prefer one list, it is better to access all lists. For the x/Δx heuristic seem the random approach to be better when k is greater or equals to 5.
We proposed the new parallel approach to the candidate set and compare it
with the previous random approach. We experimentally showed that this type
of approach improved the (δF/δx)∗Δx heuristic over discrete data. On the other
hand the x/Δx heuristic keeps its first place in lower number of accesses as was
shown in [