DEIM Forum 2016 D7-1

A Branch-and-Bound Method for Group Reverse Queries
Yuyang DONG† , Hanxiong CHEN† , Katazuka FURUSE† , and Hiroyuki KITAGAWA†† Department of Computer Science, Information and systems, University of Tsukuba,
Ibaraki 305-8577, Japan
E-mail: †tou@dblab.is.tsukuba.ac.jp, ††{chx,furuse,kitagawa}@cs.tsukuba.ac.jp
Abstract Recently, reverse ranks queries attracted significant interests in research. They applied for real-life
applications such as market analysis and product placement. One of them, Reverse k-ranks queries returns user
preferences that treat a given product be more favorite than others. Reverse k-ranks queries can help manufacturers find potential buyers even for an unpopular product. In marketing, manufacturers also willing to oﬀer several
products for sale as one combined product. Just like cable television industry often bundles channels and fast foodindustry combines separate food items into a complete meal. This kind of product bundling can help manufacturers
extend market power even with imperfectly competitive products. Unfortunately, Reverse k-ranks queries and otherreverse ranks queries can only for one product. To address this limitation, we propose a group reverse k-ranks
queries to find k most potential user preference for a set of products. To solve group reverse k-ranks more eﬃciently,
we propose a Tree pruning method (TPM) and a Branch-and-Bound pruning method (BPM). Theoretical analysis
and experimental results show the eﬃcacy of proposed methods.
Key words group reverse queries, branch-and-bound, product bundling

1. INTRODUCTION
Top-k queries and reverse k-ranks queries are two diﬀerent
kinds of view-model. Top-k queries is a user-view model that
support to consumers by obtaining the best k products fora user preference. On the other hand, reverse k-ranks [12]queries charge to manufactures to discover the potential consumers by retrieving the most appropriate user preference
than others. So it is a manufacture view mode. From theperspective of manufacturers, reverse k-ranks can be a toolfor identifying the customers and estimate the marketing ofproducts.

Figure 1: The example of reverse 1-rank queries.

Figure 1 shows the example of reverse k-ranks query whenk = 1. There are 5 diﬀerent cell phones (p1 ∼ p5 ) and thescores of ”smart” and the ”rating”, are recorded in table (a).
Two users preference (Tom and Jerry) showed in table (b);these preferences consist of the weights for each attribute.
The scores of a cell phone based on a user preference is theresult of the inner product between the cell phone attributes
vector and user preference vector. Without loss of generality,
in this paper, minimum scores will be preferable. The resultof Reverse 1-ranks queries showed at the last cells in Table(b). For example, Tom thinks cell phone p1 is the 3rd bestphone, Jerry thinks it is the 5th. To manufacture, Tom has
more possibility than Jerry to buy cell phone p1 , so reverse
1-rank query returns Tom as the result.

1. 1 motivation
In marketing, manufacturers also do sell with ProductBundling. Product Bundling is oﬀering several products forsale as one combined product. It is a common feature inmany imperfectly competitive product markets. For examples, Microsoft Co., Ltd include a word processor, spreadsheet, presentation program and other useful software into asingle Oﬃce suite. The cable television industry often bundles various channels into a single tier to expand channelmarket. Manufacturers of Video games also willing to groupa popular game with other games with the same theme, they
can obtain more benefits by selling them together.
As the Product Bundling is an important approach forpopular objects, [12] proposed reverse k-ranks queries, whichfinds for a given object the top-k user preferences whose rank
for the object is highest among all users.
Some other related researches on reverse query are listed
Figure 2: The example of group reverse 1-rank queries.

in the following. The essential diﬀerence is that they treat
one data set, while in reverse rank queries, there are twosale, it is significant to help manufacturers find the mostdata sets. Given a data point and aim at finding the queries

probable buyers for their bundled products. Unfortunately,that have this data point in their result set. Contrast withthe reverse k-ranks query and other kinds of reverse ranking

the nearest neighbour search, [3] proposed a reverse nearest

queries are all designed for just one product. To solve thisneighbour (RNN) queries. Opposite to RNN, [11] proposed

limitation, we propose a new query definition that finds kreverse furthest neighbour (RFN) queries to find the points

customers with smallest group rank values, where the rank

who deem query point as their furthest neighbour. [10] clas-of the group defined as the sum of each product’s rank. We

