2006 technical reports

The proposed system has a partially decentralized architecture involving superpeers and adopts a novel structured search mechanism derived from the theory of Error Correcting Codes (ECC). Better resilience to peer failure is achieved by utilizing replication and redundant routing paths. The number of routing hops and the number of links maintained by each superpeer scales logarithmically with the number of superpeers. The concept presented in this paper is supported with theoretical analysis, and simulation results.

We present an algorithm for rank-2 type inference in the second-order $\lambda$-calculus. Our algorithm differs from the well-known algorithm of Kfoury and Wells in that it employs only a quadratically fewer type variables and inequalities. Our algorithm consists of a translation from a $\lambda$-term to an instance of $R$-ASUP (a decidable superset of ASUP) in which the variables correspond more directly to features in the original term. We claim that our construction, being simpler and more direct, is more amenable to proof and extension.

Keywords: pattern, pattern automata, pattern expressions, regex, regular expressions

We present and rigorously analyse an algorithm that uses a a tree of virtual nodes to compute nearly arbitrary functions of global state. Our scheme is fast: running time is $\Theta(ln n)$. It is efficient: nodes exchange O(n ln n) messages. Most of these messages are within a data centre and therefore are relatively cheap. It is accurate: the computed value does not have inherent errors either due to double-counting, as with standard gossip, or due to stochastic counting, as in the Flajolet-Martin approach. Finally, it is fault tolerant: The algorithm fails with probability O( 1 / n^{c(1+r)} )$ where c is a constant and 0 <= r \leq (\ln n)^Cst a user-chosen reliability parameter. We therefore believe that our work is the basis for building robust and efficient distributed systems in a variety of problem domains.

As opposed to succinct encodings, The main advantage of succinct indexes is that we make assumptions only on the ADT through which the main data is accessed, rather than the way in which the data is encoded. This allows more freedom in the encoding of the main data.In this paper, we present succinct indexes for various data types, namely strings, binary relations and multi-labeled trees. Given the support for the interface of the ADTs of these data types, we can support various useful operations efficiently by constructing succinct indexes for them. When the operators in the ADTs are supported in constant time, our results are comparable to previous results, while allowing more flexibility in the encoding of the given data. Using our techniques, we design the first succinct encoding that represents a string of length $n$ over alphabet $[\sigma]$ using $nH_k+o(n\lg \sigma)$ bits \footnote{We use $\lg n$ to denote $\lceil \log_2 n \rceil$.} that support access / rank / select operations in $o((\lg\lg \sigma)3)$ time. We also design the first succinct text index using $nH_k+o(n\lg\sigma)$ bits that supports pattern matching queries in $O(m\lg\lg\sigma + occ\lg^{1+\epsilon}n\lg\lg\sigma)$ time, for a given pattern of length $m$. Previous results on these two problems either have a $\lg\sigma$ factor instead of $\lg\lg\sigma$ in terms of running time, or are not compressible, but our results do not have such problems.

Top-k processing in uncertain databases is semantically and computationally different from traditional top-k processing. The interplay between score and uncertainty information makes traditional processing techniques inapplicable to uncertain databases. In this paper we introduce new probabilistic formulations for top-k queries. Our formulations are based on marriage of traditional top-k semantics with possible worlds semantics. In the light of these formulations, we construct a framework that encapsulates a novel probabilistic model and efficient query processing techniques to tackle the challenges raised by uncertain data settings. We prove that our techniques are optimal in terms of the number of accessed tuples. Our experiments show the efficiency of our techniques under different data distributions with orders of magnitude improvement over naive materialization of possible worlds.

The solution presented in this paper focuses on periodically-evaluated aggregates over sliding windows of various lengths, which are a common class of persistent queries used for monitoring purposes. The proposed solution assumes that users specify an upper bound on the interval between re-evaluations of their queries and is based upon the following insight: it may be cheaper to re-execute some queries more often if their re-execution schedules can be synchronized with those of similar queries, thereby amortizing the computation costs. We also show that additional schedule synchronization is possible when the system is forced to lengthen the desired re-execution intervals during periods of overload. Our solutions are based upon a variant of the earliest-deadline-first algorithm that views persistent queries are periodic tasks. Experimental results show significant improvements in system throughput due to increased resource sharing.

This dissertation begins with the observation that the two fundamental requirements of a DSMS are dealing with transient (time-evolving) rather than static data and answering persistent rather than transient queries. One implication of the first requirement is that data maintenance costs have a significant effect on the performance of a DSMS. Additionally, traditional query processing algorithms must be re-engineered for the sliding window model because queries may need to re-process expired data and "undo" previously generated results. The second requirement suggests that a DSMS may execute a large number of persistent queries at the same time, therefore there exist opportunities for resource sharing among similar queries.

