DEIM Forum 2017 G1-1

A High-dimensional Solution for Aggregate Reverse Rank Query
Yuyang DONG† , Song WANG† , 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, ††wangsongpower@163.com, †††{chx,furuse,kitagawa}@cs.tsukuba.ac.jp
Abstract In user-product model, there are two types of datasets: Products and users. The Top-rank query inuser-product model can help users to find matching products in their top-rank. On the other hand, the aggregate
reverse rank query (ARR) can find potential users for multiple products (product bundling). ARR is an essential
tool in marketing analysis that helps manufacturers identify the placement of their product bundling. Unfortunately,
the previous solution for the ARR query is a tree-based method. Due to the curse of dimensionality, the tree-based
method makes ARR query don’t have good performance in high-dimensional data. To address this limitation, we
use a high-dimensional technical named Grid-index, and propose a Grid-index aggregate (GIA) solution to deal with
the ARR query in high-dimensional data. Our experimental results show that the GIA has better performance thanthe existing tree-based algorithms.
Key words Aggregate Reverse Rank Queries, Grid-index, High dimensional index

1. INTRODUCTION
Top-k queries is a user-view model that obtain the best k
products for a user preference. On the other hand, aggregate reverse rank query (ARR) [3] is a manufacturer-viewmodel that discovers the potential consumers by retrieving
the most appropriate user preferences for multiple products.
ARR can help manufacturers with the market analysis with
their product bundling.
Figure 1 shows the example of aggregate reverse ranks
query when k = 1. There are 5 diﬀerent books (p1 ∼ p5 )with two attributes ”price” and the ”rating” in Table (b).
Two users preferences (Tom and Jerry) are shown in Table(a); these preferences consist of the weights for each attributeof a book. The score of a book based on a user preference isthe result of the inner product between the book attributes
vector and user preference vector. All scores are ranked with

Figure 1: Users data, books data and ARR-1 results.

scores and we think the minimum scores will be preferable.
The ranking results of books by users are shown in the last

1. 1 Motivation

cells Table (a). Table (c) shows that the bookshop oﬀers two

The state-of-the-art solution for ARR is the double treekinds of product bundling, to bundle {p1 , p2 } and {p4 , p5 }.

method (DTM). It is a tree-based methodology, which uses

ARR evaluates aggregate rank with the sum of each book, so

an R-tree to indexes and prunes the data through a branch-

the bundle of {p1 , p2 } ranked as 3 + 2 = 5 based on Tom’s

and-bound method. However, the R-tree or any other spatial

preference. For {p1 , p2 }, Tom thinks the aggregate rank is

index has a shortcoming: When processing high-dimensional5, and Jerry thinks it is the 6th. ARR-1 returns Tom as adata sets, the performance declines to close to NAIVE.

result since he has more possibility than Jerry to buy thebundling.

We do an experiment to observe the consuming time of processing ARR. Figure 2 shows the comparison of performancebor. [11] classifies RKNN (reverse k nearest neighbor) into
bichromatic and monochromatic queries. RKNN may look

CPU time(s)similar with reverse rank queries that obtaining users that
140
120
100
80
60
40
20
0

NAIVE
DTM

prefer a given product as favorite, but they are completely
diﬀerent. RKNN evaluates relative Lp distance in one Euclid space with two points. However, reverse rank queries
focus on the absolute ranking among all objects, and scoresare found by inner product with two diﬀerent vectors from

2

4

6

8

10 12 14 16 18 20d

diﬀerent data space. The reverse skyline query uses the advantages of products to find the potential customers based

Figure 2: DTM vs NAIVE.

on the dominance of the competitor’s products [2, 5].

3. PRELIMINARIES
between tree-based algorithm (DTM) and the NAIVE. According to the results, DTM may not outperform the NAIVE

3. 1 Definitions

method when processing ARR in high dimensions.

We first introduce the assumption of the product database,

However, both the product’s attributes and the user’s pref-

preference database and the score function, which is same

erences are likely to be high-dimensional. For example, cellwith the related research [3, 6, 8, 13]. Assume that there isphones consumers care about many features, such as price,a product data set P and a preference data set W . Eachprocessor, storage, size, battery life, camera, etc. Therefore,p ∈ P is a d-dimensional vector that contains d non-negative

processing ARR with a high-dimensional data set is an im-