sifies RKNN (reverse k nearest neighbour) into bichromaticname this query as group reverse k-rank queries (GR-k inand monochromatic queries. This make RKNN be similar

abbreviation).

with reverse rank queries that obtaining users that prefer

Figure 2 shows the example of GR-1 queries. There are

given product as favorite, but they are diﬀerent queries.

3 groups of Bundling Product sale, {p1 , p2 }, {p2 , p3 } and

RKNN evaluates relative Lp distance in one euclid space with

{p4 , p5 }. The group rank of {p1 , p2 } is 5 by Tom’s prefer-two points. However, reverse rank queries focus on the ab-ence and is 6 by Jerry’s. So GR-1 query return Tom as thesolute ranking among all objects, and scores are found by

result.

doing inner product (weighted sum) with two diﬀerent vec-

1. 2 Contribution

tors, user preference and object, and they from diﬀerent data

The contribution of this paper is:

space. The reverse skyline query uses the advantages of prod-•

ucts to find the potential customers based on the dominanceTo address these ”one product” limitation from re-verse k-ranks queries. We define a new ranking query namedof the competitors products [2, 4].

group reverse k-ranks query (GR-k) that return best k user

3. PROBLEM STATMENT

preferences to match a set of products. The GR-k can supThere are a data set P and a data set W all in d di-port to Product Bundling.
•

We propose the solutions to process GR-k query eﬃ-

mension.

Each product p ∈ P is a vector which con-ciently. They are tree pruning method (TPM) and branch-tains d non-negative scoring attribute. p can represented as

and-bound pruning method (BPM).

p = (p[1], p[2], ..., p[d]), and p[i] is an attribute value of i’th

We employ the experiments both on factual data anddimension. The user preference w ∈ W is also a vector, andsynthetic data. The experimental results evaluate the eﬃ-

w[i] corresponds to p[i] so that evaluate the i’th attribute of∑dp, where w[i] >= 0 and i=1 = 1.

•

ciency of the proposed methods.

2. RELATED WORKThe score of p on w is defined by doing inner product∑das fw (p) =i=1 w[i] · p[i]. Without loss of generality, weUser-view model queries, top-k queries. The Onion tech-consider smaller score values are preferable that same withnique [1] precomputes and stores the convex hulls of data

related research.

points in layers like an onion. The evaluation of a linear top-

The definitions of reverse k-ranks queries [12] are as follow.

k query is accomplished by starting from the outmost and［Definition 1］ (reverse k-ranks query). Given a point set P ,processing these layers inward.

a weighting vector set W , a positive integer k, and a queryating the impact of a potential product in the market, based

point q. R-kRanks query returns a set S, S ⊂ P , |S| = k,such that ∀wi ∈ S, ∀wj ∈ (W −S), rank(wi , q) <= rank(wj , q)

on preferences of users that treat this product as one of theirholds. Where rank(w, q) = |R|, where |R| is the cardinality

top-k products. There are also various applications of re-of R, a subset of P . ∀pi ∈ R, we have f (w, pi ) < f (w, q) and∀pj ∈ (P − S), f (w, pj ) >= f (w, q).

Reverse top-k queries [5, 6] have been proposed for evalu-

verse top-k queries, [9] identifying the most influential prod-

The group rank is defined by the sum of each rank of q,ucts, [8] monitoring the popularity of locations based on user
mobility. [7] propose a branch-and-bound algorithm for re-soverse top-k queries.

［Definition 2］ (gRank(w, Q)) Given a point set P , a

However, in order to answer reverse query for some lessweighting vector w, and a query points set Q, the group∑|Q|
rank of Q for w is gRank(w, Q) = i=1
rank(w, qi ), whereset of products and user preferences. To boost eﬃciency, we
index the products data set with R-tree for grouping similar
products and use upper and lower bounders of MBRs (Minimum Bounding Rectangles) to save computing. We call ittree pruning method (TPM). The Geometry view of TPM
algorithm is showed in Figure 3. The blue shadow part, formby dash line and space border, below Q.down or above Q.up
is the part that TPM algorithm can filter.
Base on the feature of MBRs in R-tree, we can use the twofacts below to pruning unnecessary MBRs entirely.
F act 1. For a query point set Q, a weighting vector w, a
Figure 3: The filtering part (blue) of TPM algorithm with

