Please use this identifier to cite or link to this item:
|Title:||Evaluation of set-based queries with aggregation constraints||Authors:||Tran, Q.T.
|Issue Date:||2011||Citation:||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.
checked on Nov 26, 2021
checked on Dec 2, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.