Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS), Volume 35 Issue 4, November 2010

Foreword to TODS invited papers issue
Z. Meral Özsoyoğlu
Article No.: 23
DOI: 10.1145/1862919.1862920

An architecture for recycling intermediates in a column-store
Milena G. Ivanova, Martin L. Kersten, Niels J. Nes, Romulo A.P. Gonçalves
Article No.: 24
DOI: 10.1145/1862919.1862921

Automatic recycling of intermediate results to improve both query response time and throughput is a grand challenge for state-of-the-art databases. Tuples are loaded and streamed through a tuple-at-a-time processing pipeline, avoiding...

I/O efficient algorithms for serial and parallel suffix tree construction
Amol Ghoting, Konstantin Makarychev
Article No.: 25
DOI: 10.1145/1862919.1862922

Over the past three decades, the suffix tree has served as a fundamental data structure in string processing. However, its widespread applicability has been hindered due to the fact that suffix tree construction does not scale well with the size...

Space-optimal heavy hitters with strong error bounds
Radu Berinde, Piotr Indyk, Graham Cormode, Martin J. Strauss
Article No.: 26
DOI: 10.1145/1862919.1862923

The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. It has been observed that several proposed solutions to this problem can outperform their worst-case...

Relative information completeness
Wenfei Fan, Floris Geerts
Article No.: 27
DOI: 10.1145/1862919.1862924

This article investigates the question of whether a partially closed database has complete information to answer a query. In practice an enterprise often maintains master data Dm, a closed-world database. We say that a database...

Towards a theory of search queries
George H. L. Fletcher, Jan Van Den Bussche, Dirk Van Gucht, Stijn Vansummeren
Article No.: 28
DOI: 10.1145/1862919.1862925

The need to manage diverse information sources has triggered the rise of very loosely structured data models, known as dataspace models. Such information management systems must allow querying in simple ways, mostly by a form of searching....

Incremental XPath evaluation
Henrik Björklund, Wouter Gelade, Wim Martens
Article No.: 29
DOI: 10.1145/1862919.1862926

Incremental view maintenance for XPath queries asks to maintain a materialized XPath view over an XML database. It assumes an underlying XML database D and a query Q. One is given a sequence of updates U to D, and the...