MBR e of R-tree. If f (w, e.up) < f (w, Q.down), ∀p ∈ e, ∀q ∈2-dimension data.

Q, it holds f (w, q) < f (w, p).
F act 2. For a query point set Q, a weighting vector w, a
MBR e of R-tree. If f (w, e.down) < f (w, Q.up), ∀p ∈ e, ∀q ∈qi ∈ Q.
The definition of group reverse k-ranks queries is:Q, it holds f (w, q) > f (w, p).

［Definition 3］ (group reverse k-ranks query). Given a point

set P , a weighting vector set W , a positive integer k, andAlgorithm 2 Tree Pruning Method (TPM)a query point set Q. GR-kRanks query returns a set S,

Require: P, W, Q

S ⊂ P , |S| = k, such that ∀wi ∈ S, ∀wj ∈ (W − S),
gRank(wi , Q) <= gRank(wj , Q) holds.

Ensure: result set heap

4. Tree Pruning Method

1: heap ⇐ ∅2: for each w ∈ {first k element in W } do
3:heap.insert(w, gRank(w, Q))

4: minRank ⇐ heap’s last rank.
5: for each w ∈ W − {first k element in W } do

Algorithm 1 TraRtreeP6:rnk ⇐ T raRtreeP (P, w, Q, minRank)

Require: P, w, Q, minRank

7:

if rnk =| −1 thenEnsure: include: rnk; discard: -1;

8:heap.insert(w, rnk)

1: rnk ⇐ 0

9:minRank ⇐ heap’s last rank.

2: heapP.enqueue(RtreeP.Root())

10: return heap

3: while heapP.isN otEmpty() do
4:e ⇐ heapP.dequeue()

5:for each ei ∈ e do

6:
7:
8:

if f (w, ei .up) < f (w, Q.down) thenrnk ⇐ rnk + ei .size() ∗ |Q|
if rnk >= minRank thenreturn -1

9:
10:
11:
12:

else if f (w, ei .down) > f (w, Q.up) thencoutinue13:

if ei is a leaf node then14:

for each q ∈ Q do

16:
17:

19:
20:

gorithm can return whether the group rank of Q is smaller
than the given minRank or not. As the algorithm 1 shows,
T raRtreeP algorithm use R-tree to prune similar points incounter the group rank of Q (Line 1). Then we recursively
check the MBRs in products R-tree from the root (Line 2).

if f (w, q) > f (w, ei ) thenIf the upper bounder score of current entry ei smaller thanrnk + +
if rnk >= minRank thenquery set Q’s lower bound score, the counter rnk increased

return -1

18:

When given data set P , a weighting vector w, a query
point set Q and a positive integer k. The T raRtreeP al-a group (MBR). In this algorithm, we use counter rnk to

else

15:

4. 1 TraRtreeP algorithm

else
heapP.enqueue(ei )21: return rnk

by ei .size() ∗ Q (Line 6-7).

When rnk get greater thanminRank, it means this Q should not rank in minRankon w and the algorithm return -1 to terminate (Line 8-9). If
lower bound score of current entry greater than Q’s upperbound score, we don’t need to check any child in this entry

Processing group reverse k-ranks queries with the big data
set is a challenge since the naive algorithm needs to evaluate every pair of product and user preference. It will cost
vast amounts of computation with a large number of dataand just skip this entry (Line 10-11). Other situation, whenchecking a leaf node of entries, we compute the score of eachq ∈ Q on w and increase rnk (Line 13-18). If the algorithm
does not return in the recursion, we return rnk as the rank

Q and minRank. The algorithm returns 1 if all w ∈ We
make Q rank in minRank, and returns -1 if none of w ∈ We
make Q rank in minRank. When some of We may let Q
rank better than minRank, the algorithm returns 0.
The diﬀerence with TPM algorithm stated in Section 4.,
BPM use two R-tree to index weighting vectors and products. Based on the methodology of branch-and-bound, BPM
can prune both weighting vectors and products.
Figure 4: The filtering part (blue) of BPM algorithm with

5. 2 BPM algorithm

2-dimension data.
Algorithm 3 TraRtreeP++of this Q based on the weighting vector w.
4. 2 TPM algorithm.