scoring attributes.

portant requirement.

p = (p[1], p[2], ..., p[d]), where p[i] is the ith attribute value

p can also be represented as a pointof p. i.e., the value on ith dimension of p. The preference

2. RELATED WORK
For top-k queries. The Onion technique [1] precomputes
and stores the convex hulls of data points in layers like anonion. The evaluation of a linear top-k query is accomplishedw ∈ W is a d-dimensional weighting vector, and w[i] is a∑
non-negative weight that evaluates p[i], where di=1 w[i] = 1.
The score is defined as the inner product of p and w, which is∑expressed by f (w, p) = di=1 w[i] · p[i]. A query set Q, is set

by starting from the outmost and processing these layers in-of points in the space of product P (but it is not necessaryward.

that Q ⊂ P ). All values are normalized to the range (0,1].

Reverse top-k queries [6, 7, 9, 10] have been proposed for

The rank of a q on a specific w is defined as the number

evaluating the impact of a potential product in the market,

of points which have smaller scores than q:

based on preferences of users that treat this product as one of［Definition 1］ (rank(w, q)). Given a product dataset P , atheir top-k products. There are also various applications ofreverse top-k queries [9, 10]. However, to answer the reverse
query for some less popular objects, [13] proposed reverse k-preference w, and a query q, the rank of q according to w
is rank(w, q) = |S|, where S ⊂=P and ∀pi ∈ S, f (w, pi ) <f (w, q) ∧ ∀pj ∈ (P − S), f (w, pj ) >= f (w, q).

ranks queries, which finds for a given object the top-k user

To evaluate the rank of a query set Q, related work [3]preferences whose rank for the object is highest among all

gave a definition that the aggregate rank of Q is the sum ofusers. The most relevant work is our previous work named

each rank of q ∈ Q:

aggregate reverse rank query (ARR) [3]. It finds the top-k
users for multiple query products to deal with the application［Definition 1］（rank） (ARank(w, Q)). The aggregate rank∑of Q according to a w isARank(w, Q) = qi ∈Q rank(w, qi ).

The definition of aggregate reverse rank query [3] is:of product bundling.
Some other related researches on the reverse query are［Definition 2］ (aggregate reverse rank query, ARR). Givenlisted in the following. The essential diﬀerence is that they

datasets P and W , positive integer k, and query product set

two data sets. Given a data point and aim at finding theQ, ARR query returns the set S, S ⊂=W , |S| = k, such that∀wi ∈ S, ∀wj ∈ (W − S), ARank(wi , Q) <= ARank(wj , Q)

queries that have this data point in their result set. Con-holds.

treat one data set, while in reverse rank queries, there are

trast with the nearest neighbor search, [4] proposed a reverse

3. 2 Tree-based Method for ARR

nearest neighbor (RNN) queries.

Opposite to RNN, [12]The state-of-the-art solution for ARR is double tree

proposed reverse furthest neighbor (RFN) queries to findmethod (DTM) [3]. DTM uses two R-trees to index data

the points who deem query point as their furthest neigh-P and data W respectively, then filters unnecessary datawith the branch-and-bound methodology. The node of R-

tree (minimum bounding rectangle, MBR) can help to com-the leaf node. The above situation always happens in high-pare multiple p’s and w’s at one time by using the MBRs’

dimensional space.

bounds. As shown in Figure 3, the left is the space of data

4. 2 Small Filter SpaceW , and the right is the space of data P . An R-tree node

The reason of overlapped nodes comes from the tree-ew groups w1 , w2 , w3 and it’s upper bound ew .up and lower

structure itself. However, another reason for the bad perfor-

bound ew .down form the search space (gray area) with Q.

mance is because of the filtering property declines in high-DTM only need do computing of the data in the sandwicheddimensional space.

space, the nodes like e2 , e3 and e5 will be pruned directly.

As Figure 4 shows, the shape of the gray area can be a
prism or a tetra. The filtering property can be estimated bymeasuring the volume of :V ol = V olT etraX ·V olP rismX +V olT etraY ·V olP rismY (1)To give an analytical result, we assume that the upper filtering volume are equal to lower filtering volume (V olT etraX =V olT etraY ), hence:
V ol = 2 · V olT etra · V olP rism

Figure 3: Tree-based method of ARR query.

(2)

