Paper 1

Bound-and-Filter Framework for Aggregate Reverse Rank Queries

Authors: Yuyang Dong, Hanxiong Chen, Kazutaka Furuse, Hiroyuki Kitagawa

Volume 38 (2018)

Abstract

Finding top-rank products based on a given user’s preference is a user-view rank model that helps users to find their desired products. Recently, another query processing problem named reverse rank query has attracted significant research interest. The reverse rank query is a manufacturer-view model and can find users based on a given product. It can help to target potential users or find the placement for a specific product in marketing analysis.

Unfortunately, previous reverse rank queries only consider one product, and they cannot identify the users for product bundling, which is known as a common sales strategy. To address the limitation, we propose a new query named aggregate reverse rank query to find matching users for a set of products. Three different aggregate rank functions (SUM, MIN, MAX) are proposed to evaluate a given product bundling in a variety of ways and target different users. To resolve these queries more efficiently, we propose a novel and sophisticated bound-and-filter framework. In the bound phase, two points are found to bound the query set for excluding candidates outside the bounds. In the filter phase, two tree-based methods are implemented with the bounds; they are the tree pruning method (TPM) and the double-tree method (DTM). The theoretical analysis and experimental results demonstrate the efficacy of the proposed methods.

Keywords: Similarity search, Aggregate reverse rank queries, Bound-and-filter, Tree-based method.