Identifying the extremal (minimal and maximal) sets from a collection of sets is an important subproblem in the areas of data-mining and satisfiability checking. For example, extremal set finding algorithms are used in the context of mining maximal frequent itemsets, and for simplifying large propositional satisfiability instances derived from real world tasks such as circuit routing and verification. In this paper, we describe two new algorithms for the task and detail their performance on real and synthetic data. Each algorithm leverages an entirely different principle – one primarily exploits set cardinality constraints, the other lexicographic constraints. Despite the inherent difficulty of this problem (the best known worst-case bounds are nearly quadratic), we show that both these algorithms provide excellent performance in practice, and can identify all extremal sets from multi-gigabyte itemset data using only a single processor core. Both algorithms are concise and can be implemented in no more than a few hundred lines of code. Our reference C++ implementations are open source and available for download.

This paper explores an important and relatively unstudied quality measure of a sponsored search advertisement: bounce rate. The bounce rate of an ad can be informally defined as the fraction of users who click on the ad but almost immediately move on to other tasks. A high bounce rate can lead to poor advertiser return on investment, and suggests search engine users may be having a poor experience following the click. In this paper, we first provide quantitative analysis showing that bounce rate is an effective measure of user satisfaction. We then address the question, can we predict bounce rate by analyzing the features of the advertisement? An affirmative answer would allow advertisers and search engines to predict the effectiveness and quality of advertisements before they are shown. We propose solutions to this problem involving large-scale learning methods that leverage features drawn from ad creatives in addition to their keywords and landing pages.

Classification and regression tree learning on massive datasets is a common data mining task at Google, yet many state of the art tree learning algorithms require training data to reside in memory on a single machine. While more scalable implementations of tree learning have been proposed, they typically require specialized parallel computing architectures. In contrast, the majority of Google's computing infrastructure is based on commodity hardware. In this paper, we describe PLANET: a scalable distributed framework for learning tree models over large datasets. PLANET defines tree learning as a series of distributed computations, and implements each one using the MapReduce model of distributed computation. We show how this framework supports scalable construction of classification and regression trees, as well as ensembles of such models. We discuss the benefits and challenges of using a MapReduce compute cluster for tree learning, and demonstrate the scalability of this approach by applying it to a real world learning task from the domain of computational advertising.

Given a large collection of sparse vector data in a high dimensional space, we investigate the problem of finding all pairs of vectors whose similarity score (as determined by a function such as cosine distance) is above a given threshold. We propose a simple algorithm based on novel indexing and optimization strategies that solves this problem without relying on approximation methods or extensive parameter tuning. We show the approach efficiently handles a variety of datasets across a wide setting of similarity thresholds, with large speedups over previous state-of-the-art approaches.

No abstract available.

Data de-identification reconciles the demand for release of data for research purposes and the demand for privacy from individuals. This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization. A k-anonymized dataset has the property that each record is indistinguishable from at least k - 1 others. Even simple restrictions of optimized k-anonymity are NP-hard, leading to significant computational challenges. We present a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develop data-management strategies to reduce reliance on expensive operations such as sorting. Through experiments on real census data, we show the resulting algorithm can find optimal k-anonymizations under two representative cost measures and a wide range of k. We also show that the algorithm can produce good anonymizations in circumstances where the input data or input parameters preclude finding an optimal solution in reasonable time. Finally, we use the algorithm to explore the effects of different coding approaches and problem variations on anonymization quality and performance. To our knowledge, this is the first result demonstrating optimal k-anonymization of a non-trivial dataset under a general model of the problem.

This paper provides an objective evaluation of the performance impacts of binary XML encodings, using a fast stream-based XQuery processor as our representative application. Instead of proposing one binary format and comparing it against standard XML parsers, we investigate the individual effects of several binary encoding techniques that are shared by many proposals. Our goal is to provide a deeper understanding of the performance impacts of binary XML encodings in order to clarify the ongoing and often contentious debate over their merits, particularly in the domain of high performance XML stream processing.

Personal webservers have proven to be a popular means of sharing files and peer collaboration. Unfortunately, the transient availability and rapidly evolving content on such hosts render centralized, crawl-based search indices stale and incomplete. To address this problem, we propose YouSearch, a distributed search application for personal webservers operating within a shared context (e.g., a corporate intranet). With YouSearch, search results are always fast, fresh and complete -- properties we show arise from an architecture that exploits both the extensive distributed resources available at the peer webservers in addition to a centralized repository of summarized network state. YouSearch extends the concept of a shared context within web communities by enabling peers to aggregate into groups and users to search over specific groups. In this paper, we describe the challenges, design, implementation and experiences with a successful intranet deployment of YouSearch.

YouServ is a system that allows its users to pool existing desktop computing resources for high availability web hosting and file sharing. By exploiting standard web and internet protocols (e.g. HTTP and DNS), YouServ does not require those who access YouServ-published content to install special purpose software. Because it requires minimal server-side resources and administration, YouServ can be provided at a very low cost. We describe the design, implementation, and a successful intranet deployment of the YouServ system, and compare it with several alternatives.

