1630993
Join-distinct aggregate estimation over update streams
There is growing interest in algorithms for processing andquerying continuous data streams (i.e., data that is seenonly once in a fixed order) with limited memory resources.Providing (perhaps approximate) answers to queries over suchstreams is a crucial requirement for many application environments;examples include large IP network installations where performancedata from different parts of the network needs to be continuouslycollected and analyzed.
The ability to estimate the number of distinct (sub)tuples inthe result of a join operation correlating two data streams (i.e.,the cardinality of a projection with duplicate elimination over ajoin) is an important requirement for several data-analysisscenarios. For instance, to enable real-time traffic analysis andload balancing, a network-monitoring application may need toestimate the number of distinct (<i>source</i>,destination) IP-address pairs occurring in the stream of IP packetsobserved by router <i>R</i><inf>1</inf>,where the source address is also seen in packets routed through adifferent router <i>R</i><inf>2</inf>.Earlier work has presented solutions to the individual problems ofdistinct counting and join-size estimation (without duplicateelimination) over streams. These solutions, however, arefundamentally different and extending or combining them to handleour more complex "Join-Distinct" estimation problem is far fromobvious. In this paper, we propose the <i>first</i>space-efficient algorithmic solution to the general Join-Distinctestimation problem over continuous data streams (our techniques canactually handle general <i>update streams</i>comprising tuple deletions as well as insertions). Our estimatorsare probabilistic in nature and rely on novel algorithms forbuilding and combining a new class of hash-based synopses (termed"JD <i>sketches</i>") for individual update streams. Wedemonstrate that our algorithms can provide low error,high-confidence Join-Distinct estimates using only small space andsmall processing time per update. In fact, we present lower boundsshowing that the space usage of our estimators is within smallfactors of the best possible for the Join-Distinct problem.Preliminary experimental results verify the effectiveness of ourapproach.
5867882
Wavelength conversion in optical networks
In many models of optical routing, we are given a set of communication paths in a network, and we must assign a wavelength to each path so that paths sharing an edge receive different wavelengths. The goal is to assign as few wavelengths as possible in order to make as efficient use as possible of the optical bandwidth. A lot of work in the area of optical networks has considered the use of wavelength converters: if a node of a network contains a wavelength converter, any path that passes through this node may change its wavelength. Having converters at some of the nodes can reduce the number of wavelengths required for routing, down to the following natural congestion bound: even with converters, we will always need at least as many wavelengths as the maximum number of paths sharing a single edge. Thus Wilfong and Winkler defined a set S of nodes in a network to be sufficient if, placing converters at the nodes in S, every set of paths can be routed with a number of wavelengths equal to its congestion bound. They showed that finding a sufficient set of minimum size is NP-complete, even in planar graphs.In this paper, we provide a polynomial-time algorithm to find a sufficient set for an arbitrary directed network whose size is within a factor of 2 of minimum. We also observe that improving on the factor of 2 would lead to a corresponding improvement for the vertex cover problem. For the case of planar graphs, we provide a polynomial-time approximation scheme. The algorithms are based on connections between the minimum sufficient set problem and the undirected feedback vertex set problem. In particular, as a component of the algorithm on planar graphs, we develop the first polynomial-time approximation scheme for the undirected feedback vertex set problem in planar graphs, a result that we feel to be of interest in its own right.
206560175
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem
We present the first constant factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity buy-at-bulk network design in which there are two ways to install capacity on any given edge. Capacity can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. Recent work on buy-at-bulk network design has concentrated on the special case where all sinks are identical; existing constant factor approximation algorithms for this special case make crucial use of the assumption that all commodities ship flow to the same sink vertex and do not obviously extend to the multicommodity rent-or-buy problem. Prior to our work, the best heuristics for the multicommodity rent-or-buy problem achieved only logarithmic performance guarantees and relied on the machinery of relaxed metrical task systems or of metric embeddings. By contrast, we solve the network design problem directly via a novel primal-dual algorithm.
46145059
Primal-Dual Algorithms for Connected Facility Location Problems
We consider the Connected Facility Location problem. We are given a graph G = (V, E) with cost ce on edge e, a set of facilities F ? V, and a set of demands D ? V. We are also given a parameter M ? 1. A solution opens some facilities, say F, assigns each demand j to an open facility i(j), and connects the open facilities by a Steiner tree T. The cost incurred is ?i?F fi + ?j?D djci(j)j + M ?e?T ce. We want a solution of minimum cost. A special case is when all opening costs are 0 and facilities may be opened anywhere, i.e., F = V. If we know a facility v that is open, then this problem reduces to the rent-or-buy problem. We give the first primal-dual algorithms for these problems and achieve the best known approximation guarantees. We give a 9-approximation algorithm for connected facility location and a 5-approximation for the rent-or-buy problem. Our algorithm integrates the primal-dual approaches for facility location [7] and Steiner trees [1,2]. We also consider the connected k-median problem and give a constant-factor approximation by using our primal-dual algorithm for connected facility location. We generalize our results to an edge capacitated version of these problems.
47268289
Optimal configuration of OSPF aggregates
Open Shortest Path First (OSPF) is a popular protocol for routing within an autonomous system (AS) domain. In order to scale for large networks containing hundreds and thousands of subnets, OSPF supports a two-level hierarchical routing scheme through the use of OSPF areas. Subnet addresses within an area are aggregated, and this aggregation is a crucial requirement for scaling OSPF to large AS domains, as it results in significant reductions in routing table sizes, smaller link-state databases, and less network traffic to synchronize the router link-state databases. On the other hand, address aggregation also implies loss of information about the length of the shortest path to each subnet, which in turn, can lead to suboptimal routing.In this paper, we address the important practical problem of configuring OSPF aggregates to minimize the error in OSPF shortest-path computations due to subnet aggregation. We first develop an optimal dynamic programming algorithm that, given an upper bound k on the number of aggregates to be advertised and a weight assignment function for the aggregates, computes the k aggregates that result in the minimum cumulative error in the shortest-path computations for all source-destination subnet pairs. Subsequently, we tackle the problem of assigning weights to OSPF aggregates such that the cumulative error in the computed shortest paths is minimized. We demonstrate that, while for certain special cases (e.g., unweighted cumulative error) efficient optimal algorithms for the weight assignment problem can be devised, the general problem itself is NP-hard. Consequently, we have to rely on search heuristics to solve the weight assignment problem. To the best of our knowledge, our work is the first to address the algorithmic issues underlying the configuration of OSPF aggregates and to propose efficient configuration algorithms that are provably optimal for many practical scenarios.
8488383
Sorting and selection with structured costs
The study of the effect of priced information on basic algorithmic problems was initiated by M. Charikar et al. (2000). The authors continue the study of sorting and selection in the priced comparison model, i.e., when each comparison has an associated cost, and answer some of the open problems suggested by Charikar et al. If the comparison costs are allowed to be arbitrary, we show that one cannot get good approximation ratios. A different way to assign costs is based on the idea that one can distill out an intrinsic value for each item being compared, such that the cost of comparing two elements is some "well-behaved" or "structured" function of their values. We feel that most practical applications will have some structured cost property. The authors study the problems of sorting and selection (which includes finding the maximum and the median) in the structured cost model. We get a variety of approximation results for these problems, depending on the restrictions we put on the structured costs. We show that it is possible to get much improved results with the structured cost model than the case when we do not have any assumptions on comparison costs.
36050355
An efficient algorithm for solving the partial sum query problem
Abstract We address the problem: given n data values, how many partial sums must be stored so that partial sums of any other combination of these n values can be calculated in one arithmetic operation from the stored values. This problem has application in online analytical processing (OLAP) databases [Gray et al., Proc. 12th Int. Conf. Data Eng. (1996)] where it is called the partial sum aggregation query. It can also be used to generate the entire power set of n values efficiently. In this paper, we derive lower bounds for this problem, devise an efficient algorithm to solve it and show that our heuristic comes reasonably close to the lower bound.
16105375
Stochastic models for throughput analysis of randomly arriving elastic flows in the Internet
This paper is about analytical models for calculating the average bandwidth shares obtained by TCP controlled finite file transfers that arrive randomly and share a single (bottleneck) link. Owing to the complex nature of the TCP congestion control algorithm, a single model does not work well for all combinations of network parameters (i.e., mean file size, link capacity, and propagation delay). We propose two models, develop their analyses, and identify the regions of their applicability. One model is obtained from a detailed analysis of TCP's AIMD adaptive window mechanism; the analysis accounts for session arrivals and departures, and finite link buffers. It is essentially a processor sharing (PS) model with time varying service rate; hence we call it TCP-PS. The other model is a simple modification of the PS model that accounts for large propagation delays; we call this model rate limited-PS (RL-PS). The TCP-PS model analysis accommodates a general file size distribution by approximating it with a mixture of exponentials. The RL-PS model can be used for general file size distributions. We show that the TCP-PS model converges to the standard PS model as the propagation delay approaches zero. We also observe that the PS model provides very poor estimates of throughput unless the propagation delay is very small. We observe that the key parameters affecting the throughput are the bandwidth delay product (BDP), file size distribution, the link buffer and the traffic intensity. Several numerical comparisons between analytical and simulation results are provided. We observe that the TCP-PS model is accurate when the BDP is small compared to the mean file size, and the RL-PS model works well when the BDP is large compared to the mean file size.
206778468
A performance study of general grid structures for replicated data
Recently, there has been considerable interest in the study of replica-control protocols which are based on organizing several copies of an object into logical structures, such as rectangular grids. In addition to high availability, another objective in exploiting such structures is to improve the degree of load sharing in a system. The authors extend the scope of grid structures to general grids, which allow holes in various positions of a rectangular structure and are useful to consider because they often produce availabilities that are higher than solid grids, where every position must be occupied by a node. In addition to proposing an improvement to the existing grid protocol, new insights are offered into the performance of the grids, from both availability and load sharing points of view. Algorithms for designing grids to maximize availability independently and also in conjunction with a load sharing constraint are given.<<ETX>>
1111647
Performance Evaluation of an Operating System Transaction Manager
A conventional transaction manager implemented by a database management system (DBMS) was compared against one implemented within an operating system (OS) in a variety of simulated situations. Models of concurrency control and crash recovery were constructed for both environments, and the results of a collection of experiments are presented in this paper. The results indicate that an OS transaction manager incurs a severe performance disadvantage and appears to be feasible only in special circumstances.
17013178
Smart supply web: an application of web-based data and workflow mediation
This paper describes our vision of a Supply Web as the next major advance in the e-commerce world in terms of how e-services are delivered. After highlighting shortcomings of existing supply chain solutions, we give an architecture to show how three important technologies, namely, workow systems, data integration and on-line decision support, will have to come together to enable seamless deployment of e-service supply web solutions. We rst discuss research eorts (namely, XRL, YAT and DecisionFlows) that support the three technologies separately, and then describe the challenges of integrating them eectively.