Efficient Methods for Aggregate Reverse Rank Queries

Yuyang DONG  Hanxiong CHEN  Kazutaka FURUSE  Hiroyuki KITAGAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.4   pp.1012-1020
Publication Date: 2018/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017DAP0007
Type of Manuscript: Special Section PAPER (Special Section on Data Engineering and Information Management)
Category: 
Keyword: 
similarity search,  aggregate reverse rank queries,  clustering method,  cone+ tree,  

Full Text: PDF(1.8MB)
>>Buy this Article


Summary: 
Given two data sets of user preferences and product attributes in addition to a set of query products, the aggregate reverse rank (ARR) query returns top-k users who regard the given query products as the highest aggregate rank than other users. ARR queries are designed to focus on product bundling in marketing. Manufacturers are mostly willing to bundle several products together for the purpose of maximizing benefits or inventory liquidation. This naturally leads to an increase in data on users and products. Thus, the problem of efficiently processing ARR queries become a big issue. In this paper, we reveal two limitations of the state-of-the-art solution to ARR query; that is, (a) It has poor efficiency when the distribution of the query set is dispersive. (b) It has to process a large portion user data. To address these limitations, we develop a cluster-and-process method and a sophisticated indexing strategy. From the theoretical analysis of the results and experimental comparisons, we conclude that our proposals have superior performance.