Access to diverse perspectives nurtures an informed citizenry. Google and Bing have emerged as the duopoly that largely arbitrates which English-language documents are seen by web searchers. We present our empirical study over the search results produced by Google and Bing that shows a large overlap. Thus, citizens may not gain different perspectives by simultaneously probing them for the same query. Fortunately, our study also shows that by mining Twitter data, one can obtain search results that are quite distinct from those produced by Google, Bing, and Bing News. Additionally, the users found those results to be quite informative. We also present two novel tools we designed for this study. One uses tensor analysis to derive low-dimensional compact representation of search results and study their behavior over time. The other uses machine learning and quantifies the similarity of results between two search engines by framing it as a prediction problem. Although these tools have different underpinnings, the analytical results obtained using them corroborate each other, which reinforces the confidence one can place in them for finding meaningful insights from big data.

A program of study can be viewed as a knowledge graph consisting of learning units and relationships between them. Such a knowledge graph provides the core data structure for organizing and navigating learning experiences. We address three issues in this talk. First, how can we synthesize the knowledge graph, given a set of concepts to be covered in the study program. Next, how can we use data mining to identify and correct deficiencies in a knowledge graph. Finally, how can we use data mining to form study groups with the goal of maximizing overall learning. We conclude by pointing out some open research problems.

Without question, astounding advances in storage, communication, and computation have propelled us into a new world, the world of Big Data. The Big Data enthusiasts believe that it is a revolution that will transform how we live, work, and think, and it will underpin new waves of innovation and productivity growth.

Asia is in the midst of a historic transformation. Asia's per capita income is projected to rise sixfold and its share of global gross domestic product is expected to increase to 52 percent by 2050 [1]. Science and technology has been cited as one of the key pillars for the success of Asia's development [2].

Access to diverse perspectives nurtures an informed citizenry. Google and Bing have emerged as the duopoly that largely arbitrates which English language documents are seen by web searchers. A recent study shows that there is now a large overlap in the top organic search results produced by them. Thus, citizens may no longer be able to gain different perspectives by using different search engines.

The rapid proliferation of hand-held devices has led to the development of rich, interactive and immersive applications, such as e-readers for electronic books. These applications motivate retrieval systems that can implicitly satisfy any information need of the reader by exploiting the context of the user's interactions. Such retrieval systems differ from traditional search engines in that the queries constructed using the context are typically complex objects (including the document and its structure).

Given a class of large number of students, each exhibiting a different ability level, how can we group them into sections so that the overall gain for students is maximized? This question has been a topic of central concern and debate amongst social scientists and policy makers for a long time. We propose a framework for rigorously studying this question, taking a computational perspective. We present a formal definition of the grouping problem and investigate some of its variants. Such variants are determined by the desired number of groups as well as the definition of the gain for each student in the group. We focus on two natural instantiations of the gain function and we show that for both of them the problem of identifying a single group of students that maximizes the gain among its members can be solved in polynomial time. The corresponding partitioning problem, where the goal is to partition the students into non-overlapping groups appear to be much harder. However, the algorithms for the single-group version can be leveraged for solving the more complex partitioning problem. Our experiments with generated data coming from different distributions demonstrate that our algorithm is significantly better than the current strategies in vogue for dividing students in a class into sections.

Given a class of large number of students, each exhibiting a different ability level, how can we form teams of students so that the expected performance of team members improves due to team participation? We take a computational perspective and formally define two versions of such team-formation problem: the MAXTEAM and the MAXPARTITION problems. The first asks for the identification of a single team of students that improves the performance of most of the participating team members. The second asks for a partitioning of students into non-overlapping teams that also maximizes the benefit of the participating students. We show that the first problem can be solved optimally in polynomial time, while the second is NP-complete. For the MAXPARTITION problem, we also design an efficient approximate algorithm for solving it. Our experiments with generated data coming from different distributions demonstrate that our algorithm is significantly better than any of the popular strategies for dividing students in a class into sections.

Education and learning are currently undergoing transformative changes due to the emergence of tablet devices, cloud computing, and abundant online content. These trends present opportunities to transform traditional paper-based textbooks into tablet-based electronic textbooks, and to further enrich the educational experience by augmenting them with relevant supplementary materials. A natural question is whether this educational intervention, namely, enriching textbooks with relevant web articles, images and videos, is effective. It turns out that designing an experiment at scale for this purpose is nontrivial. We report on progress in designing and carrying out such an experiment.

We present study navigator, an algorithmically-generated aid for enhancing the experience of studying from electronic textbooks. The study navigator for a section of the book consists of helpful concept references for understanding this section. Each concept reference is a pair consisting of a concept phrase explained elsewhere and the link to the section in which it has been explained. We propose a novel reader model for textbooks and an algorithm for generating the study navigator based on this model. We also present the results of an extensive user study that demonstrates the efficacy of the proposed system across textbooks on different subjects from different grades.

A typical person has numerous online friends that, according to studies, the person often consults for opinions and advice. However, public broadcasting a question to all friends risks social capital when repeated too often, is not tolerant to topic sensitivity, and can result in no response, as the message is lost in a myriad of status updates. Direct messaging is more personal and avoids these pitfalls, but requires manual selection of friends to contact, which can be time consuming and challenging. A user may have difficulty guessing which of their numerous online friends can provide a high quality and timely response. We demonstrate a working system that addresses these issues by returning an ordered subset of friends predicting (a) near-term availability, (b) willingness to respond and (c) topical knowledge, given a query. The combination of these three aspects are unique to our solution, and all are critical to the problem of obtaining timely and relevant responses. Our system acts as a decision aid - we give insight into why each friend was recommended and let the user decide whom to contact.

The success of a group depends on continued participation of its members through time. We study the factors that affect continued user participation in the context of educational Twitter chats. To predict whether a user that attended her first session in a particular Twitter chat group will return to the group, we build 5F Model that captures five different factors: individual initiative, group characteristics, perceived receptivity, linguistic affinity and geographical proximity. Through statistical data analysis of thirty Twitter chats over a two year period as well as a survey study, our work provides many insights about group dynamics in Twitter chats. We show similarities between Twitter chats and traditional groups such as the importance of social inclusion and linguistic similarity while also identifying important distinctions such as the insignificance of geographical proximity. We also show that informational support is more important than emotional support in educational Twitter chats, but this does not reduce the sense of community as suggested in earlier studies.

Several issues arise with management of content that is generated in developing regions. Some result from linguistic diversity (as in India and Africa), some result from content being available only in forms that are more difficult to computationally manipulate (e.g., handwriting, speech, and legacy digital text in nonstandard encodings), some result from underinvestment in language resources for the languages of these regions, and some result from increased contact between cultures that have different views regarding the proper use of information and information artifacts. Such issues warrant focused attention if we are to optimally leverage information and knowledge management to the advantage of populations in developing regions. That is the purpose of this workshop.