Require: P, We , Q, minRank
Ensure: include: 1; discard: -1; 0: uncertain
1: rnk ⇐ 0, rnkU p ⇐ 0

In TPM algorithm, we first initialize a heap with first k

2: heapP.enqueue(RtreeP.root())

weighting vectors and their ranks (Line 1-3). Then for oth-3: while heapP.isN otEmpty() doers weighting vectors, we call Algorithm 1 to check the group4:e ⇐ heapP.dequeue()rank of the query set Q (Line 6). If the current w can make5:

for each ei ⊂ e do

Q’s rank better than the last rank in heap, this w will be

6:inserted into heap with its rank. The heap will auto-update
itself by removing the last element and insert a new w anda group rank, and then the heap sort itself by the order ofif f (We .up, Q.up) > f (We .down, ei .down) thenif f (We .up, ei .up) < f (We .down, Q.down) then7:

rnk ⇐ rnk + ei .size() ∗ |Q|

8:else if f (We .down, ei .down) > f (We .up, Q.up) then9:coutinue

10:

rank (Line 8). After update heap, minRank also updated by

11:

the last rank in heap (Line 9). At last, the algorithm returns

12:heap as the result of group reverse k-ranks query.

13:

else
if ei is a leaf node of RtreeP thenfor each q ∈ Q do
if f (We .down, q) > f (We .up, ei ) then14:

5. Branch and Bound Pruning Method
TPM use R-tree to management the similar products andavoid computing by MBRs. However, there is a limitation

rnk + +
if rnk >= minRank then

15:
16:

return -1

17:

if f (We .up, q) > f (We .up, ei ) then

18:

that TPM evaluated each user preference one by one, and it

19:

will reduce the eﬃciency when encountering a large weight

20:

vectors data set. This limitation inspires us to remove re-21:

dundant computing by grouping similar weighting vectors.

22: if rnk + rnkU p <= minRank then

We propose the branch-and-bound pruning method (BPM).

23:

The Figure 4 shows the filtering property of BPM algorithm.

rnkU p + +else
heapP.enqueue(ei )return 1

24: else
25:

return 0

We denote the R-tree for products and weighting vectors as
RtreeP and RtreeW respectively.
Based on the feature of MBRs in RtreeP and RtreeW ,there also have two facts in the following to pruning unnec-

0, we add all sub MBRs into heapW for next loop (Line 9-

essary MBRs entirely.
F act 3. For a query point set Q, a MBR ep of RtreeP and a MBR We of RtreeW . If f (We .up, ep .up) <f (We .down, Q.down), then for ∀p ∈ ep , ∀w ∈ We , ∀q ∈ Q, it
holds f (w, q) < f (w, p).
F act 4. For a query point set Q, a MBR e of R-treePand a MBR We of RtreeW .

In Algorithm 4, we start from the root of RtreeW andcall Algorithm 3 to check the We (Line 14). If the f lag is

If f (We .down, ep .down) <f (We .up, Q.up), then for ∀p ∈ ep , ∀w ∈ We , ∀q ∈ Q, it holds
f (w, q) > f (w, p).
5. 1 Traverse RtreeP with We

10). If the f lag is 1, it means every weighting vector in We
make Q rank better than minRank, so we call Algorithm 1
to compute the rank of weighting vectors in We and update
the heap and minRank (Line 20-22). When the leaf node of
single weighting vector need to check, we also use Algorithm
1 as same as the way in TPM (Line 8-12). At the end of
the algorithm, we return heap as the result of group reverse
k-ranks query.

6. EXPERIMENT

For a MBR of weighting vectors from R-treeW, denoted as
We , Algorithm 3 helps to check these weighting vectors with

We present the experimental evaluation of the TPM andBPM algorithms for aggregate reverse k-rank. All algorithms
are implemented in C++ and the experiments run on a Mac
with 2.6 GHz Intel Core i7, 16GB RAM, and 500GB flash
storage, OS X Yosemite.
Algorithm 4 branch-and-bound pruning method (BPM)

6. 1 Experiment setup
Data set P . We employed both synthetic data and real

Require: P, W, Q

data for products P . Synthetic data set are uniform (UN)

Ensure: result set heap
1: heap ⇐ ∅and clustered (CL), whose attribute value range is [0, 1). In

