27538683
Academic dishonesty and the Internet
The Internet provides new opportunities for cheating on computer science class projects.
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.
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.
7365552
Tail recursion elimination in deductive databases
We consider an optimization technique for deductive and relational databases. The optimization technique is an extension of the magic templates rewriting, and it can improve the performance of query evaluation by not materializing the extension of intermediate views. Standard relational techniques, such as unfolding embedded view definitions, do not apply to recursively defined views, and so alternative techniques are necessary. We demonstrate the correctness of our rewriting. We define a class of “nonrepeating” view definitions, and show that for certain queries our rewriting performs at least as well as magic templates on nonrepeating views, and often much better. A syntactically recognizable property, called “weak right-linearity”, is proposed. Weak right-linearity is a sufficient condition for nonrepetition and is more general than right-linearity. Our technique gives the same benefits as right-linear evaluation of right-linear views, while applying to a significantly more general class of views.
7567374
Foundations of Aggregation Constraints
We introduce a new constraint domain, aggregation constraints, which is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We study the fundamental problem of checking if a conjunction of aggregation constraints is solvable, and present undecidability results for many different classes of aggregation constraints. We describe a complete and minimal axiomatization of the class of aggregation constraints over finite multisets of reals, which permits a natural reduction from the class of aggregation constraints to the class of mixed integer/real, non-linear arithmetic constraints. We then present a polynomial-time algorithm that directly checks for solvability of a useful class of aggregation constraints, where the reduction-based approach does not lead to efficient checks for solvability.
1995310
Cache Conscious Indexing for Decision-Support in Main Memory
We study indexing techniques for main memory, including hash indexes, binary search trees, T-trees, B+-trees, interpolation search, and binary search on arrays. In a decision-support context, our primary concerns are the lookup time, and the space occupied by the index structure. Our goal is to provide faster lookup times than binary search by paying attention to reference locality and cache behavior, without using substantial extra space. We propose a new indexing technique called \Cache-Sensitive Search Trees" (CSS-trees). Our technique stores a directory structure on top of a sorted array. Nodes in this directory have size matching the cache-line size of the machine. We store the directory in an array and do not store internal-node pointers; child nodes can be found by performing arithmetic on array osets. We compare the algorithms based on their time and space requirements. We have implemented all of the techniques, and present a performance study on two popular modern machines. We demonstrate that with This research was supported by a David and Lucile Packard Foundation Fellowship in Science and Engineering, by an NSF Young Investigator Award, by NSF grant number IIS-98-12014, and by NSF CISE award CDA-9625374.
369703
Object replication strategies in content distribution networks
Recently, the Internet has witnessed the emergence of content distribution networks (CDNs). In this paper, we study the problem of optimally replicating objects in CDN servers. In our model, each Internet autonomous system (AS) is a node with finite storage capacity for replicating objects. The optimization problem is to replicate objects so that when clients fetch objects from the nearest CDN server with the requested object, the average number of ASs traversed is minimized. We formulate this problem as a combinatorial optimization problem. We show that this optimization problem is NP complete. We develop four natural heuristics and compare them numerically using real Internet topology data. We find that the best results are obtained with heuristics that have all the CDN servers cooperating in making the replication decisions. We also develop a model for studying the benefits of cooperation between nodes, which provides insight into peer-to-peer content distribution.
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.
27419087
Implementation of Monte Carlo Integration for the Analysis of Product-Form Queueing Networks
Abstract MonteQueue is a new public-domain software package which rapidly solves large and small multiclass product-form queueing networks with multiple- and single-server stations over a wide range of traffic conditions. MonteQueue obtains estimates of performance measures by applying importance sampling to sum and integral representations of the network's normalization constants. This paper discusses the implementation issues and surveys of the theoretical properties of the four importance sampling techniques included in MonteQueue. It also presents new numerical data which compare the performance of the four techniques.
19447750
Local search scheduling algorithms for maximal throughput in packet switches
We consider the (generalized) packet switch scheduling problem, where the switch service configuration has to be dynamically chosen based on observed queue backlogs, so as to maximize the throughput. A class of recently developed 'projective' scheduling algorithms, which substantially generalize the well-known maximum weight matching (MWM) algorithms for crossbar switches, are explored from the perspective of complexity. The typically huge number of possible switch configurations that the scheduler has to consider in each timeslot has been previously observed to lead to an impractical computational requirement. We introduce a new class of projective schedules based on 'local search' concepts. In particular, rather than searching the entire (typically huge) set of available service configurations to find the best one, the new scalable scheduling algorithms search 'locally' over a small neighborhood of service configurations to find a 'better' one in each time slot. We show that local projective scheduling algorithms can provide dramatic reduction in complexity without causing any loss of throughput (although they may observe higher delay). We explore the nature and structure of such schedules, which show a much higher promise for practical implementation than their global versions.
1377609
Computing approximate blocking probabilities for large loss networks with state-dependent routing
A reduced load approximation (also referred to as an Erlang fixed point approximation) for estimating point-to-point blocking probabilities in loss networks (e.g., circuit switched networks) with state-dependent routing is considered. In this approximation scheme, the idle capacity distribution for each link in the network is approximated, assuming that these distributions are independent from link to link. This leads to a set of nonlinear fixed-point equations which can be solved by repeated substitutions. The accuracy and the computational requirements of the approximation procedure for a particular routing scheme, namely least loaded routing, is examined. Numerical results for six-node and 36-node asymmetric networks are given. A novel reduced load approximation for multirate networks with state-dependent routing is also presented. >