Efficient Maintenance of Ephemeral Data

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelProceedings of the Eleventh International Conference on Database Systems for Advanced Applications
ForlagSpringer
Publikationsdato2006
Sider141-155
ISBN (Trykt)3540333371
StatusUdgivet - 2006
BegivenhedInternational Conference on Database Systems for Advanced Applications - Singapore, Singapore
Varighed: 12 apr. 200615 apr. 2006
Konferencens nummer: 11

Konference

KonferenceInternational Conference on Database Systems for Advanced Applications
Nummer11
LandSingapore
BySingapore
Periode12/04/200615/04/2006
NavnLecture Notes in Computer Science
Nummer3882
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Efficient Maintenance of Ephemeral Data'. Sammen danner de et unikt fingeraftryk.

Citationsformater