Main-Memory Operation Buffering for Efficient R-Tree Update

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

34 Citations (Scopus)

Abstract

Emerging communication and sensor technologies enable new applications of database technology that require database systems to efficiently support very high rates of spatial-index updates. Previous works in this area require the availability of large amounts of main memory, do not exploit all the main memory that is indeed available, or do not support some of the standard index operations.
Assuming a setting where the index updates need not be written to disk immediately, we propose an R-tree-based indexing technique that does not exhibit any of these drawbacks. This technique exploits the buffering of update operations in main memory as well as the grouping of operations to reduce disk I/O. In particular, operations are performed in bulk so that multiple operations are able to share I/O. The paper presents an analytical cost model that is shown to be accurate by empirical studies. The studies also show that, in terms of update I/O performance, the proposed technique improves on state of the art in settings with frequent updates.
Original languageEnglish
Title of host publicationProceedings of the Thirtythird International Conference on Very Large Data Bases
Publication date2007
Pages591-602
Publication statusPublished - 2007
EventThe Thirtythird International Conference on Very Large Data Bases - Vienna, Austria
Duration: 23 Sep 200728 Sep 2007
Conference number: 33

Conference

ConferenceThe Thirtythird International Conference on Very Large Data Bases
Number33
CountryAustria
CityVienna
Period23/09/200728/09/2007

Fingerprint

Data storage equipment
Availability
Communication
Sensors
Costs

Cite this

Jensen, C. S., Saltenis, S., & Biveinis, L. (2007). Main-Memory Operation Buffering for Efficient R-Tree Update. In Proceedings of the Thirtythird International Conference on Very Large Data Bases (pp. 591-602)
Jensen, Christian Søndergaard ; Saltenis, Simonas ; Biveinis, Laurynas. / Main-Memory Operation Buffering for Efficient R-Tree Update. Proceedings of the Thirtythird International Conference on Very Large Data Bases. 2007. pp. 591-602
@inproceedings{cfaa16f0c82811dc8dd8000ea68e967b,
title = "Main-Memory Operation Buffering for Efficient R-Tree Update",
abstract = "Emerging communication and sensor technologies enable new applications of database technology that require database systems to efficiently support very high rates of spatial-index updates. Previous works in this area require the availability of large amounts of main memory, do not exploit all the main memory that is indeed available, or do not support some of the standard index operations. Assuming a setting where the index updates need not be written to disk immediately, we propose an R-tree-based indexing technique that does not exhibit any of these drawbacks. This technique exploits the buffering of update operations in main memory as well as the grouping of operations to reduce disk I/O. In particular, operations are performed in bulk so that multiple operations are able to share I/O. The paper presents an analytical cost model that is shown to be accurate by empirical studies. The studies also show that, in terms of update I/O performance, the proposed technique improves on state of the art in settings with frequent updates.",
author = "Jensen, {Christian S{\o}ndergaard} and Simonas Saltenis and Laurynas Biveinis",
year = "2007",
language = "English",
pages = "591--602",
booktitle = "Proceedings of the Thirtythird International Conference on Very Large Data Bases",

}

Jensen, CS, Saltenis, S & Biveinis, L 2007, Main-Memory Operation Buffering for Efficient R-Tree Update. in Proceedings of the Thirtythird International Conference on Very Large Data Bases. pp. 591-602, The Thirtythird International Conference on Very Large Data Bases, Vienna, Austria, 23/09/2007.

Main-Memory Operation Buffering for Efficient R-Tree Update. / Jensen, Christian Søndergaard; Saltenis, Simonas; Biveinis, Laurynas.

Proceedings of the Thirtythird International Conference on Very Large Data Bases. 2007. p. 591-602.

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

TY - GEN

T1 - Main-Memory Operation Buffering for Efficient R-Tree Update

AU - Jensen, Christian Søndergaard

AU - Saltenis, Simonas

AU - Biveinis, Laurynas

PY - 2007

Y1 - 2007

N2 - Emerging communication and sensor technologies enable new applications of database technology that require database systems to efficiently support very high rates of spatial-index updates. Previous works in this area require the availability of large amounts of main memory, do not exploit all the main memory that is indeed available, or do not support some of the standard index operations. Assuming a setting where the index updates need not be written to disk immediately, we propose an R-tree-based indexing technique that does not exhibit any of these drawbacks. This technique exploits the buffering of update operations in main memory as well as the grouping of operations to reduce disk I/O. In particular, operations are performed in bulk so that multiple operations are able to share I/O. The paper presents an analytical cost model that is shown to be accurate by empirical studies. The studies also show that, in terms of update I/O performance, the proposed technique improves on state of the art in settings with frequent updates.

AB - Emerging communication and sensor technologies enable new applications of database technology that require database systems to efficiently support very high rates of spatial-index updates. Previous works in this area require the availability of large amounts of main memory, do not exploit all the main memory that is indeed available, or do not support some of the standard index operations. Assuming a setting where the index updates need not be written to disk immediately, we propose an R-tree-based indexing technique that does not exhibit any of these drawbacks. This technique exploits the buffering of update operations in main memory as well as the grouping of operations to reduce disk I/O. In particular, operations are performed in bulk so that multiple operations are able to share I/O. The paper presents an analytical cost model that is shown to be accurate by empirical studies. The studies also show that, in terms of update I/O performance, the proposed technique improves on state of the art in settings with frequent updates.

M3 - Article in proceeding

SP - 591

EP - 602

BT - Proceedings of the Thirtythird International Conference on Very Large Data Bases

ER -

Jensen CS, Saltenis S, Biveinis L. Main-Memory Operation Buffering for Efficient R-Tree Update. In Proceedings of the Thirtythird International Conference on Very Large Data Bases. 2007. p. 591-602