Good textbooks are organized in a systematically progressive fashion so that students acquire new knowledge and learn new concepts based on known items of information. We provide a diagnostic tool for quantitatively assessing the comprehension burden that a textbook imposes on the reader due to non-sequential presentation of concepts. We present a formal definition of comprehension burden and propose an algorithmic approach for computing it. We apply the tool to a corpus of high school textbooks from India and empirically examine its effectiveness in helping authors identify sections of textbooks that can benefit from reorganizing the material presented.

Historical prices are important information that can help consumers decide whether the time is right to buy a product. They provide both a context to the users, and facilitate the use of prediction algorithms for forecasting future prices. To produce a representative price history, one needs to consider all offers for the product. However, matching offers to a product is a challenging problem, and mismatches could lead to glaring errors in price history. We propose a principled approach to filter out erroneous matches based on a probabilistic model of prices. We give an efficient algorithm for performing inference that takes advantage of the structure of the problem. We evaluate our results empirically using merchant offers collected from a search engine, and measure the proximity of the price history generated by our approach to the true price history. Our method outperforms alternatives based on robust statistics both in tracking the true price levels and the true price trends.

Textbooks have a direct bearing on the quality of education imparted to the students. Therefore, it is of paramount importance that the educational content of textbooks should provide rich learning experience to the students. Recent studies on understanding learning behavior suggest that the incorporation of digital visual material can greatly enhance learning. However, textbooks used in many developing regions are largely text-oriented and lack good visual material. We propose techniques for finding images from the web that are most relevant for augmenting a section of the textbook, while respecting the constraint that the same image is not repeated in different sections of the same chapter. We devise a rigorous formulation of the image assignment problem and present a polynomial time algorithm for solving the problem optimally. We also present two image mining algorithms that utilize orthogonal signals and hence obtain different sets of relevant images. Finally, we provide an ensembling algorithm for combining the assignments. To empirically evaluate our techniques, we use a corpus of high school textbooks in use in India. Our user study utilizing the Amazon Mechanical Turk platform indicates that the proposed techniques are able to obtain images that can help increase the understanding of the textbook material.

Most e-commerce sites to-date have focused on helping consumers decide what to buy and where to buy. We study the complementary question of helping consumers decide when to buy, focusing on consumer durables. We introduce a utility-based model for evaluating different approaches to this question. We focus on how best to make use of forecasts in making recommendations, and propose three natural strategies. We establish a relationship between these strategies, and show that one of them is optimal. We conduct a large-scale experimental study to test the performance and robustness of these strategies. Across a wide range of conditions, the best strategy obtains 90% of the maximum possible gains.

Keeping in pace with the increasing importance of commerce conducted over the Web, several e-commerce websites now provide admirable facilities for helping consumers decide what product to buy and where to buy it. However, since the prices of durable and high-tech products generally fall over time, a buyer of such products is often faced with a dilemma: Should she buy the product now or wait for cheaper prices?

An e-commerce catalog typically comprises of specifications for millions of products. The search engine receives millions of sales offers from thousands of independent merchants that must be matched to the right products. We describe the challenges that a system for matching unstructured offers to structured product descriptions must address, drawing upon our experience from building such a system for Bing Shopping. The heart of our system is a data-driven component that learns the matching function off-line, which is then applied at run-time for matching offers to products. We provide the design of this and other critical components of the system as well as the details of the extensive experiments we performed to assess the readiness of the system. This system is currently deployed in an experimental Commerce Search Engine and is used to match all the offers received by Bing Shopping to the Bing product catalog.

We study an online advertising model in which the merchant reimburses a portion of the transacted amount to the customer in a form of rebate. The customer referral and the rebate transfer might be mediated by a search engine. We investigate how the merchants can set rebate rates across different products to maximize their revenue. We consider two widely used demand models in economics---linear and log-linear---and explain how the effects of rebates can be incorporated in these models. Treating the parameters estimated as inputs to a revenue maximization problem, we develop convex optimization formulations of the problem and combinatorial algorithms for solving them. We validate our modeling assumptions using real transaction data. We conduct an extensive simulation study to evaluate the performance of our approach on maximizing revenue, and found that it generates significantly higher revenues for merchants compared to other rebate strategies. The rebate rates selected are extremely close to the optimal rates selected in hindsight.

A comprehensive product catalog is essential to the success of Product Search engines and shopping sites such as Yahoo! Shopping, Google Product Search, and Bing Shopping. Given the large number of products and the speed at which they are released to the market, keeping catalogs up-to-date becomes a challenging task, calling for the need of automated techniques. In this paper, we introduce the problem of product synthesis, a key component of catalog creation and maintenance. Given a set of offers advertised by merchants, the goal is to identify new products and add them to the catalog, together with their (structured) attributes. A fundamental challenge in product synthesis is the scale of the problem. A Product Search engine receives data from thousands of merchants about millions of products; the product taxonomy contains thousands of categories, where each category has a different schema; and merchants use representations for products that are different from the ones used in the catalog of the Product Search engine. We propose a system that provides an end-to-end solution to the product synthesis problem, and addresses issues involved in data extraction from offers, schema reconciliation, and data fusion. For the schema reconciliation component, we developed a novel and scalable technique for schema matching which leverages knowledge about previously-known instance-level associations between offers and products; and it is trained using automatically created training sets (no manually-labeled data is needed). We present an experimental evaluation using data from Bing Shopping for more than 800K offers, a thousand merchants, and 400 categories. The evaluation confirms that our approach is able to automatically generate a large number of accurate product specifications. Furthermore, the evaluation shows that our schema reconciliation component outperforms state-of-the-art schema matching techniques in terms of precision and recall.

We present the design of Symphony, a platform that enables non-developers to build and deploy a new class of search-driven applications that combine their data and domain expertise with content from search engines and other web services. The Symphony prototype has been built on top of Microsoft's Bing infrastructure. While Symphony naturally makes use of the customization capabilities exposed by Bing, its distinguishing feature is the capability it provides to the application creator to combine their proprietary data and domain expertise with content obtained from Bing. They can also integrate specialized data obtained from web services to enhance the richness of their applications. Finally, Symphony is targeted at non-developers and provides cloud services for the creation and deployment of applications.

Classification is a core task in knowledge discovery and data mining, and there has been substantial research effort in developing sophisticated classification models. In a parallel thread, recent work from the NLP community suggests that for tasks such as natural language disambiguation even a simple algorithm can outperform a sophisticated one, if it is provided with large quantities of high quality training data. In those applications, training data occurs naturally in text corpora, and high quality training data sets running into billions of words have been reportedly used.

In web search today, a user types a few keywords which are then matched against a large collection of unstructured web pages. This leaves a lot to be desired for when the best answer to a query is contained in structured data stores and/or when the user includes some structural semantics in the query.

We study the problem of answering ambiguous web queries in a setting where there exists a taxonomy of information, and that both queries and documents may belong to more than one category according to this taxonomy. We present a systematic approach to diversifying results that aims to minimize the risk of dissatisfaction of the average user. We propose an algorithm that well approximates this objective in general, and is provably optimal for a natural special case. Furthermore, we generalize several classical IR metrics, including NDCG, MRR, and MAP, to explicitly account for the value of diversification. We demonstrate empirically that our algorithm scores higher in these generalized metrics compared to results produced by commercial search engines.

