In this article we focus on efficient solving of searching the best K objects in more attributes according to user's preferences. Local preferences are modelled with one of four types of fuzzy function. Global preferences are modelled concurrently with an aggregation function. We focused on searching the best K objects according to various user's preferences without accessing all objects. Therefore we deal with the use of TA-algorithm and MD-algorithm. Because of local preferences we used B+-trees during computing of Fagin's TA-algorithm. For searching the best K objects MD-algorithm uses multidimensional B-tree, which is also composed of B+-trees. We developed an MXT-algorithm and a new data structure, in which MXT-algorithm can effectively find the best K objects by user's preferences without accessing all the objects. We show that MXT-algorithm in some cases achieves better results in the number of accessed objects than TA-algorithm and MD-algorithm.
Nowdays, huge amounts of data in various web systems grow exponentially.
Users try to find various objects in this data, such as laptops, cars, apartments,
holidays, etc. These objects have various attributes. According to the values of
attributes, users search for the best objects for them. However, each user prefers
objects with other values of attributes [
Most users look for only a few objects that are best suited to their preferences.
Therefore, it is advantageous according to the user’s preferences directly to find
the best K objects. Making it possible to find the best K objects from the set
of objects X, it must be possible to judge which objects are better or worse for
a user U . Every user prefers objects with own preferences, which are modelled
locally by means of a fuzzy function and globally by means of an aggregation
function [
In the next, text we describle using B+-tree [
We deal also with methods and data structures for effective solution of
topK problem [
We developed a MXT-algorithm and a new data structure based on B+trees, in which MXT-algorithm can effectively find the best K objects by user’s preferences without accessing all the objects. We will show advantages of the new MXT-algorithm and a comparison with the results of other algorithms. We show that MXT-algorithm in some cases achieves better results in the number of accessed objects than TA- and MD-algorithm.
A background concerning modelling user preferences is contained in Section 2. Section 3 presents use of B+-tree for approaching the top-K problem. Sections 4 and 5 are devoted to explaining principles of Fagin’s TA-algorithm and MD-algorithm. In Section 6 we describe our new MXT-algorithm and new data structure, which is used during computation of MXT-algorithm. Section 7 presents the results of the tests and compares MD-algorithm with Fagin’s algorithms. Finally, Section 8 provides some suggestions for a future work. 2
User’s preferences In this article, we suppose a set of objects X with m attributes A1, ..., Am. Every object x ∈ X has m values aix, ..., axm of corresponding attributes. When searching for the best K objects, a user U chooses user’s preferences, which determine suitability of the object x ∈ X in dependence with its m values of attributes a1 , ..., axm for user U . In accordance to user U preferences, it is possible x to find the best K object for user U . We are using a model of user preferences, which is based on concatenation of local preferences and global preferences. At first, user U decides how he prefers objects according to each of attributes Ai, i = 1, ..., m, and then chooses a relationship between these attributes.
Local preferences reflect how the object is preferred according to only one
attribute. In this work, we used a mapping fi: dom(Ai) → [
Nominal attribute has a finite range of possible values, usually strings. For a
nominal attribute Ai user U has to rate each value of the attribute. For example,
it is mark of some products. Local preference of user U for the nominal attribute
Ai is represented as mapping fiU (x): aix → [
Ordinal attribute has some natural value ordering, other than lexical ordering.
Typical examples are integer numbers. Domain of ordinal attribute is subset of
continuous interval. The local preference of user U for the ordinal attribute Ai
is represented by fuzzy function [
For the worst object x ∈ X, fiU (x) = 0 holds and for the best one, fiU (x) = 1. Comparing fiU (x1) and fiU (x2) of two objects x1 and x2, it is possible to decide which of them is suitable for the user U according to the value of i-th attribute. When fiU (x1) > fiU (x2), then x1 is more suitable. When fiU (x1) = fiU (x2), then x1 and x2 are equally suitable.
Article [
Global preferences express how the user U prefers objects from X according
to all attributes A1, ..., Am. On the set of objects X, we consider aggregation
function @ with m variables p1, ..., pm specified as @(p1, ..., pm) : [
With aggregation function, a user U can define the mutual relations of the attributes. For example, we can use arithmetic average. For implementation of user’s influence to the aggregate function, it is possible to use weighted average, where weights u1, ..., um of single attributes A1, ..., Am determine how the user prefers single attributes, @(x) = u1·p1+...+um·pm . When the user does not care u1+...+um about i-th attribute Ai when rating the objects, he can then put 0 into the aggregate function, i.e. ui = 0.
In this work, every user U express his preference as functions f1U , ..., fmU and @U . Every object x ∈ X has its own special global rating @U (x), a measure of pertinence for the user U . In this way, it is possible to find the best K objects for the user U . When there are more objects with the same rating as rating of the best K-th object, a random object is chosen. 3
Usage of B+-tree
For application of local user’s preferences we need a data structure, from which it
is possible to obtain objects according to user’s fuzzy function f U in descending
order according to f U . Let the objects of the set X be indexed in the B+-tree
[
Every object x ∈ X is indexed by the key k ∈ dom(A), a value of which is equal to a value of attribute ax of object x, i.e. k = ax. For a key k, in general, more objects with the same A attribute value can exist in X. Therefore, we use the object array, in which are stored objects with the same value of the key k. For every key k there is a pointer to corresponding object array.
Since the leaf nodes of the B+-tree are linked in two directions [
In general, f U cannot be monotone in its domain. In this case, the domain
can be divided into continuous intervals (also leaf level of B+-tree), where f U
is monotone on each of these intervals. From the intervals, objects are obtained
concurrently according to f U as well as for monotone fuzzy function [
Fagin’s TA-algorithm
Fagin et al. describe in [
Fagin’s algorithm TA (threshold algorithm) needs to access the lists L1, ..., Lm sequentially and also directly. With the sequential access, TA searches the lists step by step from the top to the bottom and obtains pairs (x, aix). For every object x, which is detected for the first time in obtained pair (x, aix), TA obtains the missing attribute values of the object x by a direct access to the other lists.
TA uses the list TK , in which it keeps the best actual K objects ordered
according to their value of @(x). During the run of TA a threshold Th is counted,
which is calculated by means of inserting the last seen values of attributes
last, ..., almast in the lists L1, ..., Lm, respectively, at the sequential access to the
a1
aggregate function Th = @(al1ast, ..., almast). Rating of the K-th best object in TK
we denote MK . When Th ≤ MK , TA is able to stop and returns TK as the list
of the best K objects. TA can finish before it comes to the end of all the lists
[
Input: Lists L1, ..., Lm, Aggregation @, int K;
Output: List TK;
var List TK; {temporary list of objects}
begin
while(|TK| < K or Th > MK )do
(x, aix) = getNextPair(L1, ..., Lm); {it obtains next pair from
aliast = aix; one of the lists L1, ..., Lm} [
insert object x to the list TK on the right place according to @(x); else if(@(x) > MK )then begin delete K-th object from the list TK; insert object x to the list TK on the right place by @(x); end; endwhile; end. 4.1
Application of local preferences Original Fagin’s algorithms offer the possibility of rating objects only globally with an aggregate function @ and to find the best K object for the user U only according to his global preference. For the support of the local preferences, it is necessary that every i-th list Li contains pairs (x, fiU (x)) in descending order according to user’s fuzzy function fiU (x).
For application of local user’s preferences, we use B+-tree (see Section 3).
We use as the lists L1, ..., Lm a list of m B+-trees B1, ..., Bm, where in
B+tree Bi all objects are indexed by values of i-th attribute Ai. Moreover, this
structure is common for all users. A particular user U only specifies his local
preferences with fuzzy functions f1U , ..., fmU and global preferences with function
@U . Then the algorithm sequentially obtains pairs (x, fiU (x)) from B+-trees
B1, ..., Bm according to preferences of user U [
Algorithm TA also uses the direct access to the lists L1, ..., Lm, where for object x it is needed to obtain its unknown value aix from Li. B+-tree is not able to make this operation, because it is not possible to obtain the value directly. For a realization of direct access we can use, for example, an associative array. 5
Multidimensional B-tree and MD-algorithm
In [
We use the mark ρ(ki) for the pointer of the key k in B+-tree in i-th level of MDB-tree. If i < m, then ρ(ki) refers to B+-tree in (i + 1)-th level of MDB-tree. If i = m, i.e. B+-tree is in the last level of MDB-tree, then ρ(ki) refers to object array, where objects with the same values of all the m attributes are stored.
For explicit identification of B+-tree in MDB-tree, we use the sequence of
keys, which is called tree identifier [
Furthermore, in MDB-tree we use the best rating B(S) of B+-tree S [
MD-algorithm
Obtaining all the objects from MDB-tree is possible with a recursive procedure,
which searches MDB-tree in depth-first search. The work [
Let the keys from the B+-tree S with the identifier (k1, ..., ki−1) be the keys obtained one by one by a run of procedure findTopK. The pointer ρ(p) refers to B+-tree P in the next level or to the object array P . Let MK be the rating of the K-th best object in temporary list TK of best K objects. If B(P ) ≤ MK holds, then the procedure findTopK(MDB-tree, (k1, ..., ki−1)) can stop in S.
The following pseudo-code describes MD-algorithm.
Input: MDBtree MDB-tree, Aggregation @, int K; Output: List TK; var List TK; {temporary list of objects} begin
findTopK(MDB-tree, (∅), @, K); return TK; end. procedure findTopK(MDBtree MDB-tree, Identifier (k1, ..., ki−1),
Aggregation @, int K); while(there is next key in B+-tree)do {with identifier (k1, ..., ki−1)} ki = getNextKey(MDB-tree, (k1, ..., ki−1));
{ρ(ki) refers to B+-tree P or it refers to the object array P } if(|TK| = K and B(P ) ≤ MK )then return; if(P is B+-tree)then
findTopK(MDB-tree, (k1, ..., ki−1, ki), @, K); if( P is object array)then while(there is the next object x in P )do if(|TK| < K )then
insert object x to TK to the right place according to @(x); else if(@(x) > MK )then begin delete K-th object from the list TK; insert object x to the list TK on the right place by @(x); end; endwhile; endwhile; end. procedure getNextKey(MDBtree MDB-tree, Identifier (k1, ..., ki−1)); choose the next key ki with next highest value of Ai in B+-tree of MDB-tree with identifier (k1, ..., ki−1); return ki ; end.
From B+-tree we can obtain keys in descending order according to user’s fuzzy function fiU (x). Because MDB-tree is composed from B+-trees, it is possible to use application of the local user preferences directly in MD-algorithm by finding the K best objects in MDB-tree. The following procedure getNextKey changes the original MD-algorithm. procedure getNextKey(MDBtree MDB-tree, Identifier (k1, ..., ki−1),
FuzzyFunction fiU ); choose the next key ki with next highest value of i-th fuzzy function in B+-tree of MDB-tree with identifier (k1, ..., ki−1); return ki; end. 6
Combination of TA and MD-algorithm Here we describe a new top-K algorithm, which is based on combination of MDalgorithm and Fagin’s TA-algorithm.
MD-algorithm has the best results, when the objects stored in MDB-tree are
distributed regularly (uniform distribution) [
Example 1. We have set of 8 822 flats for rent in Prague. Flats have four important attributes for users, District, Type, Area, and Price. These attributes have sizes of domains, kdom(District)k = 10, kdom(T ype)k = 10, kdom(Area)k = 229, kdom(P rice)k = 411, respectively. When a user prefers attributes District and Type, then it is better to store flats in MDB-tree and to use MD-algorithm. On the other hand, when a user prefers attributes Area and Price, then it is better to use TA-algorithm and to store flats in Fagin’s lists.
In general, the attribute with a small domain size is nominal attribute and attribute with big domain size is ordinal attribute (see Section 2). It is valid also in Example 1, attributes District and Type are nominal attributes, Area and Price are ordinal attributes. 6.1
Therefore we developed a new top-K algorithm, MXT-algorithm, which is based on combination of MD-algorithm and Fagin’s TA-algorithm. MXT-algorithm uses a new data structure, which is composed of MDB-tree and Fagin’s sorted lists. This data structure is shown in Figure 4.
We suppose a set of objects X with m attributes A1, ..., Am. Attributes A1, ..., An are nominal attributes and An+1, ..., Am are ordinal attributes. Attributes A1, ..., An are stored in MDB-tree with n levels. Instead of the following m − n levels of MDB-tree, groups of m − n Fagin’s sorted lists are used. These lists contain pairs (x, aix) with values of attributes An+1, ..., Am.
MXT-algorithm is developed on the base of MD-algorithm. First n attributes A1, ..., An are searched in the same way as during the computation of MDalgorithm. In every B+-tree there are references into the groups of m − n Fagin’s sorted lists. In each of these groups a new instance of TA-algorithm is run.
The efficiency of MXT-algorithm is based on idea that we do not need to obtain the best K objects from each the group of m − n Fagin’s sorted lists. We need to obtain only objects with better rating as MK (rating of the K-th best object in global list TK ). There, it is sufficient that local threshold Thlocal (in each the group of m − n Fagin’s sorted lists) with MK is compared. Local TA-algorithm is able to stop earlier in group of Fagin’s sorted lists, Thlocal ≤ MK holds earlier than in original TA-algorithm. (see Figure 4, dotted line).
The following pseudo-code describes the MXT-algorithm, where procedure getNextKey is the same as in the MD-algorithm (see Section 5). Input: MDBtree MDB-tree, Aggregation @, int K; Output: List TK; var List TK; {temporary list of objects} begin findTopK(MDB-tree, (∅), @, K); return TK; end. procedure findTopK(MDBtree MDB-tree, Identifier (k1, ..., ki−1),
Aggregation @, int K); while(there is next key in B+-tree)do {with identifier (k1, ..., ki−1)} ki = getNextKey(MDB-tree, (k1, ..., ki−1));
{ρ(ki) refers to B+-tree P or it to group of Fagin’s lists P } if(|TK| = K and B(P ) ≤ MK )then return; if(P is B+-tree)then
findTopK(MDB-tree, (k1, ..., ki−1, ki), @, K); if( P is group of Fagin’s lists)then while(|TK| < K or Thlocal > MK )do (x, aix) = getNextPair(L1, ..., Lm); {it obtains next pair from aliast = aix; one of the lists L1, ..., Lm} Thlocal = @(al1ast, ..., almast); if(x ∈/ TK)then get the missing attribute values of the object x; if(|TK| < K)then
insert object x to the list TK on the right place by @(x); else if(@(x) > MK )then begin delete K-th object from the list TK; insert object x to the list TK oaccording to @(x); end; endwhile; endwhile; end. 6.2
Application of local preferences Analogously to MD-algorithm in attributes A1, ..., An it is possible to use application of the local user preferences. Procedure getNextKey changes MXTalgorithm in the same way as in the MD-algorithm (see Section 5.1).
In attributes An+1, ..., Am it is also possible to use application of the local user preferences. Analogously to TA-algorithm, we use as the group of m − n Fagin’s lists Ln+1, ..., Lm, a list of m − n B+-trees Bn+1, ..., Bm, and for a realization of direct access we can use, for example, an associative array. 7 Implementation and Experiments We implemented top-K TA-algorithm, MD-algorithm and MXT-algorithm using lists based on B+-trees. The implementation has been developed in Java and it uses data structures created in memory. Important for us was the number of accesses into used data structures during calculation of top-K algorithms.
We tested TA-, MD- and MXT-algorithm. During the tests, we used uniform preferences. We used user’s fuzzy functions with course ”f (x)=x” as user’s local preferences, and we used the arithmetic average as user’s global preference.
At first, we tested two sets of 100 000 objects with 5 attributes with normal and regular (uniform) distribution of attribute values. We used TA-algorithm, MD-algorithm and three variants of MXT-algorithm, i.e. MXT 3, MXT 2, MXT 1, because attribute types were not important there. For example, variant MXT 3 uses first 3 attributes as nominal attributes, which are stored as MDB-tree with 3 levels and other 2 attributes are stored as groups of 2 Fagin’s sorted lists. Figure 5 shows results of this test.
The best results have been achieved with MXT 3 and MD-algorithm for the set of objects with the regular distribution of the attributes values. Test for sets of objects with normal distribution of attribute values has shown that the new MXT-algorithm can in some cases also achieve worst results.
Afterwards, we tested the sets of 8 822 flats for rent in Prague (see Section 6, Example 1). There were two nominal attributes with a small domain size and two ordinal attributes with a big domain size. We used TA-algorithm, MD-algorithm and the most suitable variant of MXT-algorithm (as MXT 2 in previous test). Figure 6 shows results of this test for uniform preferences, and for real user’s preferences, where user prefers flats of some types in specific districts, with smaller prices and bigger areas. These two ordinal attributes were preferred according to non-monotone fuzzy functions.
The best results has been achieved with MXT-algorithm for both of used preferences. The test has shown that MXT-algorithm is most efficient solution of top-K problem for some cases. Especially it is efficient for a set of objects, which has nominal attributes with a small domain size and several ordinal attributes with a big domain size. We developed a new MXT-algorithm, which can effectively find the best K objects by user’s preferences without accessing all the objects. We implemented top-K algorithms TA-, MD- and MXT-algorithm with support of user’s preferences. Results of MXT-algorithm have shown to be comparable with those obtained by others used top-K algorithms.
MXT-algorithm is based on combination TA- and MD-algorithm. According to type of object attributes it is possible to store a set of objects in MDB-tree, in Fagin’s lists or in data structure, which MXT-algorithm uses. Moreover, MXTalgorithm can find the best K objects in each of these data structures. In this meaning, TA- and MD-algorithm are extreme cases of MXT-algorithm.
Motivation of future research can be to find application of developed
algorithms in various data structures. The article [