|
Published Articles >> Table of Contents >> Abstract
15th International Conference on Scientific and Statistical Database Management
p. 55
Space Constrained Selection Problems for Data Warehouses and Pervasive Computing
Themistoklis Palpanas, University of California, Riverside
Nick Koudas, AT&T Labs-Research
Alberto Mendelzon, University of Toronto
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SSDM.2003.1214954
Send link to a friend
| Abstract |
|
Space constrained optimization problems arise in a multitude of important applications such as data warehouses and pervasive computing. A typical instance of such problems is to select a set of items of interest, subject to a constraint on the total space occupied by these items. Assuming that each item is associated with a benefit, for a suitably defined notion of benefit, one wishes to optimize the total benefit for the selected items. In this paper, we show that in many important applications, one faces variants of this basic problem in which the individual items are sets themselves, and each set is associated with a benefit value. We present instances of such problems in the context of data warehouse management and pervasive computing, derive their complexity, and propose several techniques for solving them. Since there are no known approximation algorithms for these problems, we explore the use of greedy and randomized techniques. We present a detailed performance study of the algorithms, highlighting the efficiency of the proposed solutions and the benefits of each approach. Finally, we present a worst-case analysis of the algorithms, which can be useful in practice for choosing among the alternatives. The solutions proposed in this paper are generic and likely to find applications in many more problems of interest than those mentioned above.
|
 Additional Information
|
Citation:
Themistoklis Palpanas, Nick Koudas, Alberto Mendelzon,
"Space Constrained Selection Problems for Data Warehouses and Pervasive Computing,"
ssdbm,
p. 55,
15th International Conference on Scientific and Statistical Database Management,
2003
|
|
