ACM DL

Database Systems (TODS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Database Systems (TODS), Volume 30 Issue 2, June 2005

Tight upper bounds on the number of candidate patterns
Floris Geerts, Bart Goethals, Jan Van Den Bussche
Pages: 333-363
DOI: 10.1145/1071610.1071611
In the context of mining for frequent patterns using the standard levelwise algorithm, the following question arises: given the current level and the current set of frequent patterns, what is the maximal number of candidate patterns that can be...

iDistance: An adaptive B+-tree based indexing method for nearest neighbor search
H. V. Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu, Rui Zhang
Pages: 364-397
DOI: 10.1145/1071610.1071612
In this article, we present an efficient B+-tree based indexing method, called iDistance, for K-nearest neighbor (KNN) search in a high-dimensional metric space. iDistance partitions the data based on a space- or data-partitioning...

XQBE (XQuery By Example): A visual interface to the standard XML query language
Daniele Braga, Alessandro Campi, Stefano Ceri
Pages: 398-443
DOI: 10.1145/1071610.1071613
The spreading of XML data in many contexts of modern computing infrastructures and systems causes a pressing need for adequate XML querying capabilities; to address this need, the W3C is proposing XQuery as the standard query language for XML, with a...

Efficient algorithms for processing XPath queries
Georg Gottlob, Christoph Koch, Reinhard Pichler
Pages: 444-491
DOI: 10.1145/1071610.1071614
Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We show that XPath can be processed much more...

Making snapshot isolation serializable
Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil, Patrick O'Neil, Dennis Shasha
Pages: 492-528
DOI: 10.1145/1071610.1071615
Snapshot Isolation (SI) is a multiversion concurrency control algorithm, first described in Berenson et al. [1995]. SI is attractive because it provides an isolation level that avoids many of the common concurrency anomalies, and has been implemented...

Aggregate nearest neighbor queries in spatial databases
Dimitris Papadias, Yufei Tao, Kyriakos Mouratidis, Chun Kit Hui
Pages: 529-576
DOI: 10.1145/1071610.1071616
Given two spatial datasets P (e.g., facilities) and Q (queries), an aggregate nearest neighbor (ANN) query retrieves the point(s) of P with the smallest aggregate distance(s) to points in Q. Assuming, for example,...

XSQ: A streaming XPath engine
Feng Peng, Sudarshan S. Chawathe
Pages: 577-623
DOI: 10.1145/1071610.1071617
We have implemented and released the XSQ system for evaluating XPath queries on streaming XML data. XSQ supports XPath features such as multiple predicates, closures, and aggregation, which pose interesting challenges for streaming evaluation. Our...

Relational languages for metadata integration
Catharine M. Wyss, Edward L. Robertson
Pages: 624-660
DOI: 10.1145/1071610.1071618
In this article, we develop a relational algebra for metadata integration, Federated Interoperable Relational Algebra (FIRA). FIRA has many desirable properties such as compositionality, closure, a deterministic semantics, a modest complexity,...