The purpose of this dissertation is to develop solutions for efficient query processing over sliding windows by focusing on these two fundamental properties. In terms of the transient nature of streaming data, this dissertation is based upon the following insight. Although the data keep changing over time as the windows slide forward, the changes are not random; on the contrary, the inputs and outputs of a DSMS exhibit patterns in the way the data are inserted and deleted. It will be shown that the knowledge of these patterns leads to an understanding of the semantics of persistent queries, lower window maintenance costs, as well as novel query processing, query optimization, and concurrency control strategies. In the context of the persistent nature of DSMS queries, the insight behind the proposed solution is that various queries may need to be refreshed at different times, therefore synchronizing the refresh schedules of similar queries creates more opportunities for resource sharing.

XML has emerged as a semantic markup language for documents as well as the de facto language for data exchange over the World Wide Web. Declarative query languages, such as XPath and XQuery, are proposed for querying over large volumes of XML data. A number of techniques have been proposed to evaluate XML queries more efficiently. Many of these techniques assume a tree model of XML documents and are, therefore, also applicable to other data sources that can be explicitly or implicitly translated into a similar data model.

The focus of this thesis is on efficient evaluation and optimization of path expressions in native XML databases. Specifically, the following issues are considered: storage system design, design of physical operators and efficient execution algorithms, and the cost-based query optimizer.

The proposed storage system linearizes the tree structure into strings that can be decomposed into disk pages. Simple statistics are kept in the page headers to facilitate I/O-efficient navigation. Based on this storage system, a hybrid approach is developed to evaluate path expressions that exploit the advantages of navigational and join-based approaches. Path expressions that only contain "local" axes (child, parent, attribute, self, following-sibling, and preceding-sibling) are evaluated by means of the proposed "Next-of-Kin" (NoK) operator. A general path expression that contains both local axes and global ones (ancestor, descendant, ancestor-or-self, descendant-or-self, following, and preceding) is decomposed into NoK subtrees whose intermediate results are structurally joined to produce the final result. Experiments show that the navigational operator can be an order of magnitude faster than join-based approaches in some cases, but slower in others. Thus a cost-based query optimizer is necessary to choose the optimal execution plan based on estimates of the cost of each operator.

The cost of an operator heavily depends on the cost model and its input. The inputs to the cost model are usually the cardinalities of path expressions. In this thesis, a synopsis structure called XSEED is proposed to estimate the cardinality of a path expression. An XSEED synopsis can be constructed by compressing an XML document to a small kernel first, and then more information can be added to the synopsis. XSEED results in more accurate cardinality estimation than previous approaches and is easier to construct, easier to update, and can incorporate query feedback.

Efficient query execution exploits indexes. The last component of the thesis is a feature-based structural index, called FIX, to expedite tree matching on a large tree. This is based on the observation that the navigational operation is expensive and applying it to every tree node is very inefficient. FIX extracts distinctive features from subtrees and uses them as the index keys. Similarly, for each incoming query, the features of the query tree are extracted and used as search keys to retrieve the candidate results. Thus, it is sufficient to match only on these candidate results. The experimental results show that the pruning power of FIX is very high -- more than 99% for structure-rich data sets, and more than 20% for data sets with less structural variety.

Keywords: Probabilistic transducer, Probabilistic automaton, Stochastic transducer, Stochastic automaton, Stochastic transduction, Weighted transducer, Transducer, Automaton

Our experimental results show that unaligned binary codes that take into account the special properties of schema-independent indices achieve better compression rates than methods designed for compressing document indices and that they can reduce the size of the index by around 15% compared to byte-aligned index compression. Moreover, we present a number of performance-enhancing techniques that may be used to very efficiently decode unaligned codes. Thus, their more compact index representation does not carry the cost of a substantially decreased query processing performance. This contradicts most earlier results on the decoding performance of unaligned codes.

Using this framework, we prove that Move-to-Front (MTF) is the unique optimal algorithm for list update. This holds for both the standard cost function of Sleator and Tarjan~[C. ACM 1985] and the refined cost function proposed independently by Mart\'{\i}nez and Roura~[TCS 2000] and Munro~[ESA 2000]. Our work resolves an open conjecture of Mart\'{\i}nez and Roura, namely proposing a measure which can successfully separate MTF from all other algorithms.