the volume of g-dimensional hyper-tetra is:1 ∏1( xi ) = (1 − γ)gg! i=1g!
g

V olT etra =4. Why tree-based method performed
ARR not good with high-dimensionaldata?
In this section, we demonstrate why the tree-based method
has poor performance when processing ARR with highdimensional data. There are two reasons: Overlapped nodes
and small filter space.

(3)

the volume of the hyper-prism is:
Si =

1
1−γ
1
(xi + x′i ) · H <=( 2 )<= 2
2(4)

Recall that the length of the range is 1, so a 3 dimensional
prism in the figure, the volume is:
V olP rism3d =4. 1 Overlapped Nodes√
1
1(S1 + S2 + S1 S2 ) · H <
= 2
3

(5)

This result holds for higher dimensional prisms. The maximum volume of the filtered space is as following, whereg = d/2 and means there are same numbers of tetra or prism.
V olmax = 2 ·11
1(1 − γ)g · = (1 − γ)g
g!
2
g!

(6)

According to above Equation 6, the volume will be verysmall in high-dimensional cases, which proved that the filterable space also becomes small.

5. Proposed Grid-Index
Figure 4: Overlapped Nodes.

As we know that the most cost part in processing ARR
the linear scan is the computing of the scores (inner prod-

It is well known that R-tree groups similar points as aucts) for comparison. A d dimensional inner product needs

node with their MBR, however, the nodes will be overlappedd times multiplications and d times additions, and the mul-with each other when indexing high-dimensional data. Due

tiplications cost much more than additions. To enhance theto the high-dimensional case cannot be plotted, we use a 2-

eﬃciency of the linear scan, we introduce the concept of Grid-

dimensional example to demonstrate the overlapped nodes.

index which can help to avoid most multiplications.

In Figure 4, an R-tree indexes data points into five nodes

5. 1 Build Grid-index

e1 to e5 . Unfortunately, all nodes all overlapped each otherWe first partition the value range of data p and w, no-and intersected with the borderlines of search space (dashedtice that all attributes of p ∈ W should belong to the sameline). This time, DTM can prune nothing while doing a

range, so do all w ∈ W . In the example of Figure 5, we par-traversal of R-tree and have to compute all data points intition the value range into 4 equal intervals. For the givenp = (0.62, 0.15, 0.73), p[1] = 0.62 falls into the third parU [fw (p)] =tition [0.5, 0.75]. p[2] = 0.15, falls into the first partition,and p[3] is in the third partition. We will store the partition
numbers as an approximate vector, denoted as pa and wa , sod∑Grid[pa [i] + 1][wa [i] + 1]

(9)

i=1

Obviously, it costs only d times additions if the relation ofscores can be confirmed by above upper or lower bounds.

pa = (2, 0, 2) and wa = (0, 2, 1).
Algorithm 1 GIA
Input: PA , WA , P, W, Q, k
Output:1: buﬀer ← ∅2: kthRank ← ∞3: for each wa ∈ WA do

Figure 5: 4 partitions, allocating real values into approxi-

4:

Candidate ← ∅mate intervals and getting the approximate vector pa and5:Counter ← Domin.size

wa .

6:

Compute each f (w, q) of q ∈ Q and store in Qscores

7:

Sort Qscores in descending

8:

for each pa ∈ (PA / Domin ) do
for i to |Q| do

9:10:

if U [f (w, p)] <= Qscores [i] then

11:

Counter ← Counter + |Q| - i

12:

if counter == kthRank thenbreak to check next wa

13:

if L[f (w, p)] <= Qscores [i] <= U [f (w, p)] then

14:

Candidate ← Candidate ∪ {p}15:

if p dominates Q then16:

Domin ← Domin ∪ {p}17:

Figure 6: Mapping pairwise (p[i], w[i]) onto the 4 × 4 Grids.

Then we combined the range p and range w to form thegrids. The purpose is that we want to map an arbitrary

Refine Candidate and update Counter.
19: if Counter >= kthRank then
18:

20:

continue to next wa

21: else
22:

buﬀer.insert(w, Counter)pair of (p[i], w[i]) into a certain grid, since the inner product23:

kthRank ← the kth rank in buﬀer.

f (w, p) is the sum of pairwise multiplications of (p[i], w[i]).

24: return buﬀer

