Search

Hierarchical clustering is a fundamental tool in data mining, machine learning and statistics. Popular hierarchical clustering algorithms include top-down divisive approaches such as bisecting k-means, k-median, and k-center and bottom-up agglomerative approaches such as single-linkage, average-linkage, and centroid-linkage. Unfortunately, only a few scalable hierarchical clustering algorithms are known, mostly based on the single-linkage algorithm. So, as datasets increase in size every day, there is a pressing need to scale other popular methods.

The simulation of seismic waves is a core task in many geophysical applications. Numerical methods such as Finite Difference (FD) modelling and Spectral Element Methods (SEM) are the most popular techniques for simulating seismic waves in complex media, but for many tasks their computational cost is prohibitively expensive. In this work we present two types of deep neural networks as fast alternatives for simulating seismic waves in horizontally layered and faulted 2D acoustic media. In contrast to the classical methods both networks are able to simulate the seismic response at multiple locations within the media in a single inference step, without needing to iteratively model the seismic wavefield through time, resulting in an order of magnitude reduction in simulation time. This speed improvement could pave the way to real-time seismic simulation and benefit seismic inversion algorithms based on forward modelling, such as full waveform inversion. Our first network is able to simulate seismic waves in horizontally layered media. We use a WaveNet network architecture and show this is more accurate than a standard convolutional network design. Furthermore we show that seismic inversion can be carried out by retraining the network with its inputs and outputs reversed, offering a fast alternative to existing inversion techniques. Our second network is significantly more general than the first; it is able to simulate seismic waves in faulted media with arbitrary layers, fault properties and an arbitrary location of the seismic source on the surface of the media. It uses a convolutional autoencoder network design and is conditioned on the input source location. We investigate the sensitivity of different network designs and training hyperparameters on its simulation accuracy. We compare and contrast this network to the first network. To train both networks we introduce a time-dependent gain in the loss function which improves convergence. We discuss the relative merits of our approach with FD modelling and how our approach could be generalised to simulate more complex Earth models.

This paper considers scheduling parallelizable jobs in the non-clairvoyant speed scaling setting to minimize the objective of weighted flow time plus energy. Previously, strong lower bounds were shown on this model in the unweighted setting even when the algorithm is given a constant amount of resource augmentation over the optimal solution. However, these lower bounds were given only for certain families of algorithms that do not recognize the parallelizability of alive jobs. In this work, we circumvent previous lower bounds shown and give a scalable algorithm under the natural assumption that the algorithm can know the current parallelizability of a job. When a general power function is considered, this is also the first algorithm that has a constant competitive ratio for the problem using any amount of resource augmentation.

Online scheduling of parallelizable jobs has received a significant amount of attention recently. Scalable algorithms are known—that is, algorithms that are (1 + e)-speed O(1)-competitive for any fixed e>0. Previous research has focused on the case where each job’s parallelizability can be expressed as a concave speedup curve. However, there are cases where a job’s speedup curve can be convex. Considering convex speedup curves has received attention in the offline setting, but, to date, there are no positive results in the online model. In this work, we consider scheduling jobs with convex or concave speedup curves for the first time in the online setting. We give a new algorithm that is (1 + e)-speed O(1)-competitive. There are strong lower bounds on the competitive ratio if the algorithm is not given resource augmentation over the adversary, and thus this is essentially the best positive result one can show for this setting.

Many algorithms have been proposed to efficiently schedule parallel jobs on a multicore and/or multiprocessor machine to minimize average flow time, and the complexity of the problem is well understood. In practice, the problem is far from being understood. A reason for the gap between theory and practice is that all theoretical algorithms have prohibitive overheads in actual implementation including using many preemptions. One of the flagship successes of scheduling theory is the work-stealing scheduler. Work-stealing is used for optimizing the flow time of a single parallel job executing on a single machine with multiple cores and has a strong performance in theory and in practice. Consequently, it is implemented in almost all parallel runtime systems. This paper seeks to bridge theory and practice for scheduling parallel jobs that arrive online, by introducing an adaptation of the work-stealing scheduler for average flow time. The new algorithm Distributed Random Equi-Partition (DREP) has strong practical and theoretical performance. Practically, the algorithm has the following advantages: (1) it is non-clairvoyant; (2) all processors make scheduling decisions in a decentralized manner requiring minimal synchronization and communications; and (3) it requires a small and bounded number of preemptions. Theoretically, we prove that DREP is (4+e)-speed O(1/e^3)-competitive for average flow time. We have empirically evaluated DREP using both simulations and actual implementation by modifying the Cilk Plus work-stealing runtime system. The evaluation results show that DREP performs well compared to other scheduling strategies, including those that are theoretically good but cannot be faithfully implemented in practice.

