Region-based Online Promotion Analysis

This paper addresses a fundamental and challenging problem with broad applications: efficient processing of region-based promotion queries, i.e., to discover the top-k most interesting regions for effective promotion of an object (e.g., a product or a person) given by user, where a region is defined over continuous ranged dimensions. In our problem context, the object can be promoted in a region when it is top-ranked in it. Such type of promotion queries involves an exponentially large search space and expensive aggregation operations. For efficient query processing, we study a fresh, principled framework called region-based promotion cube (RepCube). Grounded on a solid cost analysis, we first develop a partial materialization strategy to yield the provably maximum online pruning power given a storage budget. Then, cell relaxation is performed to further reduce the storage space while ensuring the effectiveness of pruning using a given bound. Extensive experiments conducted on large data sets show that our proposed method is highly practical, and its efficiency is one to two orders of magnitude higher than baseline solutions.
Date: March 22, 2010
Book Title: Proceedings of the 13th International Conference on Extending Database Technology (EDBT 2010)
Type: InProceedings
Downloads: 308

Has 1 soft copy

remote link


  author = "Tianyi Wu and Yizhou Sun and Cuiping Li and Jiawei Han",
  title = "{Region-based Online Promotion Analysis}",
  month = "March",
  year = "2010",
  booktitle = "Proceedings of the 13th International Conference on Extending Database Technology (EDBT 2010)",