The ranking function used by search engines to order results is learned from labeled training data. Each training point is a (query, URL) pair that is labeled by a human judge who assigns a score of Perfect, Excellent, etc., depending on how well the URL matches the query. In this paper, we study whether clicks can be used to automatically generate good labels. Intuitively, documents that are clicked (resp., skipped) in aggregate can indicate relevance (resp., lack of relevance). We give a novel way of transforming clicks into weighted, directed graphs inspired by eye-tracking studies and then devise an objective function for finding cuts in these graphs that induce a good labeling. In its full generality, the problem is NP-hard, but we show that, in the case of two labels, an optimum labeling can be found in linear time. For the more general case, we propose heuristic solutions. Experiments on real click logs show that click-based labels align with the opinion of a panel of judges, especially as the consensus of the panel grows stronger.

introduction Share on Introduction to special issue on social computing, behavioral modeling, and prediction Editors: Huan Liu View Profile , John Salerno View Profile , Michael Young View Profile , Rakesh Agrawal View Profile , Philip S. Yu View Profile Authors Info & Claims ACM Transactions on Knowledge Discovery from DataVolume 3Issue 2April 2009 Article No.: 6pp 1–3https://doi.org/10.1145/1514888.1514889Published:21 April 2009Publication History 6citation751DownloadsMetricsTotal Citations6Total Downloads751Last 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Data Mining has made tremendous strides in the last decade. It is time to take data mining to the next level of contributions, while continuing to innovate for the current mainstream market. We postulate that a fruitful future direction could be humane data mining: applications to benefit individuals. The potential applications include personal data mining (e.g. personal health), enable people to get a grip on their world (e.g. dealing with the long tail of search), enable people to become creative (e.g. inventions arising from linking non-interacting scientific literature), enable people to make contributions to society (e.g. education collaboration networks), and data-driven science (e.g. study ecological disasters, brain disorders). Rooting our future work in these (and similar) applications, will lead to new data mining abstractions, algorithms, and systems.

In the sponsored search model, search engines are paid by businesses that are interested in displaying ads for their site alongside the search results. Businesses bid for keywords, and their ad is displayed when the keyword is queried to the search engine. An important problem in this process is keyword generation: given a business that is interested in launching a campaign, suggest keywords that are related to that campaign. We address this problem by making use of the query logs of the search engine. We identify queries re-lated to a campaign by exploiting the associations between queries and URLs as they are captured by the user’s clicks. These queries form good keyword suggestions since they cap-ture the “wisdom of the crowd ” as to what is related to a site. We formulate the problem as a semi-supervised learn-ing problem, and propose algorithms within the Markov Random Field model. We perform experiments with real query logs, and we demonstrate that our algorithms scale to large query logs and produce meaningful results.

Numerous widely publicized cases of theft and misuse of private information underscore the need for audit technology to identify the sources of unauthorized disclosure. We present an auditing methodology that ranks potential disclosure sources according to their proximity to the leaked records. Given a sensitive table that contains the disclosed data, our methodology prioritizes by relevance the past queries to the database that could have potentially been used to produce the sensitive table. We provide three conceptually different measures of proximity between the sensitive table and a query result. One measure is inspired by information retrieval in text processing, another is based on statistical record linkage, and the third computes the derivation probability of the sensitive table in a tree-based generative model. We also analyze the characteristics of the three measures and the corresponding ranking algorithms.

We present a secure network service for sovereign information sharing whose only trusted component is an off-theshelf secure coprocessor. The participating data providers send encrypted relations to the service that sends the encrypted results to the recipients. The technical challenge in implementing such a service arises from the limited capability of the secure coprocessors: they have small memory, no attached disk, and no facility for communicating directly with other machines in the network. The internal state of an ongoing computation within the secure coprocessor cannot be seen from outside, but its interactions with the server can be exploited by an adversary. We formulate the problem of computing join in this setting where the goal is to prevent information leakage through patterns in I/O while maximizing performance. We specify criteria for proving the security of a join algorithm and provide provably safe algorithms. These algorithms can be used to compute general joins involving arbitrary predicates and multiple sovereign databases. We thus enable a new class of applications requiring query processing across sovereign entities such that nothing apart from the result is revealed to the recipients.

The Sarbanes-Oxley Act instituted a series of corporate reforms to improve the accuracy and reliability of financial reporting. Sections 302 and 404 of the Act require SEC-reporting companies to implement internal controls over financial reporting, periodically assess the effectiveness of these internal controls, and certify the accuracy of their financial statements. We suggest that database technology can play an important role in assisting compliance with the internal control provisions of the Act. The core components of our solution include: (i) modeling of required workflows, (ii) active enforcement of control activities, (iii) auditing of actual workflows to verify compliance with internal controls, and (iv) discovery-driven OLAP to identify irregularities in financial data. We illustrate how the features of our solution fulfill Sarbanes-Oxley requirements using several real-life scenarios. In the process, we identify opportunities for new database research.

Tracking and tracing individual items is a new and emerging trend in many industries. Driven by maturing technologies such as radio-frequency identification (RFID) and upcoming standards such as the electronic product code (EPC), a rapidly increasing number of enterprises are collecting vast amounts of tracking data. To enable traceability over the entire life-cycle of items data has to be shared across independent and possibly competing enterprises. The need to simultaneously compete and cooperate requires a traceability system design that allows companies to share their traceability data while maintaining complete sovereignty over what is shared and with whom. Based on an extensive study of traceability applications, we introduce the formal concept of traceability networks and highlight the technical challenges involved in sharing data in such a network. To address these challenges, we present an innovative combination of query processing techniques from P2P networks and distributed as well as parallel databases with confidentiality enforcement techniques

This talk is about the next frontier in knowledge discovery and data mining.

Contextual preferences take the form that item i1 is preferred to item i2 in the context of X. For example, a preference might state the choice for Nicole Kidman over Penelope Cruz in drama movies, whereas another preference might choose Penelope Cruz over Nicole Kidman in the context of Spanish dramas. Various sources provide preferences independently and thus preferences may contain cycles and contradictions. We reconcile democratically the preferences accumulated from various sources and use them to create a priori orderings of tuples in an off-line preprocessing step. Only a few representative orders are saved, each corre-sponding to a set of contexts. These orders and associated contexts are used at query time to expeditiously provide ranked answers. We formally define contextual preferences, provide algorithms for creating orders and processing queries, and present experimental results that show their efficacy and practical utility.

Databases are at the core of successful businesses. Due to the voluminous stores of personal data being held by companies today, preserving privacy has become a crucial requirement for operating a business. This paper proposes how current relational database management systems can be transformed into their privacy-preserving equivalents. Specifically, we present language constructs and implementation design for fine-grained access control to achieve this goal.

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.