2: for each w ∈ {first k element in W } doUN, all attributes are generated independently following a3:heap.insert(w, gRank(w, Q))

uniform distribution. CL is generated by randomly selecting√
M centroids (M = 3 |P |) which following a uniform distri-

4: minRank ⇐ heap’s last rank.
5: heapW.enqueue(RtreeW.root())

bution. Each coordinate is generated following the normal

6: while heapW.isN otEmpty() do
7:8:

We ⇐ heapW.dequeue()

distribution with variance σ = 0.1 and mean equal to the cor-

if We is a leaf node thenresponding coordinate of the centroid. The real data, named9:rnk ⇐ T raRtreeP (P, w, Q, minRank)

HOUSE, contains 201760 6-dimensional tuples, representing

10:

if rnk =| −1 then

American family annual payment on gas, electricity, water,

11:

heap.insert(w, rnk)

heating, insurance, and property tax in 2013. The dataset

12:

minRank ⇐ heap’s last rank.

HOUSE also used into related search [5, 7].

13:

else
f lag ⇐ T raRtreeP + +(P, We , Q, minRank)

14:

if f lag == 0 then15:

heapW.enqueue(all subMBR ⊂ We )16:

if f lag == 1 then18:

= 5, and both P and W are UN data.

for each w ∈ We do

19:

Parameters. Parameters are shown in Table 1 where thedefault values are d = 3, |P |=100K, |W |=100K, k = 10, |Q|

else

17:

Data set W . For data set W , we also have UN, CL data
set that is in a same generating way with data set P .

Metrics. Our metrics is the query execution time required20:

rnk ⇐ T raRtreeP (P, w, Q, minRank)

21:

heap.insert(w, rnk)

22:

minRank ⇐ heap’s last rank.

23: return heapby each algorithm. We do each experiment over 1000 times
and present the average value. The query point set Q is randomly selected from P . To insight the filtering eﬀect of TPM
and BPM, we also observe the computing time of real score
for a point in the leaf node of R-tree.
6. 2 Experiment result
Un data. Figure 5 shows the experimental results on
uniform distribution data sets on varying dimension d (2-5).
Figure 5a shows the CPU time of implemented algorithms,
NAIVE, TPM and BPM. According to the result, we can seethat TPM is much faster than NAIVE algorithm.Notice thaty-axis is in the log. BPM is more than ten times faster thanParameter

Valuesother algorithms and is stable even in 5 dimensions. Fig-

Data dimensionality d

2 ∼ 5, 3

ure 5b shows computing times when the iterator access theDistribution of data set P

UN,CL,RE

leaf node of R-tree. BPM algorithm has less computation inDistribution of data set W

UN,CLa processing means that it prunes more unnecessary points

Data set cardinality of |W | and |P | 100K
Experiment times
Number of clusters

1000
√
√
3
|P |, 3 |W |2 ,σ 2
Variance σW
P

0.12

Table 1: Experimental parameters and default values(inbold) .

and weighting vectors than TPM.
CL data. Figure 6 shows the experimental results on
Cluster data sets on varying dimension d (2-5). Figure 6ashows the CPU time of implemented algorithms while Figure
6b shows computing times. Notice that all tree-base methods (TPM and BPM) take less time finish querying than UN
data because Cluster data is easy to index by R-tree. The
experimental result is same with UN data, TPM is the bestalgorithms and has the least computation.
House data. Figure 7 shows the performance of real datathe eﬃciency of our proposed methods.

TPM
BPM

5000

As future work, we have two objects. The first one isComputing Times

CPU time (ms)

6000

NAIVE
TPM
BPM

100000

4000

10000

to consider another evaluating function. e.g., Evaluating a

3000

group of products by the harmonic average of each one’s rank

2000

1000

1000

2

3
Dimensionality (2-5)

4

5

2

(a) Processing time.

3
4
Dimensionality (2-5)

5consider the approximate solutions for group reverse k-ranks(b) Computing times.

Figure 5: Experimental result on UN data, |P | = 100K, |W |= 100K, |Q| = 5, k = 10, d = 2 ∼ 5.
TPM
BPM

2000

Computing Times

CPU time (ms)

2500

NAIVE
TPM
BPM

100000

1500

10000

1000

500

1000
2

3
Dimensionality (2-5)

4

0

5

2

(a) Processing time .

