PDF档不能即时翻译 慢慢查太慢了 唉

• Dominated Customers: As the name implies, theseare customers who are dominated by the notebook,i.e., the notebook definitely satisfies their requirements.For example, the dominated customers of notebook A1are C5, C6, C8 and C9.• Dominating Customers: These are customers whodominate the notebook, i.e., the notebook definitelydoes not satisfy their requirements. For example, thedominating customer of notebook A1 is C1.• Incomparable Customers: These are customers whoneither dominate nor are dominated by the notebook.For example, C3 and C4 are incomparable customersof notebook A1.

2. PRELIMINARIESIn this section, we first set the context and state the assumptionsthat are adopted in this paper. We then introducethe three representative DRQs that we will consider inthis paper.2.1 Context and AssumptionsWe assume we have two manufacturers A and B, eachproducing a set of products PA = {A1, ...,As} and PB ={B1, ...,Bt}, respectively. We also have the preference of aset of customers C = {C1, ...,Cn}.Each of the products or customer preferences can be representedas a point in an N-dimensional space, D, with dimensionsD1,...,DN being the attributes of the products and customerpreferences. For simplicity, we use the general term“object” to refer to a product or a customer’s preference ifthe need to distinguish them is not needed.We assume that the domain values of each dimension Di,DV (Di), are discretized, fully ordered, numerical valueswhich can be mapped into positive integers {1,...,|DV (Di)|}.Thus, the whole of the N-dimensional space can be dividedconceptually into |DV (D1)|×|DV (D2)|×...|DV (DN)| cells,and each of the objects lies in one of the cells. Given anyobject p, we use the notation p[Di] to refer to the value ofp in dimension Di. We highlight the following:1. Our assumption is similar to most if not all data cubetechniques which discretize numeric dimensions to an acceptableresolution level.2. Mapping domain values into positive integers does not affectthe dominant relationship between the objects of analysis.This is only done to ensure easier discussion later onin the paper.We also assume, without loss of generality, that the attributesof a product or customer preference are minimumattributes [5], i.e., smaller values are preferred 2. With thisfinal assumption, we can now adopt the definition of dominatethat we have provided in Section 1 for the followingdefinitions:Definition 2.1. dominating(p,C,D)Given an object p, a set of objects C and a set of dimensionsD ⊆ D, we define dominating(p,C,D) as the set of objectsfrom C which are dominated by p in the subspace D of D.Definition 2.2. dominated(C, p,D)Given an object p, a set of objects C and a set of dimensionsD ⊆ D, we define dominated(C, p,D) as the set of objectsfrom C which dominate p in the subspace D of D. 

2.2 Three Representative DRQsIn this section, we look at three types of DRQs that arerepresentatives of the DRA we seek to examine.2.2.1 Linear Optimization QueryWe first look at LOQs. These queries are motivated bythe observation that manufacturers do not have infinite resources,and must consider various trade-offs and constraintswhen they position their products. For example, makingthe notebook lighter requires better components, which inturn pushes up the notebook price. Here, we model suchconstraints as a linear plane L that is anti-correlated withregard to all the dimensions. Our assumption here is thatall attributes are minimum attributes, and making a productbetter in one attribute requires sacrificing other aspectsin order to stay profitable.Definition 2.3. Linear Optimization Query (LOQ(L,C,D))Given a plane, L, and a set of objects, C, in an N-dimensionalspace of D, we define LOQ(L,C,D) as the aggregatemax(|dominating(p,C,D)|), where p is any point in theplane L. Note that for brevity, we take |dominating(p,C,D)| as themeasure for optimization. In fact, |dominated(C, p,D)| canbe used as the measure for optimization as well (to minimizein this case).Obviously, the actual location of the point p in the definitionof LOQ is as important as LOQ(L,C,D) itself. However,since p might not be unique, finding LOQ(L,C,D) canbe more efficient and would make our definition tidier. Laterin the paper, our algorithm for handling LOQ will identifyboth LOQ(L,C,D) and p. We now illustrate the concept ofLOQ using the following example:Example 1. Consider Figure 2, where customer preferencesfor the price and weight of the notebook are depicted togetherwith a plane L. The shaded region at the bottom-left of theplane represents configurations which are not profitable forthe manufacturer, and the region at the top-right of the planeare configurations which are profitable.In this example, LOQ(L,C,D)=4 at location p indicatedin the diagram. 

