More Web Proxy on the site http://driver.im/

research-article

Timeline index: a unified data structure for processing queries on temporal data in SAP HANA

Authors:

Martin Kaufmann,

Amin Amiri Manjili,

Panagiotis Vagenas,

Peter Michael Fischer,

Donald Kossmann,

Norman MayAuthors Info & Claims

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

Pages 1173 - 1184

https://doi.org/10.1145/2463676.2465293

Published: 22 June 2013 Publication History

Abstract

Managing temporal data is becoming increasingly important for many applications. Several database systems already support the time dimension, but provide only few temporal operators, which also often exhibit poor performance characteristics. On the academic side, a large number of algorithms and data structures have been proposed, but they often address a subset of these temporal operators only. In this paper, we develop the Timeline Index as a novel, unified data structure that efficiently supports temporal operators such as temporal aggregation, time travel, and temporal joins. As the Timeline Index is independent of the physical order of the data, it provides flexibility in physical design; e.g., it supports any kind of compression scheme, which is crucial for main memory column stores. Our experiments show that the Timeline Index has predictable performance and beats state-of-the-art approaches significantly, sometimes by orders of magnitude.

References

[1]

G. Adelson-Velskii and E. M. Landis. An Algorithm for the Organization of Information. In Proceedings of the USSR Academy of Sciences, 1962.

[2]

M. Al-Kateb et al. Adding a Temporal Dimension to the TPC-H Benchmark. In TPCTC Workshop, 2012.

[3]

B. Becker et al. An Asymptotically Optimal Multiversion B-Tree. VLDB J., 5(4), 1996.

Digital Library

[4]

M. H. Böhlen, J. Gamper, and C. S. Jensen. Multi-dimensional Aggregation for Temporal Data. In EDBT, 2006.

Digital Library

[5]

S. Börzsönyi, D. Kossmann, and K. Stocker. The Skyline Operator. In ICDE, 2001.

Digital Library

[6]

R. Elmasri, G. T. J. Wuu, and Y.-J. Kim. The Time Index: An Access Structure for Temporal Data. In VLDB, 1990.

Digital Library

[7]

F. Färber et al. The SAP HANA Database -- An Architecture Overview. IEEE Data Eng. Bull., 35(1), 2012.

[8]

F. Funke et al. Metrics for Measuring the Performance of the Mixed Workload CH-benCHmark. In TPCTC Workshop, 2011.

Digital Library

[9]

D. Gao, C. S. Jensen, R. T. Snodgrass, and M. D. Soo. Join Operations in Temporal Databases. VLDB J., 14(1), 2005.

Digital Library

[10]

M. Kaufmann, D. Kossmann, N. May, and A. Tonder. Benchmarking Databases with History Support. Technical report, SAP AG, 2013.

[11]

M. Kaufmann, D. Kossmann, N. May, and A. Tonder. SQL Extension for History Tables:. Technical report, SAP AG, 2013.

[12]

N. Kline and R. T. Snodgrass. Computing Temporal Aggregates. In ICDE, 1995.

Digital Library

[13]

D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., 1998.

Digital Library

[14]

K. G. Kulkarni and J.-E. Michels. Temporal Features in SQL: 2011. SIGMOD Record, 41(3), 2012.

Digital Library

[15]

D. B. Lomet and B. Salzberg. Access Methods for Multiversion Data. In SIGMOD, 1989.

Digital Library

[16]

D. Lomet et al. Transaction Time Support Inside a Database Engine. In ICDE, 2006.

Digital Library

[17]

P. Muth, P. E. O'Neil, A. Pick, and G. Weikum. The LHAM Log-Structured History Data Access Method. VLDB J., 8(3--4), 2000.

Digital Library

[18]

R. Rajamani. Oracle Total Recall / Flashback Data Archive. Technical report, Oracle, 2007.

[19]

S. Ramaswamy. Efficient Indexing for Constraint and Temporal Databases. In ICDT, pages 419--431, 1997.

Digital Library

[20]

B. Salzberg and V. J. Tsotras. Comparison of Access Methods for Time-Evolving Data. ACM Comput. Surv., 31(2), June 1999.

Digital Library

[21]

C. M. Saracco et al. A Matter of Time: Temporal Data Management in DB2 10. Technical report, IBM, 2012.

[22]

R. T. Snodgrass et al. TSQL2 Language Specification. SIGMOD Record, 23(1), 1994.

Digital Library

[23]

M. D. Soo, R. T. Snodgrass, and C. S. Jensen. Efficient Evaluation of the Valid-Time Natural Join. In ICDE, 1994.

Digital Library

[24]

I. Stoica et al. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In SIGCOMM, 2001.

Digital Library

[25]

M. Stonebraker. The Design of the POSTGRES Storage System. In VLDB, 1987.

Digital Library

[26]

J. Yang and J. Widom. Incremental Computation and Maintenance of Temporal Aggregates. In VLDB, 2003.

Digital Library

[27]

