enter search term and/or author name
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
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
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
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...
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...
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 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...