enter search term and/or author name
Expressive power of an algebra for data mining
Toon Calders, Laks V. S. Lakshmanan, Raymond T. Ng, Jan Paredaens
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
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
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
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
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
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...
Feature-based similarity search in graph structures
Xifeng Yan, Feida Zhu, Philip S. Yu, Jiawei Han
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
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
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...