Please use this identifier to cite or link to this item: https://doi.org/10.1145/2063576.2063791
Title: Evaluation of set-based queries with aggregation constraints
Authors: Tran, Q.T.
Chan, C.-Y. 
Wang, G.
Keywords: aggregation constraints
set-based query
Issue Date: 2011
Source: Tran, Q.T.,Chan, C.-Y.,Wang, G. (2011). Evaluation of set-based queries with aggregation constraints. International Conference on Information and Knowledge Management, Proceedings : 1495-1504. ScholarBank@NUS Repository. https://doi.org/10.1145/2063576.2063791
Abstract: Many applications often require finding a set of items of interest with respect to some aggregation constraints. For example, a tourist might want to find a set of places of interest to visit in a city such that the total expected duration is no more than six hours and the total cost is minimized. We refer to such queries as SAC queries for "set-based with aggregation constraints" queries. The usefulness of SAC queries is evidenced by the many variations of SAC queries that have been studied which differ in the number and types of constraints supported. In this paper, we make two contributions to SAC query evaluation. We first establish the hardness of evaluating SAC queries with multiple count constraints and presented a novel, pseudo-polynomial time algorithm for evaluating a non-trivial fragment of SAC queries with multiple sum constraints and at most one of either count, group-by, or content constraint. We also propose a heuristic approach for evaluating general SAC queries. The effectiveness of our proposed solutions is demonstrated by an experimental performance study. © 2011 ACM.
Source Title: International Conference on Information and Knowledge Management, Proceedings
URI: http://scholarbank.nus.edu.sg/handle/10635/42059
ISBN: 9781450307178
DOI: 10.1145/2063576.2063791
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

7
checked on Dec 11, 2017

Page view(s)

60
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.