Many practical applications require that distance measures to be asymmetric and context-sensitive. We introduce context-sensitive learnable asymmetric dissimilarity (CLAD) measures, which are defined to be a weighted sum of a fixed number of dissimilarity measures where the associated weights depend on the point from which the dissimilarity is measured. The parameters used in defining the measure capture the global relationships among the features. We provide an algorithm to learn the dissimilarity measure automatically from a set of user specified comparisons in the form "x is closer to y than to z" and study its performance. The experimental results show that the proposed algorithm outperforms other approaches due to the context sensitive nature of the CLAD measures.

We present techniques for privacy-preserving computation of multidimensional aggregates on data partitioned across multiple clients. Data from different clients is perturbed (randomized) in order to preserve privacy before it is integrated at the server. We develop formal notions of privacy obtained from data perturbation and show that our perturbation provides guarantees against privacy breaches. We develop and analyze algorithms for reconstructing counts of subcubes over perturbed data. We also evaluate the tradeoff between privacy guarantees and reconstruction accuracy and show the practicality of our approach.

Clustering algorithms typically operate on a feature vector representation of the data and find clusters that are compact with respect to an assumed (dis)similarity measure between the data points in feature space. This makes the type of clusters identified highly dependent on the assumed similarity measure. Building on recent work in this area, we formally define a class of spatially varying dissimilarity measures and propose algorithms to learn the dissimilarity measure automatically from the data. The idea is to identify clusters that are compact with respect to the unknown spatially varying dissimilarity measure. Our experiments show that the proposed algorithms are more stable and achieve better accuracy on various textual data sets when compared with similar algorithms proposed in the literature.

Sovereign information sharing allows autonomous entities to compute queries across their databases in such a way that nothing apart from the result is revealed. We describe an implementation of this model using web services infrastructure. Each site participating in sovereign sharing offers a data service that allows database operations to be applied on the tables they own. Of particular interest is the provision for binary operations such as relational joins. Applications are developed by combining these data services. We present performance measurements that show the promise of a new breed of practical applications based on the paradigm of sovereign information integration.

Encryption is a well established technology for protecting sensitive data. However, once encrypted, data can no longer be easily queried aside from exact matches. We present an order-preserving encryption scheme for numeric data that allows any comparison operation to be directly applied on encrypted data. Query results produced are sound (no false hits) and complete (no false drops). Our scheme handles updates gracefully and new values can be added without requiring changes in the encryption of other values. It allows standard databse indexes to be built over encrypted tables and can easily be integrated with existing database systems. The proposed scheme has been designed to be deployed in application environments in which the intruder can get access to the encrypted database, but does not have prior domain information such as the distribution of values and annot encrypt or decrypt arbitrary values of his choice. The encryption is robust against estimation of the true value in such environments.

No abstract available.

We show that PC keyboards, notebook keyboards, telephone and ATM pads are vulnerable to attacks based on differentiating the sound emanated by different keys. Our attack employs a neural network to recognize the key being pressed. We also investigate why different keys produce different sounds and provide hints for the design of homophonic keyboards that would be resistant to this type of attack.

No abstract available.

Beginning with a general survey of the new requirements placed on the database technology by the e-commerce applications, we discuss four specific problems as concrete examples and their solutions. 1. The search provided by most e-Commerce sites is rather primitive and is based on the traditional database metaphor of submitting an SQL query and packaging the response as an HTML page. The Eureka parameteric search engine replaced the above submit/response metaphor with a continuous querying metaphor that seamlessly integrates querying with result browsing. We discuss this new metaphor and present the required computational techniques and data structures. 2. The problem of integrating documents from different sources into a master catalog is pervasive in eCommerce websites, marketplaces and portals. The conventional technology for automating this process consisted of building a classifier that uses the categorization of documents in the master catalog to construct a model for predicting the category of unknown documents. However, many of the data sources have their own categorization, and classification accuracy can be improved by factoring in the implicit information in these source categorizations. Empirical evaluation of the catalog integrator built using this insight showed very large improvement in accuracy. We present this new integration technology. 3. Another hard problem in creating searchable E-Commerce catalogs is that the data extraction to obtain attribute-value pairs to be able to do parametric searches is difficult and error-prone. We take the audacious approach of not requiring the relationship between attributes and values to be accurately established and simply use only numbers during the searches. We present this new technology and characterize its applicability. 4. e-Commerce catalogs require data schemas that are constantly evolving and sparsely populated. The conventional horizontal row representation used in database systems fails to meet functional and manageability requirements for such data. This problem is addressed by representing objects in a vertical format, storing an object as a set of tuples. However, writing queries against this format becomes cumbersome and error prone and the existing tools no longer work. We developed techniques for defining a logical horizontal view and transforming the horizontal view queries into queries against the vertical format. By using clever rewriting, we were able to obtain very high query performance of the vertical representation on DB2. We discuss the transformations and present performance results.

The choice of database layout, i.e., how database objects such as tables and indexes are assigned to disk drives can significantly impact the I/O performance of the system. Today, DBAs typically rely on fully striping objects across all available disk drives as the basic mechanism for optimizing I/O performance. While full striping maximizes I/O parallelism, when query execution involves coaccess of two or more large objects, e.g., a merge join of two tables, the above strategy may be suboptimal due to the increased number of random I/O accesses on each disk drive. Here, we propose a framework for automating the choice of database layout for a given database that also takes into account the effects of coaccessed objects in the workload faced by the system. We formulate the above as an optimization problem and present an efficient solution to the problem that judiciously takes into account the trade-off between I/O parallelism and random I/O accesses. Our experiments on Microsoft SQL server show the superior I/O performance of our techniques compared to the traditional approach of fully striping each database object across all disk drives.

Platform for privacy preferences (P3P) is the most significant effort currently underway to enable Web users to gain control over their private information. P3P provides mechanisms for Web site owners to express their privacy policies in a standard format that a user can programmatically check against her privacy preferences to decide whether to release her data to the Web site. We discuss architectural alternatives for implementing P3P and present a server-centric implementation that reuses database querying technology, as opposed to the prevailing client-centric implementations based on specialized engines. Not only does the proposed implementation have qualitative advantages, our experiments indicate that it performs significantly better than the sole public-domain client-centric implementation and that the latency introduced by preference matching is small enough for real-world deployments of P3P.

The explosive progress in networking, storage, and processor technologies is resulting in an unprecedented amount of digitization of information. In concert with this dramatic increase in digital data, concerns about the privacy of personal information have emerged globally. The concerns over massive collection of data are naturally extending to analytic tools applied to data. Data mining, with its promise to efficiently discover valuable, non-obvious information from large databases, is particularly vulnerable to misuse.The challenge for the database community is to design information systems that protect the privacy and ownership of individual data without impeding information flow. One way of preserving privacy of individual data values is to perturb them. Since the primary task in data mining is the development of models about aggregated data, we explore if we can develop accurate models without access to precise information in individual data records. We consider the concrete case of building a decision-tree classifier from perturbed data. While it is not possible to accurately estimate original values in individual data records, we describe a reconstruction procedure to accurately estimate the distribution of original data values. By using these reconstructed distributions, we are able to build classifiers whose accuracy is comparable to the accuracy of classifiers built with the original data. We also discuss how to discover association rules over privacy preserved data.Inspired by the privacy tenet of the Hippocratic Oath, we argue that future database systems must include responsibility for the privacy of data they manage as a founding tenet. We enunciate the key principles for such Hippocratic database systems, distilled from the principles behind current privacy legislations and guidelines. We identify the technical challenges and problems in designing Hippocratic databases, and also outline some solution approaches.

