Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Conference or Workshop Paper |
| Scope | Discipline-based scholarship |
| Published in Proceedings | Yes |
| Title | On the efficient construction of multislices from recurrences |
| Organization Unit | |
| Authors |
|
| Presentation Type | paper |
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| Page Range | 42 - 59 |
| Event Title | SSDBM: Scientific and Statistical Database Management, 22nd International Conference, SSDBM 2010, Heidelberg, Germany, June 30 - July 2 |
| Event Type | conference |
| Event Location | Heidelberg |
| Event Start Date | June 30 - 2010 |
| Event End Date | July 2 - 2010 |
| Abstract Text | Recurrences are defined as sets of time instants associated with events and they are present in many application domains, including public transport schedules and personal calendars. Because of their large size, recurrences are rarely stored explicitly, but some form of compact representation is used. Multislices are a compact representation that is well suited for storage in relational databases. A multislice is a set of time slices where each slice employs a hierarchy of time granularities to compactly represent multiple recurrences. In this paper we investigate the construction of multislices from recurrences. We define the compression ratio of a multislice, show that different construction strategies produce multislices with different compression ratios, and prove that the construction of minimal multislices, i.e., multislices with a maximal compression ratio, is an NP-hard problem. We propose a scalable algorithm, termed LMerge, for the construction of multislices from recurrences. Experiments with real-world recurrences from public transport schedules confirm the scalability and usefulness of LMerge: the generated multislices are very close to minimal multislices, achieving an average compression ratio of approx. 99%. A comparison with a baseline algorithm that iteratively merges pairs of mergeable slices shows significant improvements of LMerge over the baseline approach. |
| Digital Object Identifier | 10.1007/978-3-642-13818-8_5 |
| Other Identification Number | 1440; merlin-id:53 |
| PDF File |
Download from ZORA
|
| Export |
BibTeX
EP3 XML (ZORA)
|