Motivated by fundamental applications in databases and relational machine learning, we formulate and study the problem of answering functional aggregate queries (FAQ) in which some of the input factors are defined by a collection of additive inequalities between variables. We refer to these queries as FAQ-AI for short. To answer FAQ-AI in the Boolean semiring, we define relaxed tree decompositions and relaxed submodular and fractional hypertree width parameters. We show that an extension of the InsideOut algorithm using Chazelle's geometric data structure for solving the semigroup range search problem can answer Boolean FAQ-AI in time given by these new width parameters. This new algorithm achieves lower complexity than known solutions for FAQ-AI. It also recovers some known results in database query answering. Our second contribution is a relaxation of the set of polymatroids that gives rise to the counting version of the submodular width, denoted by #subw. This new width is sandwiched between the submodular and the fractional hypertree widths. Any FAQ and FAQ-AI over one semiring can be answered in time proportional to #subw and respectively to the relaxed version of #subw. We present three applications of our FAQ-AI framework to relational machine learning: k-means clustering, training linear support vector machines, and training models using non-polynomial loss. These optimization problems can be solved over a database asymptotically faster than computing the join of the database relations.

International audience

When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be incurred from the expensive task of saving the memory’s state or from loading data into and out of memory. Thus, it is desirable to schedule jobs non-preemptively to avoid the costs of preemption. There is a need for non-preemptive system schedulers for desktops, servers, and data centers. Despite this need, there is a gap between theory and practice. Indeed, few non-preemptive online schedulers are known to have strong theoretical guarantees. This gap is likely due to strong lower bounds on any online algorithm for popular objectives. Indeed, typical worst-case analysis approaches, and even resource-augmented approaches such as speed augmentation, result in all algorithms having poor performance guarantees. This article considers online non-preemptive scheduling problems in the worst-case rejection model where the algorithm is allowed to reject a small fraction of jobs. By rejecting only a few jobs, this article shows that the strong lower bounds can be circumvented. This approach can be used to discover algorithmic scheduling policies with desirable worst-case guarantees. Specifically, the article presents algorithms for the following three objectives: minimizing the total flow-time, minimizing the total weighted flow-time plus energy where energy is a convex function, and minimizing the total energy under the deadline constraints. The algorithms for the first two problems have a small constant competitive ratio while rejecting only a constant fraction of jobs. For the last problem, we present a constant competitive ratio without rejection. Beyond specific results, the article asserts that alternative models beyond speed augmentation should be explored to aid in the discovery of good schedulers in the face of the requirement of being online and non-preemptive.

A 4D broadband assessment has been performed in a deep offshore West Africa environment using repeated dual-sensor streamer acquisitions. Three sail lines have been re-acquired only a few weeks after the original acquisition with standard 4D acquisition consideration. The study has compared the data repeatability metric NRMS along the processing sequences using, on one side, a reconstructed band limited 4D data corresponding to a single hydrophone and on the other side an extended bandwidth 4D data using the up-going wavefield only. Because the datasets have been recorded using the same acquisition, the main differences come from the bandwidth discrepancy and the variable sea-state. The 4D “Up-going on Up-going” preserves, for all processing steps, around 1% NRMS benefit against the 4D hydrophone-only. Because the NRMS comparison is biased by the dominant frequency discrepancy, the 1% gain does not fully reflect the detectability advantage of the 4D broadband. The NRMS analysis on the low frequency part has demonstrated the clear improvement on 4D broadband and a qualitative evaluation on the 4D differences has highlighted the negative effect of the sea-state on the hydrophone-only 4D results.

Motivated by fundamental applications in databases and relational machine learning, we formulate and study the problem of answering functional aggregate queries (FAQ) in which some of the input factors are defined by a collection of additive inequalities between variables. We refer to these queries as FAQ-AI for short. To answer FAQ-AI in the Boolean semiring, we define relaxed tree decompositions and relaxed submodular and fractional hypertree width parameters. We show that an extension of the InsideOut algorithm using Chazelle’s geometric data structure for solving the semigroup range search problem can answer Boolean FAQ-AI in time given by these new width parameters. This new algorithm achieves lower complexity than known solutions for FAQ-AI. It also recovers some known results in database query answering. Our second contribution is a relaxation of the set of polymatroids that gives rise to the counting version of the submodular width, denoted by #subw. This new width is sandwiched between the submodular and the fractional hypertree widths. Any FAQ and FAQ-AI over one semiring can be answered in time proportional to #subw and respectively to the relaxed version of #subw. We present three applications of our FAQ-AI framework to relational machine learning: k -means clustering, training linear support vector machines, and training models using non-polynomial loss. These optimization problems can be solved over a database asymptotically faster than computing the join of the database relations.

We consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. A set of n jobs arrive online and each job Ji has an associated function pi(t), the profit obtained for finishing job Ji at time t. Each job has its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs showing O(1)-competitive algorithms using resource augmentation.

Modern science and engineering is driven by massively large data sets and its advance heavily relies on massively parallel computing platforms such as Spark, MapReduce, and Hadoop. Theoretical models have been proposed to understand the power and limitations of such platforms. Recent study of developed theoretical models has led to the discovery of new algorithms that are fast and efficient in both theory and practice, thereby beginning to unlock their underlying power. Given recent promising results, the area has turned its focus on discovering widely applicable algorithmic techniques for solving problems efficiently. In this paper we make progress towards this goal by giving a principled framework for simulating sequential dynamic programs in the distributed setting. In particular, we identify two key properties, monotonicity and decomposability, which allow us to derive efficient distributed algorithms for problems possessing the properties. We showcase our framework by considering several core dynamic programming applications, Longest Increasing Subsequence, Optimal Binary Search Tree, and Weighted Interval Selection. For these problems, we derive algorithms yielding solutions that are arbitrarily close to the optimum, using O(1) rounds and O(n/m) memory on each machine where n is the input size and m is the number of machines available.

In this paper we consider one of the most basic scheduling problems where jobs have their respective arrival times and deadlines. The goal is to schedule as many jobs as possible non-preemptively by their respective deadlines on m identical parallel machines. For the last decade, the best approximation ratio known for the single machine case (\(m = 1\)) has been \(1-1/e - \epsilon \approx 0.632\) due to [Chuzhoy-Ostrovsky-Rabani, FOCS 2001 and MOR 2006]. We break this barrier and give an improved 0.644-approximation. For the multiple machine case, we give an algorithm whose approximation guarantee becomes arbitrarily close to 1 as the number of machines increases. This improves upon the previous best \(1 - 1/(1 + 1/m)^m\) approximation due to [Bar-Noy et al., STOC 1999 and SICOMP 2009], which converges to \(1-1/e\) as m goes to infinity. Our result for the multiple-machine case extends to the weighted throughput objective where jobs have different weights, and the goal is to schedule jobs with the maximum total weight. Our results show that the \(1 - 1/e\) approximation factor widely observed in various coverage problems is not tight for the non-preemptive maximum throughput scheduling problem.

This paper considers the online machine minimization problem, a basic real time scheduling problem. The setting for this problem consists of n jobs that arrive over time, where each job has a deadline by which it must be completed. The goal is to design an online scheduler that feasibly schedules the jobs on a nearly minimal number of machines. An algorithm is c-machine optimal if the algorithm will feasibly schedule a collection of jobs on c ·m machines if there exists a feasible schedule on m machines. For over two decades the best known result was a O(log P)-machine optimal algorithm, where P is the ratio of the maximum to minimum job size. In a recent breakthrough, a O(log m)-machine optimal algorithm was given. In this paper, we exponentially improve on this recent result by giving a O(log log m)-machine optimal algorithm.

In this paper we consider the power of migration in heterogeneous machines settings and general profit scheduling. We begin by showing that on related machines or on related machines with restricted assignment that any migratory algorithm can be simulated by a non-migratory algorithm given 1+e speed augmentation and O(1/e) and O(1/e2) machine augmentation, respectively, for any 0 0 when compared against a non-migratory adversary. Previous results were only known in the identical machines setting. As an example of the usefulness of the previous results on migration, they with the results on genial profit scheduling give a (1+e)-speed O(1/e4)-competitive algorithm for general profit scheduling when comparing against a migratory algorithm on related machines with restricted assignment for any e >0.

In this article, the online pull-based broadcast model is considered. In this model, there are n pages of data stored at a server and requests arrive for pages online. When the server broadcasts page p , all outstanding requests for the same page p are simultaneously satisfied. We consider the problem of minimizing average (total) flow time online where all pages are unit-sized. For this problem, there has been a decade-long search for an online algorithm which is scalable, that is, (1 + ϵ)-speed O (1)-competitive for any fixed ϵ > 0. In this article, we give the first analysis of an online scalable algorithm.