Literature on information integration across databases tacitly assumes that the data in each database can be revealed to the other databases. However, there is an increasing need for sharing information across autonomous entities in such a way that no information apart from the answer to the query is revealed. We formalize the notion of minimal information sharing across private databases, and develop protocols for intersection, equijoin, intersection size, and equijoin size. We also show how new applications can be built using the proposed protocols.

No abstract available.

The Platform for Privacy Preferences (P3P) is the most significant effort currently underway to enable web users to gain control over their private information. The designers of P3P simultaneously designed a preference language called APPEL to allow users to express their privacy preferences, thus enabling automatic matching of privacy preferences against P3P policies. Unfortunately subtle interactions between P3P and APPEL result in serious problems when using APPEL: Users can only directly specify what is unacceptable in a policy, not what is acceptable; simple preferences are hard to express; and writing APPEL preferences is error prone. We show that these problems follow from a fundamental design choice made by APPEL, and cannot be solved without completely redesigning the language. Therefore we explore alternatives to APPEL that can overcome these problems. In particular, we show that XPath serves quite nicely as a preference language and solves all the above problems. We identify the minimal subset of XPath that is needed, thus allowing matching programs to potentially use a smaller memory footprint. We also give an APPEL to XPath translator that shows that XPath is as expressive as APPEL.

Recent advances in information retrieval over hyperlinked corpora have convincingly demonstrated that links carry less noisy information than text. We investigate the feasibility of applying link-based methods in new applications domains. The specific application we consider is to partition authors into opposite camps within a given topic in the context of newsgroups. A typical newsgroup posting consists of one or more quoted lines from another posting followed by the opinion of the author. This social behavior gives rise to a network in which the vertices are individuals and the links represent "responded-to" relationships. An interesting characteristic of many newsgroups is that people more frequently respond to a message when they disagree than when they agree. This behavior is in sharp contrast to the WWW link graph, where linkage is an indicator of agreement or common interest. By analyzing the graph structure of the responses, we are able to effectively classify people into opposite camps. In contrast, methods based on statistical analysis of text yield low accuracy on such datasets because the vocabulary used by the two sides tends to be largely identical, and many newsgroup postings consist of relatively few words of text.

A large fraction of the useful Web is comprised of specification documents that largely consist of (attribute name, numeric value) pairs embedded in text. Examples include product information, classified advertisements, resumes, etc. The approach taken in the past to search these documents by first establishing correspondences between values and their names has achieved limited success because of the difficulty of extracting this information from free text. We propose a new approach that does not require this correspondence to be accurately established. Provided the data has "low reflectivity", we can do effective search even if the values in the data have not been assigned attribute names and the user has omitted attribute names in the query. We give algorithms and indexing structures for implementing the search. We also show how hints (i.e., imprecise, partial correspondences) from automatic data extraction techniques can be incorporated into our approach for better accuracy on high reflectivity data sets. Finally, we validate our approach by showing that we get high precision in our answers on real data sets from a variety of domains.

We present a framework for mining association rules from transactions consisting of categorical items where the data has been randomized to preserve privacy of individual transactions. While it is feasible to recover association rules and preserve privacy using a straightforward "uniform" randomization, the discovered rules can unfortunately be exploited to find privacy breaches. We analyze the nature of privacy breaches and propose a class of randomization operators that are much more effective than uniform randomization in limiting the breaches. We derive formulae for an unbiased support estimator and its variance, which allow us to recover itemset supports from randomized datasets, and show how to incorporate these formulae into mining algorithms. Finally, we present experimental results that validate the algorithm by applying it on real datasets.

A large fraction of the useful web comprises of specification documents that largely consist of hattribute name, numeric valuei pairs embedded in text. Examples include product information, classified advertisements, resumes, etc. The approach taken in the past to search these documents by first establishing correspondences between values and their names has achieved limited success because of the difficulty of extracting this information from free text. We propose a new approach that does not require this correspondence to be accurately established. Provided the data has "low reflectivity", we can do effective search even if the values in the data have not been assigned attribute names and the user has omitted attribute names in the query. We give algorithms and indexing structures for implementing the search. We also show how hints (i. e, imprecise, partial correspondences) from automatic data extraction techniques can be incorporated into our approach for better accuracy on high reflectivity datasets. Finally, we validate our approach by showing that we get high precision in our answers on real datasets from a variety of domains.

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.

Many emerging data mining applications require a similarity join between points in a high-dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsi/ tree, for fast spatial similarity joins on high-dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence, the proposed index structure scales to high-dimensional data. We analyze the cost of the join for the /spl epsi/ tree and the R-tree family, and show that the /spl epsi/ tree will perform better for high-dimensional joins. Empirical evaluation, using synthetic and real-life data sets, shows that similarity join using the /spl epsi/ tree is twice to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions. We also discuss how some of the ideas of the /spl epsi/ tree can be applied to the R-tree family. These biased R-trees perform better than the corresponding traditional R-trees for high-dimensional similarity joins, but do not match the performance of the /spl epsi/ tree.

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

We address the problem of integrating documents from different sources into a master catalog. This problem is pervasive in web marketplaces and portals. Current technology for automating this process consists of building a classifier that uses the categorization of documents in the master catalog to construct a model for predicting the category of unknown documents. Our key insight is that many of the data sources have their own categorization, and classification accuracy can be improved by factoring in the implicit information in these source categorizations. We show how a Naive Bayes classification can be enhanced to incorporate the similarity information present in source catalogs. Our analysis and empirical evaluation show substantial improvement in the accuracy of catalog integration. Keywords: Classification, Categorization, Data Mining, Catalog Integration, Web Portals, Web Marketplaces 1.

The advent of the World Wide Web has created an explosion in the available on-line information. As the range of potential choices expand, the time and effort required to sort through them also expands. We propose a formal framework for expressing and combining user preferences to address this problem. Preferences can be used to focus search queries and to order the search results. A preference is expressed by the user for an entity which is described by a set of named fields; each field can take on values from a certain type. The * symbol may be used to match any element of that type. A set of preferences can be combined using a generic combine operator which is instantiated with a value function, thus providing a great deal of flexibility. Same preferences can be combined in more than one way and a combination of preferences yields another preference thus providing the closure property. We demonstrate the power of our framework by illustrating how a currently popular personalization system and a real-life application can be realized as special cases of our framework. We also discuss implementation of the framework in a relational setting.

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".