Article Share on Vinci: a service-oriented architecture for rapid development of web applications Authors: Rakesh Agrawal IBM Almaden Research Center, 650 Harry Road, San Jose, CA IBM Almaden Research Center, 650 Harry Road, San Jose, CAView Profile , Roberto J. Bayardo IBM Almaden Research Center, 650 Harry Road, San Jose, CA IBM Almaden Research Center, 650 Harry Road, San Jose, CAView Profile , Daniel Gruhl IBM Almaden Research Center, 650 Harry Road, San Jose, CA IBM Almaden Research Center, 650 Harry Road, San Jose, CAView Profile , Spiros Papadimitriou Carnegie Mellon University, Dept. of Computer Science and IBM Almaden Research Center, 650 Harry Road, San Jose, CA Carnegie Mellon University, Dept. of Computer Science and IBM Almaden Research Center, 650 Harry Road, San Jose, CAView Profile Authors Info & Claims WWW '01: Proceedings of the 10th international conference on World Wide WebMay 2001Pages 355–365https://doi.org/10.1145/371920.372088Published:01 April 2001Publication History 24citation2,443DownloadsMetricsTotal Citations24Total Downloads2,443Last 12 Months6Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Constraint-based rule miners find all rules in a given dataset meeting user-specified constraints such as minimum support and confidence. We describe a new algorithm that directly exploits all user-specified constraints including minimum support, minimum confidence, and a new constraint that ensures every mined rule offers a predictive advantage over any of its simplifications. Our algorithm maintains efficiency even at low supports on data that is dense (e.g. relational data). Previous approaches such as Apriori and its variants exploit only the minimum support constraint, and as a result are ineffective on dense data date to a combinatorial explosion of "frequent itemsets".

Several algorithms have been proposed for finding the “best, ” “optimal,” or “most interesting ” rule(s) in a database according to a variety of metrics including confidence, support, gain, chi-squared value, gini, entropy gain, laplace, lift, and conviction. In this paper, we show that the best rule according to any of these metrics must reside along a support/confidence border. Further, in the case of conjunctive rule mining within categorical data, the number of rules along this border is conveniently small, and can be mined efficiently from a variety of real-world data-sets. We also show how this concept can be generalized to mine all rules that are best according to any of these criteria with respect to an arbitrary subset of the population of interest. We argue that by returning a broader set of rules than previous algorithms, our techniques allow for improved insight into the data and support more user-interaction in the optimized rule-mining process. 1.

We present a pattern-mining algorithm that scales roughly linearly in the number of maximal patterns embedded in a database irrespective of the length of the longest pattern. In comparison, previous algorithms based on Apriori scale exponentially with longest pattern length. Experiments on real data show that when the patterns are long, our algorithm is more efficient by an order of magnitude or more.

The goal of the InfoSleuth project at MCC is to exploit and synthesize new technologies into a unified system that retrieves and processes information in an ever-changing network of information sources. InfoSleuth has its roots in the Carnot project at MCC, which specialized in integrating heterogeneous information bases. However, recent emerging technologies such as internetworking and the World Wide Web have significantly expanded the types, availability, and volume of data available to an information management system. Furthermore, in these new environments, there is no formal control over the registration of new information sources, and applications tend to be developed without complete knowledge of the resources that will be available when they are run. Federated database projects such as Carnot that do static data integration do not scale up and do not cope well with this ever-changing environment. On the other hand, recent Web technologies, based on keyword search engines, are scalable but, unlike federated databases, are incapable of accessing information based on concepts. In this experience paper, we describe the architecture, design, and implementation of a working version of InfoSleuth. We show how InfoSleuth integrates new technological developments such as agent technology, domain ontologies, brokerage, and internet computing, in support of mediated interoperation of data and services in a dynamic and open environment. We demonstrate the use of information brokering and domain ontologies as key elements for scalability.

Article Free Access Share on The InfoSleuth Project Authors: R. J. Bayardo Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , W. Bohrer Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , R. Brice Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , A. Cichocki Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , J. Fowler Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , A. Halal Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , V. Kashyap Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , T. Ksiezyk Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , G. Martin Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , M. Nodine Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , M. Rashid Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , M. Rusinkiewicz Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , R. Shea Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , C. Unnikrishnan Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , A. Unruh Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile , D. Woelk Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, Texas Microelectronics and Computer Technology Corporation (MCC), 3500 West Balcones Center Drive, Austin, TexasView Profile Authors Info & Claims SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of dataJune 1997 Pages 543–545https://doi.org/10.1145/253260.253401Online:01 June 1997Publication History 7citation339DownloadsMetricsTotal Citations7Total Downloads339Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Special support for quickly finding the first-few answers of a query is atready appearing in commercial database systems.This support is useful in active databases,when dealing with potentially unmanageable query results, and as a declarative akernativeto navigational techniques.In this paper, wediscuss query processing techniques for first-answer queries.We provide a method for predicting the cost of a first-answer query plan under an execution model that attempts to reduce wasted effort in join pipelining.We define new statistics necessary for accurate cost prediction, and discuss techniques for obtaining the statistics through traditional statistical measures (e.g.selectivity) and semantic data properties commonly specified through modem 00DB and relatiorud schemas.The proposed techniques also apply to all-answer query processing when optimizing for fast delivery of the initiat query results.

We describe a purely declarative method for introducing modularity into forward-chaining, rule-based languages and its embodiment in the Venus rule language. The method is enforced by the syntax of the language and includes the ability to parameterize the rule groups. Drawing from two of three Venus applications developed to date, we illustrate how this form of modularity contributes directly to the resolution of certain software engineering problems associated with rule languages.>