3
4
Dimensionality (2-5)5(b) Computing times.

Figure 6: Experimental result on CL data, |P | = 100K, |W |= 100K, |Q| = 5, k = 10, d = 2 ∼ 5.
3000

NAIVE
TPM
BPM

Computing Times

CPU time (ms)

NAIVE
TPM

2500

100000

2000

1500

10000

1000

10

20
30
k, number of result (10-50)4050(a) Processing time.

500
10

20

30
k, number of result (10-50)40instead of the sum function in this paper. The second one50(b) Computing times.

Figure 7: Experimental result on HOUSE data, |P | = 100K,|W | = 100K, |Q| = 5, k = 10, d = 2 ∼ 5.

set HOUSE. Figure 7a and 7b is the result of CPU cost andcomputing time respectively. Clearly, both TPM and BPM
faster than NAIVE and TPM is the best one. The BPM
is faster than TPM and has less computation amount thanTPM.

7. CONCLUSION
Reverse rank queries have become important tools in marketing analyzing. However, the related researches of reverse
rank queries are all for one product. We propose group reverse k-ranks queries to apply reverse rank queries into thesituation of several products like the Product Bundling. We
devise two methods, TPM and BPM, to answer group reverse
k-ranks queries eﬃciently. Tree Pruning Method (TPM) isa tree-based pruning method prune unnecessary productswith the help of R-tree. Branch-and-Bound Pruning Method(BPM) uses two R-tree to manage Products and User preferences, the unnecessary Products and User preferences canbe pruned at the same time based on the methodology ofBranch-and-Bound. We do the comparison experiment on
both synthetic data and real data, the experimental verify

queries.
References[1] Chang, Y.-C., Bergman, L. D., Castelli, V., Li, C.-S.,
Lo, M.-L., and Smith, J. R. The onion technique: Indexing for linear optimization queries. In SIGMOD Conference(2000), pp. 391–402.
[2] Dellis, E., and Seeger, B. Eﬃcient computation of reverse skyline queries. In Proceedings of the 33rd International Conference on Very Large Data Bases, University of
Vienna, Austria, September 23-27, 2007 (2007), pp. 291–
302.
[3] Korn, F., and Muthukrishnan, S. Influence sets based onreverse nearest neighbor queries. In Proceedings of the 2000
ACM SIGMOD International Conference on Managementof Data, May 16-18, 2000, Dallas, Texas, USA. (2000),
pp. 201–212.
[4] Lian, X., and Chen, L. Monochromatic and bichromatic
reverse skyline search over uncertain databases. In Proceedings of the ACM SIGMOD International Conference
on Management of Data, SIGMOD 2008, Vancouver, BC,
Canada, June 10-12, 2008 (2008), pp. 213–226.
[5] Vlachou, A., Doulkeridis, C., and Kotidis, Y. Reverse
top-k queries. In ICDE (2010), pp. 365–376.
[6] Vlachou, A., Doulkeridis, C., and Kotidis, Y.
Monochromatic and bichromatic reverse top-k queries.
pp. 1215–1229.
[7] Vlachou, A., Doulkeridis, C., and Kotidis, Y. Branchand-bound algorithm for reverse top-k queries. In SIGMOD
Conference (2013), pp. 481–492.
[8] Vlachou, A., Doulkeridis, C. Monitoring reverse top-k
queries over mobile devices. In MobiDE (2011), pp. 17–24.
[9] Vlachou, A., Doulkeridis, C., and Kotidis, Y. Identifying the most influential data objects with reverse top-k
queries. pp. 364–372.
[10] Yang, S., Cheema, M. A., Lin, X., and Zhang, Y. SLICE:
reviving regions-based pruning for reverse k nearest neighbors queries. In IEEE 30th International Conference on
Data Engineering, Chicago, ICDE 2014, IL, USA, March
31 - April 4, 2014 (2014), pp. 760–771.
[11] Yao, B., Li, F., and Kumar, P. Reverse furthest neighbors in spatial databases. In Proceedings of the 25th International Conference on Data Engineering, ICDE 2009,
March 29 2009 - April 2 2009, Shanghai, China (2009),
pp. 664–675.
[12] Zhang, Z., Jin, C., and Kang, Q. Reverse k-ranks query.
PVLDB 7, 10 (2014), 785–796.