Presents parallel algorithms for building decision-tree classifiers on shared-memory multiprocessor (SMP) systems. The proposed algorithms span the gamut of data and task parallelism. The data parallelism is based on attribute scheduling among processors. This basic scheme is extended with task pipelining and dynamic load balancing to yield faster implementations. The task-parallel approach uses dynamic subtree partitioning among processors. Our performance evaluation shows that the construction of a decision-tree classifier can be effectively parallelized on an SMP machine with good speedup.

Data mining has attracted tremendous interest in the research community as well as commercial market place. The last few years have witnessed a flurry of technical innovations and introduction of comercial products. The next major challenge facing data mining is to make a transition from a niche technology to a main stream technology. I will present key technical and environmental issues that must be addressed for a successful transition.

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.

Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate clusters in large high dimensional datasets. 1 Introduction Clustering is a descriptive task that seeks to identify homogeneous groups of objects based on the values of th...

Data mining on large data warehouses is becoming increasingly important. In support of this trend, we consider a spectrum of architectural alternatives for coupling mining with database systems. These alternatives include: loose-coupling through a SQL cursor interface; encapsulation of a mining algorithm in a stored procedure; caching the data to a file system on-the-fly and mining; tight-coupling using primarily user-defined functions; and SQL implementations for processing in the DBMS. We comprehensively study the option of expressing the mining algorithm in the form of SQL queries using Association rule mining as a case in point. We consider four options in SQL-92 and six options in SQL enhanced with object-relational extensions (SQL-OR). Our evaluation of the different architectural alternatives shows that from a performance perspective, the Cache-Mine option is superior, although the performance of the SQL-OR option is within a factor of two. Both the Cache-Mine and the SQL-OR approaches incur a higher storage penalty than the loose-coupling approach which performance-wise is a factor of 3 to 4 worse than Cache-Mine. The SQL-92 implementations were too slow to qualify as a competitive option. We also compare these alternatives on the basis of qualitative factors like automatic parallelization, development ease, portability and inter-operability.

A partial-sum query obtains the summation over a set of specified cells of a data cube. We establish a connection between the covering problem in the theory of error-correcting codes and the partial-sum problem and use this connection to devise algorithms for the partial-sum problem with efficient space-time trade-offs. For example, using our algorithms, with 44 percent additional storage, the query response time can be improved by about 12 percent; by roughly doubling the storage requirement, the query response time can be improved by about 34 percent.

The authors propose a data model and a few algebraic operations that provide semantic foundation to multidimensional databases. The distinguishing feature of the proposed model is the symmetric treatment not only of all dimensions but also measures. The model provides support for multiple hierarchies along each dimension and support for ad hoc aggregates. The proposed operators are composable, reorderable, and closed in application. These operators are also minimal in the sense that none can be expressed in terms of others nor can any one be dropped without sacrificing functionality. They make possible the declarative specification and optimization of multidimensional database queries that are currently specified operationally. The operators have been designed to be translated to SQL and can be implemented either on top of a relational database system or within a special purpose multidimensional database engine. In effect, they provide an algebraic application programming interface (API) that allows the separation of the front end from the back end. Finally, the proposed model provides a framework in which to study multidimensional databases and opens several new research problems.

In last year’s ICDE panel in New Orleans [l], we examined the question of whether database research is able to provide leadership to database industries. There was a consensus that with the maturing of the field, we should now focus on new areas where we can leverage off our rich experience in database research. The question of what problem to work on next has always been a difficult one to answer and we suspect that it will not get easier. Even then, it will be rewarding to examine the question of how the successful and not so successful threads of research came into being and what caught our fancy and why. Specifically, we will seek the perspective of the panelists on the following questions:

Many emerging data mining applications require a similarity join between points in a high-dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsiv/-kdB tree, for fast spatial similarity joins on high-dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence the proposed index structure scales to high-dimensional data. Empirical evaluation, using synthetic and real-life datasets, shows that similarity join using the /spl epsiv/-kdB tree is 2 to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions.

A partial-sum query obtains the summation over a set of specified cells of a data cube.We establish a connection between the covering problem in the theory of error-correcting codes and the partial-sum problem and use this connection to devise algorithms for the partial-sum problem with efficient space-time trade-offs.For example, using our algorithms, with 44% additional storage, the query response time can be improved by about 12%; by rougbly doubling the storage requirement, the query response time can be improved by about 34%.

A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. We present fast algorithms for range queries for two types of aggregation operations: SUM and MAX. These two operations cover techniques required for most popular aggregation operations, such as those supported by SQL.

We introduce the problem of mining association rules in large relational tables containing both quantitative and categorical attributes. An example of such an association might be "10% of married people between age 50 and 60 have at least 2 cars". We deal with quantitative attributes by fine-partitioning the values of the attribute and then combining adjacent partitions as necessary. We introduce measures of partial completeness which quantify the information lost due to partitioning. A direct application of this technique can generate too many similar rules. We tackle this problem by using a "greater-than-expected-value" interest measure to identify the interesting rules in the output. We give an algorithm for mining such quantitative association rules. Finally, we describe the results of using this approach on a real-life dataset.

We consider the problem of mining association rules on a shared nothing multiprocessor. We present three algorithms that explore a spectrum of trade-offs between computation, communication, memory usage, synchronization, and the use of problem specific information. The best algorithm exhibits near perfect scaleup behavior, yet requires only minimal overhead compared to the current best serial algorithm.

We are given a large database of customer transactions, where each transaction consists of customer-id, transaction time, and the items bought in the transaction. We introduce the problem of mining sequential patterns over such databases. We present three algorithms to solve this problem, and empirically evaluate their performance using synthetic data. Two of the proposed algorithms, AprioriSome and AprioriAll, have comparable performance, albeit AprioriSome performs a little better when the minimum number of customers that must support a sequential pattern is low. Scale-up experiments show that both AprioriSome and AprioriAll scale linearly with the number of customer transactions. They also have excellent scale-up properties with respect to the number of transactions per customer and the number of items in a transaction.>

We view database mining as the efficient construction and verification of models of patterns embedded in large databases. Many of the database mining problems have been motivated by the practical decision support problems faced by most large retail organizations. In the Quest project at the IBM Almaden Research center, we have focussed on three classes of database mining problems involving classification, associations, and sequences. In this tutorial, I will draw upon my Quest experience to present my perspective of database mining, describe current work, and present some open problems.

No abstract available.

Given a large graph, stored on disk, there is often a need to perform a search over this graph. Such a need could arise, for example, in the search component of a data-intensive expert system or to solve path problems in deductive database systems. In this paper, we present a novel data structuring technique and show how a branch-and-bound search algorithm can use this data structuring to prune the search space. Simulation results confirm that, using these techniques, a search can be expedited significantly without incurring a large storage penalty. As a side benefit, it is possible to organize the search to obtain successive approximations to the desired solution with considerable reduction in the total search.>