Figure 6 shows the 4 × 4 grids and the mapping (p[i], w[i])onto grids. It is important to know that the same value
range makes these grids can be re-used for mapping all pairs(p[i], w[i]), i.e., No matter how much dimensions the data
has, only one Grid is suﬃcient.
Suppose that both the value range of p and w are divided into n partitions, and the step values of partition are
represented by a (n+1)-element vector αp for points andαw for weights. In the example of Figure 5, αp = αw =(0, 0.25, 0.5, 0.75, 1). The Grid-index is a 2-dimensional array and stores the multiplication results of all step values:
Grid[i][j] = αp [i] · αw [j], i, j ∈ [0, n](7)

5. 3 Grid-index Aggregate Reverse Rank Algorithm (GIA)
Algorithm 1 describes the proposed method GIA. It is adouble looping framework that scans each pa ∈ PA for eachwa ∈ WA , and look up the Grid-index to avoiding computing. For each wa , we use a Counter to record the aggregate
rank ARank(w, Q) (Line 4). In the inner loop(Line 8-17),
the Counter will be update when the f (w, q) is greater thana current point p. We carry out an optimization that calculates and sorts each q’s score in advance (Line 6-7). We use
Grid-index to obtain the U [f (w, p)], if U [f (w, p)] is smaller
than a q’s score, the Counter will increase by the remained

5. 2 Upper and Lower Bounds of Score f (w, p)

number of q and we don’t need to compare more (Line 10-11).

We pre-calculate the approximate vectors set PA and WA

If the rank relationship can not decide by the upper and lower

For a pa ∈ PA and afrom Grid-index, we add these kind of p into Candidate (Linewa ∈ WA , we use the Grid-index to obtain the upper bound

14-15), and we will refine the Candidate after scanning all

U (w, p)], and lower bound L(w, p):

pa if it is necessary (Line 18). Another optimization is thatfor data P and W , respectively.

L[fw (p)] =

d
∑
i=1

Grid[pa [i]][wa [i]](8)“global dominating point”, a p is a global dominating point
if all p[i] <= q[i] where i = 1, 2, ..., d, and we keep them intoValues

Data dimensionality d3 ∼ 20, 3Distribution of data set P

UN,CL,RE

Distribution of data set W

UN,CLData set cardinality of |W | and |P | 100K
Experiment times
Number of clusters

1000
√
√
3
|P |, 3 |W |Table 1: Experimental parameters and default values(inCPU time(s)Parameter

100
90
80
70
60
50
40
30
20
10

bold) .

SCAN
DTM
GIA

2

4

6

8

10 12 14 16 18 20da set Domin (Line 16-17). We will skip checking the global

Figure 7: Experimental result on UN data, |P | = 100K, |W |dominating points (Line 8) instead of initializing Counter= 100K, |Q| = 10, k = 10, d = 2 ∼ 20.

by the size of Domin (Line 5). A k-element buﬀer is used
to keep the top-k w’s and their aggregate ranks for Q as theresult of ARR query (Line 1, 22). The algorithm will break60

kthRank, which is initialize as ∞ (Line 2) and update by50

the rank value of the last element in buﬀer (Line 23).

6. EXPERIMENTCPU time(s)and start to check the next wa when the Counter reaches

SCAN
DTM
GIA

40
30
20
10

We present the experimental evaluation of the SCAN,

1020

DTM and GIA algorithms for aggregate reverse k-rank.
SCAN has the same strategy as that of GIA; the only difference is that SCAN computes the scores while GIA uses
Grid-index. All algorithms are implemented in C++ and

30

40

50

k

Figure 8: Experimental result on UN data, |P | = 100K, |W |= 100K, |Q| = 10, d = 6, k = 10 ∼ 50.

the experiments run on a Mac with 2.6 GHz Intel Core i7,
16GB RAM, and 500GB flash storage, OS X Yosemite.
Data set P . We employed both synthetic data and real
data for products P . Synthetic data set are uniform (UN)and clustered (CL), whose attribute value range is [0, 1). In
UN, all attributes are generated independently following a

CPU time(s)6. 1 Experiment setup

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

100
90
80
70
60
50
40
30
20
10

SCAN
DTM
GIA

5

10

15

20

25

|Q|