The first condition of Definition 4.5 ensures that the cellpartition is convex. The second condition ensures that thecell partition is maximal while having a regular rectangularshape. For example, assuming the dataset C has only onesingle point 1, 2(1, 2 means column 1 and row 2) ina space 3×3, Figure 6(a) shows the maximal cell partitionaccording to the number of points dominated (shown as thevalue of each cell in Figure 6).Although in this case we obtain the maximal classes, welose the important property that each class has a uniqueupper bound and lower bound.Definition 4.6. Upper Bound/Lower BoundGiven an equivalence class of cells, CL, the upper boundof CL is a cell p at the corner of the MBR that bounds CLsuch that p dominates all cells in CL. The lower boundof CL, is a cell p at the corner of the MBR that bounds CLsuch that p is dominated by all cells in CL. Since the existence of unique upper and lower bounds isvery useful for answering the three types of representativeDRQs, we want to keep the unique property of the upperbound for each class while doing cell partition. This is themotivation for the second condition of Definition 4.5.We use CL.upp, CL.low, CL.num and CL.Dn to representthe upper bound, the lower bound, the number of points containedand the number of points dominated by cells in anequivalence class CL, respectively. For example, the equivalenceclass in the green color region in Figure 6(b) can berepresented as CL={2,1, 3,2, 0}. That is, CL.upp is thecell 2,1, CL.low is the cell 3,2, and CL.Dn is 0.After having computed the value for each cell, the procedureCompress() in Algorithm 3 is immediately called bythe function Enumerate(). It iterates through all dimensions,and checks if the current cell can be merged with oneof its children (Lines 1-8). If it cannot merge into any existingclass, it forms a new class CLm itself (Lines 9-12).Note that CLm is a temp class and cannot be output yet.It may merge with one of its parent cells later. A tempclass list is maintained to keep all temp classes in reverselexicographical order of upper bounds.After a new temp class is created, it is inserted at the endof the list. Once we find that a cell cannot merge with oneof its child temp classes CLt, we delete CLt from the tempclass list and output it.Note that the output order from head to tail is very importantwhen the classes in the temp class list are output.It guarantees all classes are output in reverse lexicographicalorder. This order helps improve the efficiency of indexconstruction, which we will discuss below.The gray cells in Figure 5 show the class upper boundsproduced by Algorithm 1 when the dataset in Figure 4 (a)is used.

5.3 Comparative Dominant QueryComparative dominant queries are those queries whichaim to compare the set of dominated objects between competitiveproducts. So far, we have defined two kinds ofCAQs: CDQ−(A,B,C,D), which retrieves |gdominating(A,C,D)- gdominating ( B, C, D)|; and CDQT(A,B,C,D), which retrieves|gdominating(A,C,D)Tgdominating(B,C,D)|.To handle such queries, we can search the D*-tree fromthe root level by level. To accumulate the number of pointsthat is dominated by A (or B), we associate a class list withA (or B). Once we find the lower bound of a class CL isdominated by at least one point in A, then all children ofCL must be dominated by A. In this case, we need not searchthe subtrees of CL for A any more. What we need to do is toput CL and all its children to the class list of A and searchthe subtrees of CL further for B. If we find that the lowerbound of a class CL is dominated by at least one point inB, then all children of CL must be dominated by B. In thiscase, the search on subtrees of CL will be pruned off. Weonly need to put CL and all its children into the class list ofB. The switch between searching for A and B is controlledby the variable Flag.If the lower bound of CL (or CL) is not dominated byany point in A (or B) , the children of CL (or CL)needto be recursively processed. After we finish the search ofthe D*-tree, we get two class list, one is for A and one isfor B. What we need to do now is to accumulate the numof all classes on the same list. The algorithm of the CDQanswering algorithm is given in Algorithm 5. For brevity,we suppress further details.

Effect of Cardinality: To evaluate the effect of cardinalityon our techniques, we varied the cardinality of the datasets from 30 to 70. Figure 12(b) shows the run time of bothalgorithms against varying cardinality. We can see that ascardinality increases, the run time of the without-pruningapproach increases rapidly while that of the with-pruningapproach increases only modestly. This is because as car-dinality increases, the cube becomes sparse and the withpruningapproach is able to make use of the sparseness toreduce running time.