Ode, a database system and environment based on the object paradigm, is discussed. Ode is defined, queried and manipulated using the database programming language O++, which is based on C++. The O++ compiler translates O++ programs into C++ programs that contain calls to the Ode object manager. The implementation of O++, the Ode object manager, and the translation of the database facilities in O++ are described. The problems encountered in the implementation and their resolutions are reviewed.>

An access structure that accelerates the processing of generalized transitive closure queries is presented. For an acyclic graph, the access structure consists of source-destination pairs arranged in a topologically sorted order. For a cyclic graph, entries in the structure are approximately topologically sorted. The authors present a breadth-first algorithm for creating such a structure, show how it can be used to process queries, and describe incremental techniques for maintaining it.>

Polyglot is an extensible relational-database-type system that supports inheritance, encapsulation, and dynamic method dispatch. It allows use from multiple application languages and permits objects to retain their behavior as they cross the boundary between database and application program. The authors describe the design of Polyglot, extensions to the structured query language (SQL) to support the use of Polyglot types and methods, and the implementation of Polyglot in the Starburst relational database system.>

We are given a large database of customer transactions. Each transaction consists of items purchased by a customer in a visit. We present an efficient algorithm that generates all significant association rules between items in the database. The algorithm incorporates buffer management and novel estimation and pruning techniques. We also present results of applying this algorithm to sales data obtained from a large retailing company, which shows the effectiveness of the algorithm.

The authors' perspective of database mining as the confluence of machine learning techniques and the performance emphasis of database technology is presented. Three classes of database mining problems involving classification, associations, and sequences are described. It is argued that these problems can be uniformly viewed as requiring discovery of rules embedded in massive amounts of data. A model and some basic operations for the process of rule discovery are described. It is shown how the database mining problems considered map to this model, and how they can be solved by using the basic operations proposed. An example is given of an algorithm for classification obtained by combining the basic rule discovery operations. This algorithm is efficient in discovering classification rules and has accuracy comparable to ID3, one of the best current classifiers.>

We present SQL/TC, an extension of SQL, to allow the expression of generalized transitive closure queries. The extension permits the user to pose queries that compute paths between two points and information associated with these paths. Such queries may specify selections on arcs, paths, or sets of paths, The output of a query may include the aggregation of information for different paths between the same endpoints. Our notation is declarative, preserves the spirit of SQL, and allows a declarative and concise formulation of transitive closure queries.>

In designing the versioning facility in Ode, a few but semantically sound and powerful concepts are introduced that allow implementation of a wide variety of paradigms. Some of the salient features of these versioning facilities are the following: (1) object versioning is orthogonal to type; (2) reference to an object can be bound statically to a specific version of the object or dynamically to whatever is its latest version; and (3) both temporal as well as derived-from relationships between versions of an object are maintained automatically. These facilities have been incorporated seamlessly into Ode's database programming language, O++. The new language constructs are powerful enough to make O++ a suitable platform for implementing a variety of versioning paradigms and application-specific systems.>

Two complementary techniques for optimizing generalized transitive closure queries are presented: (i) selections on paths are applied during the closure computation, so that paths that are not in the result and that are not needed to compute the result are pruned as early as possible and (ii) paths that are in the result, or needed to compute the result, are represented in a condensed form. The condensed representation holds the minimal information that is necessary for the specified label computations and selections to be performed. The combined impact of these techniques is that the number of paths generated during the closure computation and the storage required for each such path are both greatly reduced.>

Multi-methods allow method selection to be based on the types of any number of arguments.Languages that currently support multi-methods do not support static type checking.We show how multi-methods can be statically type checked and how information collected at the time of program compilation can be used to make the run-time dispatch of multi-methods more efficient.The results presented can provide the basis for introducing multi-methods in languages with static type checking and for designing new object-oriented paradigms based on multi-methods. 'The exact syntax is different in C++;we have taken liberty with the syntax to clarify the point.

No abstract available.

OdeView is the graphical front end for Ode, an object-oriented database system and environment. Ode's data model supports data encapsulation, type inheritance, and complex objects. OdeView provides facilities for examining the database schema (i.e., the object type or class hierarchy), examining class definitions, browsing objects, following chains of references starting from an object, synchronized browsing, displaying selected portions of objects (projection), and retrieving objects with specific characteristics (selection).

OdeView is the graphical front end for Ode, an object-oriented database system and environment. It is intended for users who do not want to write programs in Ode's database programming language O++ to interact with Ode but instead want to use a friendlier interface to Ode. OdeView is based on the graphical direct manipulation paradigm that involves selection of items from pop-up menus and icons that can be clicked on and dragged. OdeView provides facilities for examining the database schema examining class definitions, browsing objects, following chains of references, displaying selected portions of objects or selecting a subset of the ways in which an object can be displayed (projection), and retrieving specific objects (selection).

We present new algorithms for computing transitive closure of large database relations. Unlike iterative algorithms, such as the seminaive and logarithmic algorithms, the termination of our algorithms does not depend on the length of paths in the underlying graph (hence the name direct algorithms). Besides reachability computations, the proposed algorithms can also be used for solving path problems. We discuss issues related to the efficient implementation of these algorithms, and present experimental results that show the direct algorithms perform uniformly better than the iterative algorithms. A side benefit of this work is that we have proposed a new methodology for evaluating the performance of recursive queries.

The authors argue for implementing composition as a primitive operation and present a single-sided composition algorithm that performs join protection and duplicate elimination as one unified operation. They report experimental results that show an operating region in which this algorithm outperforms composition by the standard method. This operating region is characterized by a join result many times larger than the source relations, and many duplicates after projection over the nonjoin attributes. This occurs, for example, in deductive databases when computing transitive closures of dense graphs.>

The problem of efficiently processing recursive path queries in deductive database systems is discussed, and a semimaterialized encoding structure is proposed as an attractive approach that provides a balance between efficiency of retrieval and feasibility of storage. Incremental algorithms are presented that enable the effects of updates to the underlying database to be reflected in the materialized information. Performance simulations indicate that these techniques can significantly speed up the processing of path queries at an acceptable level of storage overhead.>

We argue that accessing the transitive closure of relationships is an important component of both databases and knowledge representation systems in Artificial Intelligence. The demands for efficient access and management of large relationships motivate the need for explicitly storing the transitive closure in a compressed and local way, while allowing updates to the base relation to be propagated incrementally. We present a transitive closure compression technique, based on labeling spanning trees with numeric intervals, and provide both analytical and empirical evidence of its efficacy, including a proof of optimality.

ODE is a database system and environment based on the object paradigm. It offers one integrated data model for both database and general purpose manipulation. The database is defined, queried and manipulated in the database programming language O++ which is based on C++. O++ borrows and extends the object definition facility of C++, called the class. Classes support data encapsulation and multiple inheritance. We provide facilities for creating persistent and versioned objects, defining sets, and iterating over sets and clusters of persistent objects. We also provide facilities to associate constraints and triggers with objects. This paper presents the linguistic facilities provided in O++ and the data model it supports.