bution. Each coordinate is generated following the normal
distribution with variance σ = 0.1 and mean equal to the cor-Figure 9: Experimental result on UN data, |P | = 100K, |W |responding coordinate of the centroid. The real data, named= 100K, k = 10, d = 6, |Q| = 5 ∼ 25.

HOUSE, contains 201760 6-dimensional tuples, representing
American family annual payment on gas, electricity, water,
heating, insurance, and property tax in 2013. The dataset
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 .
Parameters. Parameters are shown in Table 1 where thedefault values are d = 6, |P |=100K, |W |=100K, k = 10, |Q|= 10, and both P and W are UN data.
Metrics. Our metrics is the query execution time requiredby each algorithm. We do each experiment over 1000 times
and present the average value. The query point set Q is
randomly selected from P .

CPU time(s)HOUSE also used into related search [6, 8].

180
160
140
120
100
80
60
40
20

SCAN
DTM
GIA

2

4

6

8

10 12 14 16 18 20dFigure 10: Experimental result on CL data, |P | = 100K, |W |= 100K, |Q| = 10, k = 10, d = 2 ∼ 20.

CPU time(s)References

50
45
40
35
30
25
20
15
10

SCAN
DTM
GIA

10

20

30

40

50

k

Figure 11: Experimental result on HOUSE data, |P | = 100K,|W | = 100K, |Q| = 10, d = 6, k = 10 ∼ 50.

6. 2 Experiment result
Un data. Figure 7 shows the experimental results on uniform distribution data sets on varying dimension d (from 3
to 20). According to the result, we can see that both SCAN
and GIA becomes faster than DTM algorithm after six dimensions. GIA always faster than SCAN at least two times
because it use Grid-index to filter. Figure 8 and Figure 9
show the CPU time of varying k (from 10 to 50) and varying|Q| (from 5 to 25) respectively. All algorithm are insensitive to k and Q since k ≪ |P |, k ≪ |W | and |Q| ≪ |P |,|Q| ≪ |W |.
CL data. Figure 10 shows the experimental results on
Cluster data sets on varying dimension d (from 3-20). Notice that DTM take less time to finish querying than UN
data because Cluster data is easy to index by R-tree. But
GIA still becomes outperform DTM after eight dimensions.
HOUSE data. Figure 11 shows the performance of real
data set HOUSE with diﬀerent k (from 10 to 50). Clearly,
GIA is faster than SCAN and DTM.

7. CONCLUSION
In marketing analysis, aggregate reverse rank query can beused to help manufacturers recognize their consumer base bymatching their bundled products with user preferences. The
state-of-the-art solution DTM is a tree-based algorithms, andare not designed to deal with high-dimensional data. In thispaper, we proposed the Grid-index and the GIA algorithm
to overcome the cost of high-dimensional computing. Experimental results confirmed the eﬃciency of the proposed
algorithm when compared to the tree-based algorithms especially in high-dimensional cases.
In future work, we will focus on the optimization when theuser preferences data w ∈ W has many zero entry, i.e., when
W is sparse. Since in practice, a user is normally interested
in a few attributes of the products.

[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] Dong, Y., Chen, H., Furuse, K., and Kitagawa, H. Aggregate reverse rank queries. In Database and Expert Systems Applications - 27th International Conference, DEXA
2016, Porto, Portugal, September 5-8, 2016, Proceedings,
Part II (2016), pp. 87–101.
[4] 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.
[5] 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.
[6] Vlachou, A., Doulkeridis, C., Kotidis, Y. Reverse top-k
queries. In ICDE (2010), pp. 365–376.
[7] Vlachou, A., Doulkeridis, C., Kotidis, Y. Monochromatic and bichromatic reverse top-k queries. pp. 1215–1229.
[8] Vlachou, A., Doulkeridis, C., and Kotidis, Y. Branchand-bound algorithm for reverse top-k queries. In SIGMOD
Conference (2013), pp. 481–492.
[9] Vlachou, A., Doulkeridis, C. Monitoring reverse top-k
queries over mobile devices. In MobiDE (2011), pp. 17–24.
[10] Vlachou, A., Doulkeridis, C., and Kotidis, Y. Identifying the most influential data objects with reverse top-k
queries. pp. 364–372.
[11] 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.
[12] 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.
[13] Zhang, Z., Jin, C., and Kang, Q. Reverse k-ranks query.
PVLDB 7, 10 (2014), 785–796.