Efficient Maintenance of Ephemeral Data

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

Abstract

Motivated by the increasing prominence of loosely-coupled systems, such as mobile and sensor networks, the characteristics of which include intermittent connectivity and volatile data, we study the tagging of data with so-called expiration times. More specifically, when data are inserted into a database, they may be stamped with time values indicating when they expire, i.e., when they are regarded as stale or invalid and thus are no longer considered part of the database. In a number of applications, expiration times are known and can be assigned at insertion time. We present data structures and algorithms for online management of data stamped with expiration times. The algorithms are based on fully functional treaps, which are a combination of binary search trees with respect to a primary attribute and heaps with respect to a secondary attribute. The primary attribute implements primary keys, and the secondary attribute stores expiration times in a minimum heap, thus keeping a priority queue of tuples to expire. A detailed and comprehensive experimental study demonstrates the well-behavedness and scalability of the approach as well as its efficiency with respect to a number of competitors.
Original languageEnglish
Title of host publicationProceedings of the Eleventh International Conference on Database Systems for Advanced Applications
PublisherSpringer
Publication date2006
Pages141-155
ISBN (Print)3540333371
Publication statusPublished - 2006
EventInternational Conference on Database Systems for Advanced Applications - Singapore, Singapore
Duration: 12 Apr 200615 Apr 2006
Conference number: 11

Conference

ConferenceInternational Conference on Database Systems for Advanced Applications
Number11
CountrySingapore
CitySingapore
Period12/04/200615/04/2006
SeriesLecture Notes in Computer Science
Number3882
ISSN0302-9743

Fingerprint

tagging
connectivity
experimental study
sensor
attribute

Cite this

Schmidt, A., & Jensen, C. S. (2006). Efficient Maintenance of Ephemeral Data. In Proceedings of the Eleventh International Conference on Database Systems for Advanced Applications (pp. 141-155). Springer. Lecture Notes in Computer Science, No. 3882
Schmidt, Albrecht ; Jensen, Christian Søndergaard. / Efficient Maintenance of Ephemeral Data. Proceedings of the Eleventh International Conference on Database Systems for Advanced Applications. Springer, 2006. pp. 141-155 (Lecture Notes in Computer Science; No. 3882).
@inproceedings{05d81e409fdd11db8ed6000ea68e967b,
title = "Efficient Maintenance of Ephemeral Data",
abstract = "Motivated by the increasing prominence of loosely-coupled systems, such as mobile and sensor networks, the characteristics of which include intermittent connectivity and volatile data, we study the tagging of data with so-called expiration times. More specifically, when data are inserted into a database, they may be stamped with time values indicating when they expire, i.e., when they are regarded as stale or invalid and thus are no longer considered part of the database. In a number of applications, expiration times are known and can be assigned at insertion time. We present data structures and algorithms for online management of data stamped with expiration times. The algorithms are based on fully functional treaps, which are a combination of binary search trees with respect to a primary attribute and heaps with respect to a secondary attribute. The primary attribute implements primary keys, and the secondary attribute stores expiration times in a minimum heap, thus keeping a priority queue of tuples to expire. A detailed and comprehensive experimental study demonstrates the well-behavedness and scalability of the approach as well as its efficiency with respect to a number of competitors.",
author = "Albrecht Schmidt and Jensen, {Christian S{\o}ndergaard}",
year = "2006",
language = "English",
isbn = "3540333371",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "3882",
pages = "141--155",
booktitle = "Proceedings of the Eleventh International Conference on Database Systems for Advanced Applications",
address = "Germany",

}

Schmidt, A & Jensen, CS 2006, Efficient Maintenance of Ephemeral Data. in Proceedings of the Eleventh International Conference on Database Systems for Advanced Applications. Springer, Lecture Notes in Computer Science, no. 3882, pp. 141-155, International Conference on Database Systems for Advanced Applications, Singapore, Singapore, 12/04/2006.

Efficient Maintenance of Ephemeral Data. / Schmidt, Albrecht; Jensen, Christian Søndergaard.

Proceedings of the Eleventh International Conference on Database Systems for Advanced Applications. Springer, 2006. p. 141-155 (Lecture Notes in Computer Science; No. 3882).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Efficient Maintenance of Ephemeral Data

AU - Schmidt, Albrecht

AU - Jensen, Christian Søndergaard

PY - 2006

Y1 - 2006

N2 - Motivated by the increasing prominence of loosely-coupled systems, such as mobile and sensor networks, the characteristics of which include intermittent connectivity and volatile data, we study the tagging of data with so-called expiration times. More specifically, when data are inserted into a database, they may be stamped with time values indicating when they expire, i.e., when they are regarded as stale or invalid and thus are no longer considered part of the database. In a number of applications, expiration times are known and can be assigned at insertion time. We present data structures and algorithms for online management of data stamped with expiration times. The algorithms are based on fully functional treaps, which are a combination of binary search trees with respect to a primary attribute and heaps with respect to a secondary attribute. The primary attribute implements primary keys, and the secondary attribute stores expiration times in a minimum heap, thus keeping a priority queue of tuples to expire. A detailed and comprehensive experimental study demonstrates the well-behavedness and scalability of the approach as well as its efficiency with respect to a number of competitors.

AB - Motivated by the increasing prominence of loosely-coupled systems, such as mobile and sensor networks, the characteristics of which include intermittent connectivity and volatile data, we study the tagging of data with so-called expiration times. More specifically, when data are inserted into a database, they may be stamped with time values indicating when they expire, i.e., when they are regarded as stale or invalid and thus are no longer considered part of the database. In a number of applications, expiration times are known and can be assigned at insertion time. We present data structures and algorithms for online management of data stamped with expiration times. The algorithms are based on fully functional treaps, which are a combination of binary search trees with respect to a primary attribute and heaps with respect to a secondary attribute. The primary attribute implements primary keys, and the secondary attribute stores expiration times in a minimum heap, thus keeping a priority queue of tuples to expire. A detailed and comprehensive experimental study demonstrates the well-behavedness and scalability of the approach as well as its efficiency with respect to a number of competitors.

M3 - Article in proceeding

SN - 3540333371

T3 - Lecture Notes in Computer Science

SP - 141

EP - 155

BT - Proceedings of the Eleventh International Conference on Database Systems for Advanced Applications

PB - Springer

ER -

Schmidt A, Jensen CS. Efficient Maintenance of Ephemeral Data. In Proceedings of the Eleventh International Conference on Database Systems for Advanced Applications. Springer. 2006. p. 141-155. (Lecture Notes in Computer Science; No. 3882).