Efficient least-fixpoint query evaluation is crucial to using logic as the query language for relational databases. The authors present a selection transposition algorithm that allows selections that are conjunctions of the predicates of the form column theta value to be evaluated ahead of the least-fixpoint operator while processing linear recursive queries. It is also shown that the algorithm transposes the strongest possible selection.>

A selection transposition algorithm is presented that allows selections that are conjunctions of predicates of the form 'column theta value' to be evaluated ahead of the least fixpoint operator while processing linear recursive queries. It is shown that the algorithm transposes the strongest possible selection.>

A model is presented for parallel processing in loosely coupled multiprocessing environments, such as networks of computer workstations, that are amenable to large-grained parallelism. The model takes into account the overhead involved in data communication to and from a remote processor and can be used to partition a large class of computations optimally, consisting of computations that can be organized as a one-level tree and are homogeneous and separable. The optimal partition can be determined for a given number processors, and, if required, the optimal number of processors to use can also be derived. Experimental results validate the model and demonstrate its effectiveness.>

An extension of E.F. Codd's relational algebra (1970) with an alpha ( alpha ) operator is presented that allows a large class of natural and useful recursive queries to be expressed, and yet has the property of being efficiently implementable. Formally, this class is a superset of linear recursive queries. Intuitively, this class comprises queries that examine transitive relationships between various instances of an entity. It is believed that this class covers many natural and interesting recursive queries. Examples of such queries include determining parts requirements for manufacturing a product, finding the critical path in a project management network, finding the shortest path between two cities, verifying connectivity between two points of a circuit, etc.>

An alpha (α) operator is proposed which when added to relational algebra allows a large class of natural and useful recursive queries to be expressed, and yet has the property of being efficiently implementable.

We show that every linearly recursive query can be expressed as a transitive closure possibly preceded and followed by operations already available in relational algebra. This reduction is possible even if there are repeated variables in the recursive literals and if some of the arguments in the recursive literals are constants. Such an equivalence has significant theoretical and practical ramifications. One the one hand it influences the design of expressive notations to capture recursion as an augmentation of relational query languages. On the other hand implementation of deductive databases is impacted in that the design does not have to provide the generality that linear recursion would demand. It suffices to study the single problem of transitive closure and to provide an efficient implementation for it.

A number of recent studies have examined the performance of concurrency control algorithms for database management systems. The results reported to date, rather than being definitive, have tended to be contradictory. In this paper, rather than presenting “yet another algorithm performance study,” we critically investigate the assumptions made in the models used in past studies and their implications. We employ a fairly complete model of a database environment for studying the relative performance of three different approaches to the concurrency control problem under a variety of modeling assumptions. The three approaches studied represent different extremes in how transaction conflicts are dealt with, and the assumptions addressed pertain to the nature of the database system's resources, how transaction restarts are modeled, and the amount of information available to the concurrency control algorithm about transactions' reference strings. We show that differences in the underlying assumptions explain the seemingly contradictory performance results. We also address the question of how realistic the various assumptions are for actual database systems.

There is growing evidence that, for a fairly wide variety of database workloads and system configurations, locking is the concurrency control strategy of choice. With locking, of course, comes the possibility of deadlocks. Although the database literature is full of algorithms for dealing with deadlocks, very little in the way of practical performance information is available to a database system designer faced with the decision of choosing a good deadlock resolution strategy. This paper is an attempt to bridge this gap in our understanding of the behavior and performance of alternative deadlock resolution strategies. We employ a simulation model of a database environment to study the relative performance of several strategies based on deadlock detection, several strategies based on deadlock prevention, and a strategy based on timeouts. We show that the choice of the best deadlock resolution strategy depends upon the level of data contention, the resource utilization levels, and the types of transactions. We provide guidelines for selecting a deadlock resolution strategy for different operating regions.

We consider a computing environment consisting of a network of autonomous, yet cooperating personal computer workstations and shared servers. Computing cycles in such an environment can be shared by creating a pool of compute servers in the network that may be used by the workstations to supplement their computing needs. Some processors may be permanently designated to be the compute servers. In addition, through an advertisement mechanism, any workstation may make itself temporarily available for a specific duration of time to be used as a compute server. In this paper, we present the design and implementation of a scheme for augmenting the UNIX® operating system with the location independent remote execution capability. This capability allows processes to be offloaded to the compute servers and preserves the execution environment of these processes as if they were still executing locally at the originating machine. Our model provides execution location independence of processes by preserving the process view of the file system, parent-child relationships, process groups, and process signaling across machine boundaries in a transparent way. We also present our scheme that allows processors to advertise themselves as available to some or all nodes in the network and withdraw as a compute server in a distributed manner. The scheme is robust in presence of node failures.

RAFT is a recursive algorithm for fault tolerance that uses a combination of dynamic space and time redundancy techniques for detecting faulty processors and recovering from errors. U * is a multicomputer testbed consisting of a network of AT&T 3B2 computers running a network operating system based on the UNIX system. This paper describes a software implementation of RAFT on U * , and demonstrates the effectiveness of a RAFT-like scheme for designing fault-tolerant multicomputer systems. Results of Monte Carlo experiments, conducted on this system that validated the theoretical basis of RAFT, are presented. Experimentally observed performance penalty, incurred due to fault tolerance, is also presented.

Article Free Access Share on Models for studying concurrency control performance: alternatives and implications Authors: Rakesh Agrawal AT&T Bell Laboratories, Murray Hill NJ AT&T Bell Laboratories, Murray Hill NJView Profile , Michael J. Carey Computer Sciences Department, University of Wisconsin, Madison WI Computer Sciences Department, University of Wisconsin, Madison WIView Profile , Miron Livny Computer Sciences Department, University of Wisconsin, Madison WI Computer Sciences Department, University of Wisconsin, Madison WIView Profile Authors Info & Claims SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of dataMay 1985 Pages 108–121https://doi.org/10.1145/318898.318909Published:01 May 1985Publication History 63citation638DownloadsMetricsTotal Citations63Total Downloads638Last 12 Months46Last 6 weeks7 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

Dunng the past decade.a number of database machme designs have been proposed Most of these desagns have been optamlzed wrth respect to retrreval querres, whrle rgnormg the issue of recovery and tts Impact on performance of the proposed archztecture In this paper, we propose several parallel recovery architectures for multaprocessor database machmes, examme the characterrstacs and performance of each, and evaluate thear Impact on the performance of the database machme Our results rndlcate that a recovery archatecture based on parallel loggmg has the best overall performance 1. llltroduction

In spite of the wide variety of concurrency control and recovery mechanisms proposed during the past decade, the behavior and the performance of various concurrency control and recovery mechanisms remain largely not well understood. In addition, although concurrency control and recovery mechanisms are intimately related, the interaction between them has not been adequately explored. In this paper, we take a unified view of the problems associated with concurrency control and recovery for transaction-oriented multiuser centralized database management systems, and we present several integrated mechanisms. We then develop analytical models to study the behavior and compare the performance of these integrated mechanisms, and we present the results of our performance evaluation.