BACKGROUND: Drug combinations have the potential to improve efficacy while limiting toxicity. To robustly identify synergistic combinations, high-throughput screens using full dose-response surface are desirable but require an impractical number of data points. Screening of a sparse number of doses per drug allows to screen large numbers of drug pairs, but complicates statistical assessment of synergy. Furthermore, since the number of pairwise combinations grows with the square of the number of drugs, exploration of large screens necessitates advanced visualization tools. RESULTS: We describe a statistical and visualization framework for the analysis of large-scale drug combination screens. We developed an approach suitable for datasets with large number of drugs pairs even if small number of data points are available per drug pair. We demonstrate our approach using a systematic screen of all possible pairs among 108 cancer drugs applied to melanoma cell lines. In this dataset only two dose-response data points per drug pair and two data points per single drug test were available. We used a Bliss-based linear model, effectively borrowing data from the drug pairs to obtain robust estimations of the singlet viabilities, consequently yielding better estimates of drug synergy. Our method improves data consistency across dosing thus likely reducing the number of false positives. The approach allows to compute p values accounting for standard errors of the modeled singlets and combination viabilities. We further develop a synergy specificity score that distinguishes specific synergies from those arising with promiscuous drugs. Finally, we developed a summarized interactive visualization in a web application, providing efficient access to any of the 439,000 data points in the combination matrix ( http://www.cmtlab.org:3000/combo_app.html ). The code of the analysis and the web application is available at https://github.com/arnaudmgh/synergy-screen . CONCLUSIONS: We show that statistical modeling of single drug response from drug combination data can help determine significance of synergy and antagonism in drug combination screens with few data point per drug pair. We provide a web application for the rapid exploration of large combinatorial drug screen. All codes are available to the community, as a resource for further analysis of published data and for analysis of other drug screens.

At Google, the quality and speed of statistical data mining algorithms directly affects the usefulness of our search results and the relevance of our targeted advertising. One of the things that makes planet-wide, high throughput, 24/7 data mining so interesting is that all parts of the software stack are involved. This talk will walk up the stack, from the physical machines in warehouse-sized data centers, through networking and secondary storage abstractions to the distributed numerical methods and high throughput training and serving algorithms needed to support online logs processing and machine learning. We will also discuss the significant infrastructure and algorithmic impacts of batch versus online training: both data mining modes have essential roles in Google.

Analyzing gene expression data from microarray devices has many important application in medicine and biology, but presents significant challenges to data mining. Microarray data typically has many attributes (genes) and few examples (samples), making the process of correctly analyzing such data difficult to formulate and prone to common mistakes. For this reason it is unusually important to capture and record good practices for this form of data mining. This paper presents a process for analyzing microarray data, including pre-processing, gene selection, randomization testing, classification and clustering; this process is captured with "Clementine Application Templates". The paper describes the process in detail and includes three case studies, showing how the process is applied to 2-class classification, multi-class classification and clustering analyses for publicly available microarray datasets.

In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its kth nearest neighbor. We rank each point on the basis of its distance to its kth nearest neighbor and declare the top n points in this ranking to be outliers. In addition to developing relatively straightforward solutions to finding such outliers based on the classical nested-loop join and index join algorithms, we develop a highly efficient partition-based algorithm for mining outliers. This algorithm first partitions the input data set into disjoint subsets, and then prunes entire partitions as soon as it is determined that they cannot contain outliers. This results in substantial savings in computation. We present the results of an extensive experimental study on real-life and synthetic data sets. The results from a real-life NBA database highlight and reveal several expected and unexpected aspects of the database. The results from a study on synthetic data sets demonstrate that the partition-based algorithm scales well with respect to both data set size and data set dimensionality.

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex aggregate queries based on statistical summaries of the full data. In this paper, we demonstrate the difficulty of providing good approximate answers for join-queries using only statistics (in particular, samples) from the base relations. We propose join synopses as an effective solution for this problem and show how precomputing just one join synopsis for each relation suffices to significantly improve the quality of approximate answers for arbitrary queries with foreign key joins. We present optimal strategies for allocating the available space among the various join synopses when the query work load is known and identify heuristics for the common case when the work load is not known. We also present efficient algorithms for incrementally maintaining join synopses in the presence of updates to the base relations. Our extensive set of experiments on the TPC-D benchmark database show the effectiveness of join synopses and various other techniques proposed in this paper.

Selectivity estimation of queries is an important and well-studied problem in relational database systems. In this paper, we examine selectivity estimation in the context of Geographic Information Systems, which manage spatial data such as points, lines, poly-lines and polygons. In particular, we focus on point and range queries over two-dimensional rectangular data. We propose several techniques based on using spatial indices, histograms, binary space partitionings (BSPs), and the novel notion of spatial skew. Our techniques carefully partition the input rectangles into subsets and approximate each partition accurately. We present a detailed experimental study comparing the proposed techniques and the best known sampling and parametric techniques. We evaluate them using synthetic as well as real-life TIGER datasets. Based on our experiments, we identify a BSP based partitioning that we call Min-Skew which consistently provides the most accurate selectivity estimates for spatial queries. The Min-Skew partitioning can be constructed efficiently, occupies very little space, and provides accurate selectivity estimates over a broad range of spatial queries.

The World Wide Web is rapidly emerging as an important medium for transacting commerce as well as for the dissemination of information related to a wide range of topics (e.g., business, government, recreation). According to most predictions, the majority of human information will be available on the Web in ten years. These huge amounts of data raise a grand challenge for the database community, namely, how to turn the Web into a more useful information utility. This is exactly the subject that will be addressed by this panel.

We study the problem of discovering association rules that display regular cyclic variation over time. For example, if we compute association rules over monthly sales data, we may observe seasonal variation where certain rules are true at approximately the same month each year. Similarly, association rules can also display regular hourly, daily, weekly, etc., variation that is cyclical in nature. We demonstrate that existing methods cannot be naively extended to solve this problem of cyclic association rules. We then present two new algorithms for discovering such rules. The first one, which we call the sequential algorithm, treats association rules and cycles more or less independently. By studying the interaction between association rules and time, we devise a new technique called cycle pruning, which reduces the amount of time needed to find cyclic association rules. The second algorithm, which we call the interleaved algorithm, uses cycle pruning and other optimization techniques for discovering cyclic association rules. We demonstrate the effectiveness of the interleaved algorithm through a series of experiments. These experiments show that the interleaved algorithm can yield significant performance benefits when compared to the sequential algorithm. Performance improvements range from 5% to several hundred percent.

Indexing a class hierarchy, in order to efficiently search or update the objects of a class according to a (range of) value(s) of an attribute, impacts OODB performance heavily. For this indexing problem, most systems use the class hierarchy index (CH) technique of [15] implemented using B+-trees. Other techniques, such as those of [14, 18,31], can lead to improved average-case performance but involve the implementation of new data-structures. As a special form of external dynamic two-dimensional range searching, this OODB indexing problem is solvable within reasonable worst-case bounds [12]. Based on this insight, we have developed a technique, called indexing by class-division (CD), which we believe can be used as a practical alternative to CH. We present an optimized implementation and experimental validation of CD's average-case performance. The main advantages of the CD technique are: (1) CD is an extension of CH that provides a significant speed-up over CH for a wide spectrum of range queries--this speed-up is at least linear in the number of classes queried for uniform data and larger otherwise; and (2) CD queries, updates and concurrent use are implementable using existing B+-tree technology. The basic idea of class-division involves a time-space tradeoff and CD requires some space and update overhead in comparison to CH. In practice, this overhead is a small factor (2 to 3) and, in worst-case, is bounded by the depth of the hierarchy and the logarithm of its size.

External 2-dimensional searching is a fundamental problem with many applications in relational, object-oriented, spatial, and temporal databases. For example, interval intersection can be reduced to 2-sided, 2-dimensional searching and indexing class hierarchies of objects to 3-sided, 2-dimensional searching. Path caching is a new technique that can be used to transform a number of time/space efficient data structures for internal 2-dimensional searching (such as segment trees, interval trees, and priority search trees) into I/O efficient external ones. Let n be the size of the database, B the page size, and t the output size of a query. Using path caching, we provide the first data structure with optimal I/O query time O(logBn+t/B) for 2-sided, 2-dimensional searching. Furthermore, we show that path caching requires a small space overhead O(n÷Blog2log2B) and is simple enough to admit dynamic updates in optimal O(logBn) amortized time. We also extend this data structure to handle 3-sided, 2-dimensional searching with optimal I/O query-time, at the expense of slightly higher storage and update overheads.

We examine I/O-efficient data structures that provide indexing support for new data models. The database languages of these models include concepts from constraint programming (e.g., relational tuples are generalized to conjunctions of constraints) and from object-oriented programming (e.g., objects are organized in class hierarchies). Let n be the size of the database, c the number of classes, B the secondary storage page size, and t the size of the output of a query. Indexing by one attribute in the constraint data model (for a fairly general type of constraints) is equivalent to external dynamic interval management, which is a special case of external dynamic 2-dimensional range searching. We present a semi-dynamic data structure for this problem which has optimal worst-case space O(n/B) pages and optimal query I/O time O(logBn+t/B) and has O(logBn+(log2Bn)/B) amortized insert I/O time. If the order of the insertions is random then the expected number of I/O operations needed to perform insertions is reduced to O(logBn). Indexing by one attribute and by class name in an object-oriented model, where objects are organized as a forest hierarchy of classes, is also a special case of external dynamic 2-dimensional range searching. Based on this observation we first identify a simple algorithm with good worst-case performance for the class indexing problem. Using the forest structure of the class hierarchy and techniques from the constraint indexing problem, we improve its query I/O time from O(log2c logBn + t/B) to O(logB + log2B).