Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS), Volume 31 Issue 4, December 2006

Expressive power of an algebra for data mining
Toon Calders, Laks V. S. Lakshmanan, Raymond T. Ng, Jan Paredaens
Pages: 1169-1214
DOI: 10.1145/1189769.1189770
The relational data model has simple and clear foundations on which significant theoretical and systems research has flourished. By contrast, most research on data mining has focused on algorithmic issues. A major open question is: what's an...

On the complexity of nonrecursive XQuery and functional query languages on complex values
Christoph Koch
Pages: 1215-1256
DOI: 10.1145/1189769.1189771
This article studies the complexity of evaluating functional query languages for complex values such as monad algebra and the recursion-free fragment of XQuery. We show that monad algebra, with equality restricted to atomic values, is complete for...

Adaptive rank-aware query optimization in relational databases
Ihab F. Ilyas, Walid G. Aref, Ahmed K. Elmagarmid, Hicham G. Elmongui, Rahul Shah, Jeffrey Scott Vitter
Pages: 1257-1304
DOI: 10.1145/1189769.1189772
Rank-aware query processing has emerged as a key requirement in modern applications. In these applications, efficient and adaptive evaluation of top-k queries is an integral part of the application semantics. In this article, we introduce a...

Maintaining stream statistics over multiscale sliding windows
Yishan Jiao
Pages: 1305-1334
DOI: 10.1145/1189769.1189773
In this article, we propose a new multiscale sliding window model which differentiates data items in different time periods of the data stream, based on a reasonable monotonicity of resolution assumption. Our model, as a well-motivated extension of...

Towards multidimensional subspace skyline analysis
Jian Pei, Yidong Yuan, Xuemin Lin, Wen Jin, Martin Ester, Qing Liu, Wei Wang, Yufei Tao, Jeffrey Xu Yu, Qing Zhang
Pages: 1335-1381
DOI: 10.1145/1189769.1189774
The skyline operator is important for multicriteria decision-making applications. Although many recent studies developed efficient methods to compute skyline objects in a given space, none of them considers skylines in multiple subspaces...

The Sort-Merge-Shrink join
Christopher Jermaine, Alin Dobra, Subramanian Arumugam, Shantanu Joshi, Abhijit Pol
Pages: 1382-1416
DOI: 10.1145/1189769.1189775
One of the most common operations in analytic query processing is the application of an aggregate function to the result of a relational join. We describe an algorithm called the Sort-Merge-Shrink (SMS) Join for computing the answer to...

Foreword to special section on SIGMOD/PODS 2005
Foto Afrati, Jennifer Widom
Pages: 1417-1417
DOI: 10.1145/1189769.1189776

Feature-based similarity search in graph structures
Xifeng Yan, Feida Zhu, Philip S. Yu, Jiawei Han
Pages: 1418-1453
DOI: 10.1145/1189769.1189777
Similarity search of complex structures is an important operation in graph-related applications since exact matching is often too restrictive. In this article, we investigate the issues of substructure similarity search using indexed features...

Peer data exchange
Ariel Fuxman, Phokion G. Kolaitis, Renée J. Miller, Wang-Chiew Tan
Pages: 1454-1498
DOI: 10.1145/1189769.1189778
In this article, we introduce and study a framework, called peer data exchange, for sharing and exchanging data between peers. This framework is a special case of a full-fledged peer data management system and a generalization of data exchange...

A divide-and-merge methodology for clustering
David Cheng, Ravi Kannan, Santosh Vempala, Grant Wang
Pages: 1499-1525
DOI: 10.1145/1189769.1189779
We present a divide-and-merge methodology for clustering a set of objects that combines a top-down “divide” phase with a bottom-up “merge” phase. In contrast, previous algorithms use either top-down or bottom-up methods to...