We consider speed scaling problems where the objective is to minimize a linear combination of arbitrary scheduling objective S , and energy E . A natural conjecture is that there is an O ( 1 ) -competitive algorithm for S on a fixed speed processor if and only if there is an O ( 1 ) -competitive algorithm for S + E on a processor with an arbitrary power function. We give evidence to support this conjecture by providing an O ( 1 ) -competitive algorithm for the objective of integer stretch plus energy.

This paper presents several online scheduling algorithms for two related perfor- mance metrics, namely maximum response time and maximum delay-factor, and also their weighted versions. The delay factor metric is new (introduced in Chang et al. (SODA'08)), while special cases of maximum weighted response time have been considered before. We study both the standard scheduling model where each arriving job requires its own pro- cessing, as well as the broadcast scheduling model where multiple requests/jobs can be simultaneously satisfied. Motivated by strong lower bounds, we consider the resource augmentation model intro- duced in Kalyanasundaram and Pruhs (JACM'95) where the algorithm is given a machine with faster speed than the adversary. We give scalable algorithms; that is, algorithms that when given (1+e)-speed are O(poly(1=e))-competitive for any fixed e > 0. Our main contributions are for broadcast scheduling. Along the way we also show that the FIFO (first-in-first-out) algorithm is 2-competitive for broadcast scheduling even when pages have non-uniform sizes. We complement our algorithmic results by showing that a natural greedy

In recent work we quantified the anticipated performance boost when a sorting algorithm is modified to leverage user-addressable "near-memory," which we call scratchpad. This architectural feature is expected in the Intel Knight's Landing processors that will be used in DOE's next large-scale supercomputer. This paper expands our analytical study of the scratchpad to consider k-means clustering, a classical data-analysis technique that is ubiquitous in the literature and in practice. We present new theoretical results using the model introduced in [13], which measures memory transfers and assumes that computations are memory-bound. Our theoretical results indicate that scratchpad-aware versions of k-means clustering can expect performance boosts for high-dimensional instances with relatively few cluster centers. These constraints may limit the practical impact of scratch-pad for k-means acceleration, so we discuss their origins and practical implications. We corroborate our theory with experimental runs on a system instrumented to mimic one with scratchpad memory. We also contribute a semi-formalization of the computational properties that are necessary and sufficient to predict a performance boost from scratchpad-aware variants of algorithms. We have observed and studied these properties in the context of sorting, and now clustering. We conclude with some thoughts on the application of these properties to new areas. Specifically, we believe that dense linear algebra has similar properties to k-means, while sparse linear algebra and FFT computations are more similar to sorting. The sparse operations are more common in scientific computing, so we expect scratchpad to have significant impact in that area.

Fairness is an important criterion considered in scheduling together with overall job latency. Round Robin is a popular scheduling policy that distributes resources to jobs equally at any point in time guaranteeing instantaneous fairness of jobs. In this paper we give the first analysis of Round Robin for the L_2-norm of flow time and show that it is O(1)-speed O(1)-competitive on multiple machines. The L_2-norm is a popular scheduling objective that makes a natural balance between temporal fairness and jobs latency. Prior to our work, Round Robin has not been analyzed for the L_2-norm even in the single machine setting. Our result establishes that Round Robin is fair not only instantaneously but also temporarily.

In this paper we introduce a new network scheduling model. Here jobs need to be sent via routers on a tree to machines to be scheduled, and the communication is constrained by network bandwidth. The scheduler coordinates network communication and job machine scheduling. This type of scheduler is highly desirable in practice; yet few works have considered combing networking with job processing. We consider the popular objective of total flow time in the online setting. We give a (1+e)-speed O(1/e7)-competitive algorithm when all routers are identical and all machines are identical for any fixed e >0. Then we go on to show a (2+e)-speed O(1/e7)-competitive algorithm when the routers are identical and the machines are unrelated. To show these results we introduce an interesting combination of potential function and dual fitting techniques as well as a reduction of general tree scheduling to a special case of trees.

As the signal to noise response of conventional acquisition systems has improved, vendors have developed technologies aimed at using signal processing to mitigate the effects of the source and receiver ghosts. In 2012, a 3D exploration survey with 9m receiver tow depth and a single repeat sail-line using an 18m receiver tow depth was acquired offshore Namibia by Polarcus on behalf of Serica Energy and their coventurers, BP and NAMCOR. BP asked three vendors to process the 18m tow repeat sail-line and the nearest shot line extracted from the 9m tow dataset with both their conventional and pre-stack broadband processing sequences. In this paper we evaluate the results. All the vendor broadband workflows were successful in recovering signal in the receiver notches, and the resulting datasets all showed an increase in bandwidth. However, the evaluation also revealed large differences in phase behaviour between the vendors’ results, underlining the importance of phase corrections when broadband processing.

Much current interest in the field of broadband marine seismic is towards employing processing solutions to attenuate the effect of the sea surface ghost. Whilst focus is towards application in the pre-stack domain, our development of a 1-D based post-stack broadband processing workflow has shown it to be a feasible technique for achieving broader bandwidth data. Such a method allows a simple and efficient resolution improvement, particularly for legacy datasets, where pre-stack data is not available. Here we show examples of post-stack broadband processing to full stack data and discuss the benefits and limitations of broadband processing in the post-stack domain.

A challenge in computer architecture is that processors often cannot be fed data from DRAM as fast as CPUs can consume it. Therefore, many applications are memory-bandwidth bound. With this motivation and the realization that traditional architectures (with all DRAM reachable only via bus) are insufficient to feed groups of modern processing units, vendors have introduced a variety of non-DDR 3D memory technologies (Hybrid Memory Cube (HMC),Wide I/O 2, High Bandwidth Memory (HBM)). These offer higher bandwidth and lower power by stacking DRAM chips on the processor or nearby on a silicon interposer. We will call these solutions "near-memory," and if user-addressable, "scratchpad." High-performance systems on the market now offer two levels of main memory: near-memory on package and traditional DRAM further away. In the near term we expect the latencies near-memory and DRAM to be similar. Thus, it is natural to think of near-memory as another module on the DRAM level of the memory hierarchy. Vendors are expected to offer modes in which the near memory is used as cache, but we believe that this will be inefficient.In this paper, we explore the design space for a user-controlled multi-level main memory. Our work identifies situations in which rewriting application kernels can provide significant performance gains when using near-memory. We present algorithms designed for two-level main memory, using divide-and-conquer to partition computations and streaming to exploit data locality. We consider algorithms for the fundamental application of sorting and for the data analysis kernel k -means. Our algorithms asymptotically reduce memory-block transfers under certain architectural parameter settings. We use and extend Sandia National Laboratories' SST simulation capability to demonstrate the relationship between increased bandwidth and improved algorithmic performance. Memory access counts from simulations corroborate predicted performance improvements for our sorting algorithm. In contrast, the k -means algorithm is generally CPU bound and does not improve when using near-memory except under extreme conditions. These conditions require large instances that rule out SST simulation, but we demonstrate improvements by running on a customized machine with high and low bandwidth memory. These case studies in co-design serve as positive and cautionary templates, respectively, for the major task of optimizing the computational kernels of many fundamental applications for two-level main memory systems. Emerging architectures feature high-bandwidth scratchpad memory that is not cache.We adapt a classical external-memory model to this context.We design and analyze algorithms for sorting and k-means using this model.We validate our predictions with simulation and/or a custom machine.

Reordering buffer management (RBM) is an elegant theoretical model that captures the tradeoff between buffer size and switching costs for a variety of reordering/sequencing problems. In this problem, colored items arrive over time, and are placed in a buffer of size \(k\). When the buffer becomes full, an item must be removed from the buffer. A penalty cost is incurred each time the sequence of removed items switches colors. In the non-uniform cost model, there is a weight \(w_c\) associated with each color \(c\), and the cost of switching to color \(c\) is \(w_c\). The goal is to minimize the total cost of the output sequence, using the buffer to rearrange the input sequence.

We introduce a scheduling algorithm Intermediate-SRPT, and show that it is O (log P )-competitive with respect to average flow time when scheduling jobs whose parallelizability is intermediate between being fully parallelizable and sequential. Here, the parameter P denotes the ratio between the maximum job size to the minimum. We also show a general matching lower bound on the competitive ratio. Our analysis builds on an interesting combination of potential function and local competitiveness arguments.

We initiate a competitive analysis of packet forwarding policies for maximum and average flow in a line network. We show that the policies Earliest Arrival and Furthest-To-Go are scalable, but not constant competitive, for maximum flow. We show that there is no constant competitive algorithm for average flow.

Batch scheduling gives a powerful way of increasing the throughput by aggregating multiple homogeneous jobs. It has applications in large scale manufacturing as well as in server scheduling. In batch scheduling, when explained in the setting of server scheduling, the server can process requests of the same type up to a certain number simultaneously. Batch scheduling can be seen as capacitated broadcast scheduling, a popular model considered in scheduling theory. In this paper, we consider an online batch scheduling model. For this model we address flow time objectives for the first time and give positive results for average flow time, the k-norms of flow time and maximum flow time. For average flow time and the k-norms of flow time we show algorithms that are O(1)-competitive with a small constant amount of resource augmentation. For maximum flow time we show a 2-competitive algorithm and this is the best possible competitive ratio for any online algorithm.

Greedy algorithms are practitioners' best friends - they are intuitive, simple to implement, and often lead to very good solutions. However, implementing greedy algorithms in a distributed setting is challenging since the greedy choice is inherently sequential, and it is not clear how to take advantage of the extra processing power.Our main result is a powerful sampling technique that aids in parallelization of sequential algorithms. We then show how to use this primitive to adapt a broad class of greedy algorithms to the MapReduce paradigm; this class includes maximum cover and submodular maximization subject to p-system constraints. Our method yields efficient algorithms that run in a logarithmic number of rounds, while obtaining solutions that are arbitrarily close to those produced by the standard sequential greedy algorithm. We begin with algorithms for modular maximization subject to a matroid constraint, and then extend this approach to obtain approximation algorithms for submodular maximization subject to knapsack or p-system constraints. Finally, we empirically validate our algorithms, and show that they achieve the same quality of the solution as standard greedy algorithms but run in a substantially fewer number of rounds.

We consider computing optimal k-norm preemptive schedules of jobs that arrive over time. In particular, we show that computing the optimal k-norm of flow schedule, 1 |rj, pmtn |∑j (Cj−rj)k in standard 3-field scheduling notation, is strongly NP-hard for k∈(0, 1) and integers k∈(1,∞). Further we show that computing the optimal k-norm of stretch schedule, 1 |rj, pmtn |∑j ((Cj−rj)/pj)k in standard 3-field scheduling notation, is strongly NP-hard for k∈(0, 1) and integers k∈∪(1,∞).

Benjamin Moseley (1742–1819) was an English doctor who left England and spent eighteen years working in Kingston, Jamaica. His time there coincided with the massive expansion of sugar production on the island. Drawing on his own experience as well as an extensive range of classical and contemporary published sources, Moseley presents a lively history of the cultivation and use of sugar cane. The work, first published in 1799 and expanded in this second edition in 1800, discusses the origins of the plant and its later cultivation and development in the Americas, as well as the popularity of refined sugar. Special attention is devoted to the plant's medicinal uses. Moseley also became known for his outspoken opposition to the growing practice of vaccination, and he uses a medical essay in the appendix of this book to launch an attack on the effectiveness of cowpox in inoculations.

Most of the online advertising today is sold via an auction, which requires the advertiser to respond with a valid bid within a fraction of a second. As such, most advertisers employ bidding agents to submit bids on their behalf. The architecture of such agents typically has (1) an offline optimization phase which incorporates the bidder's knowledge about the market and (2) an online bidding strategy which simply executes the offline strategy. The online strategy is typically highly dependent on both supply and expected price distributions, both of which are forecast using traditional machine learning methods. In this work we investigate the optimum strategy of the bidding agent when faced with incorrect forecasts. At a high level, the agent can invest resources in improving the forecasts, or can tighten the loop between successive offline optimization cycles in order to detect errors more quickly. We show analytically that the latter strategy, while simple, is extremely effective in dealing with forecast errors, and confirm this finding with experimental evaluations.

Over half a century old and showing no signs of aging, k-means remains one of the most popular data processing algorithms. As is well-known, a proper initialization of k-means is crucial for obtaining a good final solution. The recently proposed k-means++ initialization algorithm achieves this, obtaining an initial set of centers that is provably close to the optimum solution. A major downside of the k-means++ is its inherent sequential nature, which limits its applicability to massive data: one must make k passes over the data to find a good initial set of centers. In this work we show how to drastically reduce the number of passes needed to obtain, in parallel, a good initialization. This is unlike prevailing efforts on parallelizing k-means that have mostly focused on the post-initialization phases of k-means. We prove that our proposed initialization algorithm k-means|| obtains a nearly optimal solution after a logarithmic number of passes, and then show that in practice a constant number of passes suffices. Experimental evaluation on real-world large-scale data demonstrates that k-means|| outperforms k-means++ in both sequential and parallel settings., Comment: VLDB2012