9401708
Complex Aggregation at Multiple Granularities
Datacube queries compute simple aggregates at multiple granularities. In this paper we examine the more general and useful problem of computing a complex subquery involving multiple dependent aggregates at multiple granularities. We call such queries multi-feature cubes. An example is Broken down by all combinations of month and customer, find the fraction of the total sales in 1996 of a particular item due to suppliers supplying within 10% of the minimum price (within the group), showing all subtotals across each dimension. We classify multi-feature cubes based on the extent to which fine granularity results can be used to compute coarse granularity results; this classification includes distributive, algebraic and holistic multi-feature cubes. We provide syntactic sufficient conditions to determine when a multi-feature cube is either distributive or algebraic. This distinction is important because, as we show, existing datacube evaluation algorithms can be used to compute multi-feature cubes that are distributive or algebraic, without any increase in I/O complexity. We evaluate the CPU performance of computing multi-feature cubes using the datacube evaluation algorithm of Ross and Srivastava. Using a variety of synthetic, benchmark and real-world data sets, we demonstrate that the CPU cost of evaluating distributive multi-feature cubes is comparable to that of evaluating simple datacubes. We also show that a variety of holistic multi-feature cubes can be evaluated with a manageable overhead compared to the distributive case.
2292054
Efficient Hash Probes on Modern Processors
Bucketized versions of Cuckoo hashing can achieve 95-99% occupancy, without any space overhead for pointers or other structures. However, such methods typically need to consult multiple hash buckets per probe, and have therefore been seen as having worse probe performance than conventional techniques for large tables. We consider workloads typical of database and stream processing, in which keys and payloads are small, and in which a large number of probes are processed in bulk. We show how to improve probe performance by (a) eliminating branch instructions from the probe code, enabling better scheduling and latency-hiding by modern processors, and (b) using SIMD instructions to process multiple keys/payloads in parallel. We show that on modern architectures, probes to a bucketized Cuckoo hash table can be processed much faster than conventional hash table probes, for both small and large memory-resident tables. On a Pentium 4, a probe is two to four times faster, while on the Cell SPE processor a probe is ten times faster.
15557838
Structural totality and constraint stratification
Kenneth A. Ross* Department of Computer Science, Columbia University
16955834
Querying Multiple Features of Groups in Relational Databases
Some aggregate and grouping queries are conceptually simple, but difficult to express in SQL. This difficulty causes both conceptual and implementation problems for the SQLbased database system. Complicated queries and views are hard to understand and maintain. Further, the code produced is sometimes unnecessarily inefficient, as we demonstrate experimentally using a commercial database system. In this paper, we examine a class of queries involving (potentially repeated) selection, grouping and aggregation over the same groups, and propose an extension of SQL syntax that allows the succinct representation of these queries. We propose a new relational algebra operation that represents several levels of aggregation over the same groups in an operand relation. We demonstrate that the extended relational operator can be evaluated using efficient algorithms. We describe a translation from the extended SQL language into our algebraic language. We have implemented a preprocessor that evaluates our extended language on top of a commercial l This research was supported by a grant from the AT&T Foundation, by a David and Lucile Packard Foundation Fellowship in Science and Engineering, by a Sloan Foundation Fellowship, by NSF grants IRI-9209029, CDA-90-24735, and by an NSF Young Investigator award. Permission to copy without fee all or part of this material is gmnted provided that the wpier are not made or distributed for direct commercial advantage, the VLDB wpyrinht notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. Proceedings of the 22nd VLDB Conference Mumbai(Bombay), India, 1996 database system. We demonstrate that on a variety of examples, our implementation improves performance over standard SQL representations of the same examples by orders of magnitude.
2564021
Database research at Columbia University
Columbia University has a number of projects that touch on database systems issues. In this report, we describe the Columbia Fast Query Project (Section 2), the JAM project (Section 3), the CARDGIS project (Section 4), the Columbia Internet Information Searching Project (Section 5), the Columbia Content-Based Visual Query project (Section 6), and projects associated with Columbia’s Programming Systems Laboratory (Section 7).
8569541
Partitioned optimization of complex queries
Performing complex analysis on top of massive data stores is essential to most modern enterprises and organizations and requires significant aggregation over different attribute sets (dimensions) of the participating relations. Such queries may take hours or days, a time period unacceptable in most cases. As a result, it is important to study these queries and identify special frequent cases that can be evaluated with specialized algorithms. Understanding complex aggregate queries leads to better execution plans and, consequently, performance. The idea of partitioning is fundamental and central in aggregate queries. This concept can be used to define a class of queries called group queries. The main characteristic of a group query is that it can be evaluated in a partitioned (or groupwise) fashion, i.e. the underlying relation(s) can be partitioned (based on a set of attributes) into disjoint groups and each group can be processed separately, possibly in parallel. For example, a query that performs a complex operation (e.g. joins and/or selections and/or aggregations) within each group is a group query. To express it in SQL, one has to join/correlate several views and/or subqueries on the grouping attributes. A naive plan (where the joins are executed) may be very expensive, even for relatively small base relations. On the other hand, a groupwise evaluation can lead to huge performance gains. We present a syntactic criterion to identify group queries in SQL and show that every group query can be expressed in a way that satisfies this criterion. This work is based on Chatziantoniou and Ross [Querying Multiple Features of Groups in Relational Databases. in: 22nd International Conference on Very Large Databases, VLDB, 1996, pp. 295-306]. The concept of group queries is useful not only in terms of evaluation, but also in terms of analyzing a complex decision support query that aggregates over different sets of attributes. In such a case the query may be decomposable to one or more query components, where each component is a group query. This observation allows parallel execution, multi-query processing and identification of special cases. We present in this paper two algorithms to decompose a complex aggregate query to its group query components. The value of groupwise processing has been recently recognized by the research community and implemented in at least a major commercial system. To be of use however in a relational system, partitioned evaluation has to be modeled as a relational operator. We review three different approaches for such an operator and propose a generalized groupwise operator. We also perform some experiments to show that naive optimization with the new operator incorporated without taking into consideration decompositions to group query components does not always lead to the most efficient plans. An extended syntax is another way to identify special frequent cases and apply efficient algorithms. Having specific operators for common operations contributes to the succinctness and optimizability of certain queries (e.g. datacubes). An extended syntax is presented with emphasis for multi-feature queries, a frequent and practical subclass of group queries that is amenable to specialized evaluation, involving (potentially repeated) selection, grouping and aggregation over the same groups.
6259994
Hierarchical Peer-To-Peer Systems
Structured peer-to-peer (P2P) lookup services organize peers into a flat overlay network and offer distributed hash table (DHT) functionality. Data is associated with keys and each peer is responsible for a subset of the keys. In hierarchical DHTs, peers are organized into groups, and each group has its autonomous intra-group overlay network and lookup service. Groups are organized in a top-level overlay network. To find a peer that is responsible for a key, the top-level overlay first determines the group responsible for the key; the responsible group then uses its intra-group overlay to determine the specific peer that is responsible for the key. We provide a general framework for hierarchical DHTs with scalable overlay management. We specifically study a two-tier hierarchy that uses Chord for the top level. Our analysis shows that by using the most reliable peers in the top level, the hierarchical design significantly reduces the expected number of hops. We also present a method to construct hierarchical DHTs that map well to the Internet topology and achieve short intra-group communication delay. The results demonstrate the feasibility of locality-based peer groups, which allow P2P systems to take full advantage of the hierarchical design.
10446891
Periodic broadcasting with VBR-encoded video
Abstract.We consider designing near video on demand (NVOD) systems that minimize startup latency while maintaining high image quality. Recently nonuniform segmentation has been used to develop periodic broadcasting techniques for NVOD. These techniques give significant reductions in startup latency as compared with more conventional uniform segmentation. Essentially all of these schemes assume, however, that the videos are CBR-encoded. Since a CBR-encoded video has a larger average rate than an open-loop VBR encoding with the same image quality, there is potential to obtain further performance improvements by using VBR video. In this paper we develop a series of multiplexing schemes for the periodic broadcasting of VBR-encoded video that are based on smoothing, server buffering, and client prefetching. Two key but conflicting performance measures exist when using VBR video: latency and packet loss. By introducing small additional delays in our multiplexing schemes, our trace-based numerical work shows that the schemes can achieve nearly 100% link utilization with negligible packet loss. When the ratio of the CBR rate to the VBR average rate is a modest 1.8, startup latency can be reduced by a factor of four or more for common scenarios.
1775458
Optimal streaming of layered video
This paper presents a model and theory for streaming layered video. We model the bandwidth available to the streaming application as a stochastic process whose statistical characteristics are unknown a priori. The random bandwidth models short-term variations due to congestion control (such as TCP-friendly conformance). We suppose that the video has been encoded into a base and an enhancement layer, and that to decode the enhancement layer the base layer has to be available to the client. We make the natural assumption that the client has abundant local storage and attempts to prefetch as much of the video as possible during playback. At any instant of time, starvation or partial starvation can occur at the client in either of the two layers. During periods of starvation, the client applies video error concealment to hide the loss. We study the dynamic allocation of the available bandwidth to the two layers in order to minimize the impact pact of client starvation. For the case of an infinitely-long video, we find that the optimal policy takes on a surprisingly simple and static form. For finite-length videos, the optimal policy is a simple static policy when the enhancement layer is deemed at least as important as the base layer. When the base layer is more important, we design a threshold policy heuristic which switches between two static policies. We provide numerical results that compare the performance of no-prefetching, static and threshold policies.
8733679
Stochastic Fluid Theory for P2P Streaming Systems
We develop a simple stochastic fluid model that seeks to expose the fundamental characteristics and limitations of P2P streaming systems. This model accounts for many of the essential features of a P2P streaming system, including the peers' realtime demand for content, peer churn (peers joining and leaving), peers with heterogeneous upload capacity, limited infrastructure capacity, and peer buffering and playback delay. The model is tractable, providing closed-form expressions which can be used to shed insight on the fundamental behavior of P2P streaming systems. The model shows that performance is largely determined by a critical value. When the system is of moderate-to-large size, if a certain ratio of traffic loads exceeds the critical value, the system performs well; otherwise, the system performs poorly. Furthermore, large systems have better performance than small systems since they are more resilient to bandwidth fluctuations caused by peer churn. Finally, buffering can dramatically improve performance in the critical region, for both small and large systems. In particular, buffering can bring more improvement than can additional infrastructure bandwidth.
10455339
Pollution in P2P file sharing systems
One way to combat P2P file sharing of copyrighted content is to deposit into the file sharing systems large volumes of polluted files. Without taking sides in the file sharing debate, in this paper we undertake a measurement study of the nature and magnitude of pollution in the FastTrack P2P network, currently the most popular P2P file sharing system. We develop a crawling platform which crawls the majority of the FastTrack Network's 20,000+ supernodes in less than 60 minutes. From the raw data gathered by the crawler for popular audio content, we obtain statistics on the number of unique versions and copies available in a 24-hour period. We develop an automated procedure to detect whether a given version is polluted or not, and we show that the probabilities of false positives and negatives of the detection procedure are very small. We use the data from the crawler and our pollution detection algorithm to determine the fraction of versions and fraction of copies that are polluted for several recent and old songs. We observe that pollution is pervasive for recent popular songs. We also identify and describe a number of anti-pollution mechanisms.