D. Zhang, V. J. Tsotras, and B. Seeger. Efficient Temporal Join Processing Using Indices. In ICDE, 2002.

Digital Library

[28]

D. Zhang et al. On Computing Temporal Aggregates with Range Predicates. ACM Trans. Database Syst., 33(2), 2008.

Digital Library

Cited By

Ceccarello MDignös AGamper JKhnaisser C(2025)Indexing temporal relations for range-duration queriesDistributed and Parallel Databases10.1007/s10619-024-07452-643:1Online publication date: 9-Jan-2025
https://doi.org/10.1007/s10619-024-07452-6
Christodoulou GBouros PMamoulis N(2024)LIT: Lightning-fast In-memory Temporal IndexingProceedings of the ACM on Management of Data10.1145/36392752:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639275
Amagata D(2024)Independent Range Sampling on Interval Data2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00041(449-461)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00041
Show More Cited By

Index Terms

Timeline index: a unified data structure for processing queries on temporal data in SAP HANA
1. Information systems
  1. Data management systems
    1. Database management system engines
  2. Information retrieval
    1. Document representation

Recommendations

SHB+-Tree: A Segmentation Hybrid Index Structure for Temporal Data
ICA3PP 2015: Proceedings, Part II, of the 15th International Conference on Algorithms and Architectures for Parallel Processing - Volume 9529

Temporal index provide an important way to accelerate query performance in temporal database. However, the current temporal index can not support the variety of queries very well, and it is hard to take account of both the efficiency of query execution ...
The Chunk-Locality Index: An Efficient Query Method for Climate Datasets
IPDPSW '12: Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum

Geoscientists have a constant need to query into large-scale multidimensional array-based datasets. The most efficient way to accelerate queries is indexing. We focus on the climate datasets and propose a novel and efficient indexing method called the ...
GCH-OSQL: a temporally-oriented object-oriented query language based on a three-valued logic
TIME '97: Proceedings of the 4th International Workshop on Temporal Representation and Reasoning (TIME '97)

The need of managing temporal information given at different levels of granularity and indeterminacy is common to many application areas. Between them, we focus on the management of clinical data. Different time granularities are also needed in querying ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

June 2013

1322 pages

ISBN:9781450320375

DOI:10.1145/2463676

General Chairs:
Kenneth Ross
Columbia University
,
Divesh Srivastava
AT&T Research
,
Program Chair:
Dimitris Papadias
HKUST

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York, USA

Acceptance Rates

SIGMOD '13 Paper Acceptance Rate 76 of 372 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
1,042
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)8

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ceccarello MDignös AGamper JKhnaisser C(2025)Indexing temporal relations for range-duration queriesDistributed and Parallel Databases10.1007/s10619-024-07452-643:1Online publication date: 9-Jan-2025
https://doi.org/10.1007/s10619-024-07452-6
Christodoulou GBouros PMamoulis N(2024)LIT: Lightning-fast In-memory Temporal IndexingProceedings of the ACM on Management of Data10.1145/36392752:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639275
Amagata D(2024)Independent Range Sampling on Interval Data2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00041(449-461)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00041
Reppas IMirabi MFathi LBinnig CDignös AGamper J(2024)Parallel Processing of Temporal Anti-Joins in MemoryDatabase Systems for Advanced Applications10.1007/978-981-97-5552-3_6(86-102)Online publication date: 1-Oct-2024
https://doi.org/10.1007/978-981-97-5552-3_6
Xu JWong R(2023)Efficiently Answering Top-k Window Aggregate Queries: Calculating Coverage Number Sequences over Hierarchical Structures2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00104(1300-1312)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00104
Christodoulou GBouros PMamoulis N(2023)HINT: a hierarchical interval index for Allen relationshipsThe VLDB Journal10.1007/s00778-023-00798-w33:1(73-100)Online publication date: 1-Jun-2023
https://doi.org/10.1007/s00778-023-00798-w
Pereira AAlmeida JLopes ROliveira J(2022)Visualising Time-evolving Semantic Biomedical Data2022 IEEE 35th International Symposium on Computer-Based Medical Systems (CBMS)10.1109/CBMS55023.2022.00053(264-269)Online publication date: Jul-2022
https://doi.org/10.1109/CBMS55023.2022.00053
Khnaisser CHamrouni HBlumenthal DDignös AGamper J(2022)Querying Temporal Anomalies in Healthcare Information Systems and BeyondAdvances in Databases and Information Systems10.1007/978-3-031-15740-0_16(209-222)Online publication date: 29-Aug-2022
https://doi.org/10.1007/978-3-031-15740-0_16
Ataei PKhan FWalkingshaw ETilevich EDe Roover C(2021)A variational database management systemProceedings of the 20th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3486609.3487197(29-42)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1145/3486609.3487197
Körber MGlombiewski NSeeger BLi GLi ZIdreos SSrivastava D(2021)Index-Accelerated Pattern Matching in Event StoresProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457245(1023-1036)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457245
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents