This article addresses the challenges of using call detail record (CDR) data to study migration. Repurposing CDR data for this task have many advantages, including the lower costs of data collection and the potential for contemporaneous analysis. We present a framework for the repurposing and analysis of CDR data. We identify the home location of a subscriber, with corresponding confidence measures, and determine if the subscriber is a definite migrant, likely migrant, likely nonmigrant, or definite nonmigrant. A predictive model then uses mobility and social network features, extracted from the CDR data, to predict the individual decision to migrate. We are the first to address the challenging task of predicting the migration decision at the individual level. We also provide insight into features that can have an impact on the decision to migrate. An in-depth evaluation using CDR data from two provinces in Sri Lanka provides a granular map of migrant inflow and outflow. The success of our prediction model and the insights gained from the evaluation prepare the way for the repurposing of CDR data for social good with a focus on migration.

DSMM 2019 will explore the challenges of macro-modeling with financial and economic datasets. The workshop will also showcase the 2019 Financial Entity Identification and Information Integration (FEIII) Challenge which involves two challenge tasks, one over small business data and the other over customs data for shipping manifests.

Many real-world data sets are modeled as entity relationship graphs or heterogeneous information networks. In these graphs, nodes represent entities and edges mimic relationships. ObjectRank extends the well-known PageRank authority flow–based ranking method to entity relationship graphs using an authority flow weight vector (W). The vector W assigns a different authority flow–based importance (weight) to each edge type based on domain knowledge or personalization. In this paper, our contribution is a framework for Learning to Rank in entity relationship graphs to learn W, in the context of authority flow. We show that the problem is similar to learning a recursive scoring function. We present a two-phase iterative solution and multiple variants of learning. In pointwise learning, we learn W, and hence the scoring function, from the scores of a sample of nodes. In pairwise learning, we learn W from given preferences for pairs of nodes. To demonstrate our contribution in a real setting, we apply our framework to learn the rank, with high accuracy, for a real-world challenge of predicting future citations in a bibliographic archive—that is, the FutureRank score. Our extensive experiments show that with a small amount of training data, and a limited number of iterations, our Learning to Rank approach learns W with high accuracy. Learning works well with pairwise training data in large graphs.

Microblogs such as Twitter support a rich variety of user interactions using hashtags, urls, retweets and mentions. Microblogs are an exemplar of a hybrid network; there is an explicit network of followers, as well as an implicit network of users who retweet other users, and users who mention other users. These networks are important proxies for influence. In this paper, we develop a comprehensive behavioral model of an individual user and her interactions in the hybrid network. We choose a focal user and predict those users who will be influenced by her, and will retweet and/or mention the focal user, in the near future. We define a potential function, based on a hybrid network, which reflects the likelihood of a candidate user being influenced by, and having a specific type of link to, a focal user, in the future. We show that the potential function based prediction model converges to the Bonacich centrality metric. We develop a fast unsupervised solution which approximates the future hybrid network and the future Bonacich potential. We perform an extensive evaluation over a microblog network and a stream of tweets from Twitter. Our solution outperforms several baseline methods including ones based on singular value decomposition (SVD) and a supervised Ranking SVM.

Drug-target interaction studies are important because they can predict drugs' unexpected therapeutic or adverse side effects. In silico predictions of potential interactions are valuable and can focus effort on in vitro experiments. We propose a prediction framework that represents the problem using a bipartite graph of drug-target interactions augmented with drug-drug and target-target similarity measures and makes predictions using probabilistic soft logic (PSL). Using probabilistic rules in PSL, we predict interactions with models based on triad and tetrad structures. We apply (blocking) techniques that make link prediction in PSL more efficient for drug-target interaction prediction. We then perform extensive experimental studies to highlight different aspects of the model and the domain, first comparing the models with different structures and then measuring the effect of the proposed blocking on the prediction performance and efficiency. We demonstrate the importance of rule weight learning in the proposed PSL model and then show that PSL can effectively make use of a variety of similarity measures. We perform an experiment to validate the importance of collective inference and using multiple similarity measures for accurate predictions in contrast to non-collective and single similarity assumptions. Finally, we illustrate that our PSL model achieves state-of-the-art performance with simple, interpretable rules and evaluate our novel predictions using online data sets.

Authority flow techniques like PageRank and ObjectRank can provide personalized ranking of typed entity-relationship graphs. There are two main ways to personalize authority flow ranking: Node-based personalization, where authority originates from a set of user-specific nodes; edge-based personalization, where the importance of different edge types is user-specific. We propose the first approach to achieve efficient edge-based personalization using a combination of precomputation and runtime algorithms. In particular, we apply our method to ObjectRank, where a personalized weight assignment vector (WAV) assigns different weights to each edge type or relationship type. Our approach includes a repository of rankings for various WAVs. We consider the following two classes of approximation: (a) SchemaApprox is formulated as a distance minimization problem at the schema level; (b) DataApprox is a distance minimization problem at the data graph level. SchemaApprox is not robust since it does not distinguish between important and trivial edge types based on the edge distribution in the data graph. In contrast, DataApprox has a provable error bound. Both SchemaApprox and DataApprox are expensive so we develop efficient heuristic implementations, ScaleRank and PickOne respectively. Extensive experiments on the DBLP data graph show that ScaleRank provides a fast and accurate personalized authority flow ranking.

Topic detection with large and noisy data collections such as social media must address both scalability and accuracy challenges. KeyGraph is an efficient method that improves on current solutions by considering keyword cooccurrence. We show that KeyGraph has similar accuracy when compared to state-of-the-art approaches on small, well-annotated collections, and it can successfully filter irrelevant documents and identify events in large and noisy social media collections. An extensive evaluation using Amazon’s Mechanical Turk demonstrated the increased accuracy and high precision of KeyGraph, as well as superior runtime performance compared to other solutions.

We present a microblog recommendation system that can help monitor users, track conversations, and potentially improve diffusion impact. Given a Twitter network of active users and their followers, and historical activity of tweets, retweets and mentions, we build upon a prediction tool to predict the Top K users who will retweet or mention a focal user, in the future [10]. We develop personalized recommendations for each focal user. We identify characteristics of focal users such as the size of the follower network, or the level of sentiment averaged over all tweets; both have an impact on the quality of personalized recommendations. We use (high) betweenness centrality as a proxy of attractive users to target when making recommendations. Our recommendations successfully identify a greater fraction of users with higher betweenness centrality, in comparison to the overall distribution of betweenness centrality of the ground truth users for some focal user.

Annotation graph datasets are a natural representation of scientific knowledge. They are common in the life sciences and health sciences, where concepts such as genes, proteins or clinical trials are annotated with controlled vocabulary terms from ontologies. We present a tool, PAnG (Patterns in Annotation Graphs), that is based on a complementary methodology of graph summarization and dense subgraphs. The elements of a graph summary correspond to a pattern and its visualization can provide an explanation of the underlying knowledge. Scientists can use PAnG to develop hypotheses and for exploration.

The phenomenal growth of social media, both in scale and importance, has created a unique opportunity to track information diffusion and the spread of influence, but can also make efficient tracking difficult. Given data streams representing blog posts on multiple blog channels and a focal query post on some topic of interest, our objective is to predict which of those channels are most likely to contain a future post that is relevant, or similar, to the focal query post. We denote this task as the future author prediction problem (FAPP). This problem has applications in information diffusion for brand monitoring and blog channel personalization and recommendation. We develop prediction methods inspired by (naive) information retrieval approaches that use historical posts in the blog channel for prediction. We also train a ranking support vector machine (SVM) to solve the problem. We evaluate our methods on an extensive social media dataset; despite the difficulty of the task, all methods perform reasonably well. Results show that ranking SVM prediction can exploit blog channel and diffusion characteristics to improve prediction accuracy. Moreover, it is surprisingly good for prediction in emerging topics and identifying inconsistent authors.

We present a recommendation system for social media that draws upon monitoring and prediction methods. We use historical posts on some focal topic or historical links to a focal blog channel to recommend a set of authors to follow. Such a system would be useful for brand managers interested in monitoring conversations about their products. Our recommendations are based on a prediction system that trains a ranking Support Vector Machine (RSVM) using multiple features including the content of a post, similarity between posts, links between posts and/or blog channels, and links to external websites. We solve two problems, Future Author Prediction (FAP) and Future Link Prediction (FLP), and apply the prediction outcome to make recommendations. Using an extensive experimental evaluation on a blog dataset, we demonstrate the quality and value of our recommendations.

A variety of emerging online data delivery applications challenge existing techniques for data delivery to human users, applications, or middleware that are accessing data from multiple autonomous servers. In this paper, we develop a framework for formalizing and comparing pull-based solutions and present dual optimization approaches. The first approach, most commonly used nowadays, maximizes user utility under the strict setting of meeting a priori constraints on the usage of system resources. We present an alternative and more flexible approach that maximizes user utility by satisfying all users. It does this while minimizing the usage of system resources. We discuss the benefits of this latter approach and develop an adaptive monitoring solution Satisfy User Profiles (SUPs). Through formal analysis, we identify sufficient optimality conditions for SUP. Using real (RSS feeds) and synthetic traces, we empirically analyze the behavior of SUP under varying conditions. Our experiments show that we can achieve a high degree of satisfaction of user utility when the estimations of SUP closely estimate the real event stream, and has the potential to save a significant amount of system resources. We further show that SUP can exploit feedback to improve user utility with only a moderate increase in resource utilization.

As the social interaction of Internet users increases, so does the need to effectively rank social media. We study the challenges of personalized ranking of blog posts. Web search techniques are inadequate since social media lack many of the characteristics of the Web such as rich document content and an extensive hyperlink graph. Further, user behavior in social media has moved beyond keyword based search and must support users who follow a particular blog or theme. In this research, we extend a social media dataset to exploit the associations between authors, blog posts, and categories (topics) of the posts. We then apply personalized authority flow based ranking algorithms based on the random surfer model. We evaluate our personalization approaches through an extensive study on a range of virtual users whose preferences are defined based on intuitive criteria. Our evaluation shows that the accuracy of our personalized recommendations ranges from good to very good for a majority of users, and outperforms reasonable baseline approaches.

There has been an explosion of hyperlinked data in many domains, e.g., the biological Web. Expressive query languages and effective ranking techniques are required to convert this data into browsable knowledge. We propose the Graph Information Discovery (GID) framework to support sophisticated user queries on a rich web of annotated and hyperlinked data entries, where query answers need to be ranked in terms of some customized ranking criteria, e.g., PageRank or ObjectRank. GID has a data model that includes a schema graph and a data graph, and an intuitive query interface. The GID framework allows users to easily formulate queries consisting of sequences of hard filters (selection predicates) and soft filters (ranking criteria); it can also be combined with other specialized graph query languages to enhance their ranking capabilities. GID queries have a well-defined semantics and are implemented by a set of physical operators, each of which produces a ranked result graph. We discuss rewriting opportunities to provide an efficient evaluation of GID queries. Soft filters are a key feature of GID and they are implemented using authority flow ranking techniques; these are query dependent rankings and are expensive to compute at runtime. We present approximate optimization techniques for GID soft filter queries based on the properties of random walks, and using novel path-length-bound and graph-sampling approximation techniques. We experimentally validate our optimization techniques on large biological and bibliographic datasets. Our techniques can produce high quality (Top K) answers with a savings of up to an order of magnitude, in comparison to the evaluation time for the exact solution.

Web monitoring 2.0 supports the complex information needs of clients who probe multiple information sources and generate mashups by integrating across these volatile streams. A proxy that aims at satisfying multiple customized client profiles will face a scalability challenge in trying to maximize the number of clients served while at the same time fully satisfying complex client needs. In this paper, we introduce an abstraction of complex execution intervals, a combination of time intervals and information streams, to capture complex client needs. Given some budgetary constraints (e.g., bandwidth), we present offline algorithmic solutions for the problem of maximizing completeness of capturing complex profiles.

Customized semantic query answering, personalized search, focused crawlers and localized search engines frequently focus on ranking the pages contained within a subgraph of the global Web graph. The challenge for these applications is to compute PageRank-style scores efficiently on the subgraph, i.e., the ranking must reflect the global link structure of the Web graph but it must do so without paying the high overhead associated with a global computation. We propose a framework of an exact solution and an approximate solution for computing ranking on a subgraph. The IdealRank algorithm is an exact solution with the assumption that the scores of external pages are known. We prove that the IdealRank scores for pages in the subgraph converge. Since the PageRank-style scores of external pages may not typically be available, we propose the ApproxRank algorithm to estimate scores for the subgraph. Both IdealRank and ApproxRank represent the set of external pages with an external node L1and extend the subgraph with links to L1. They also modify the PageRank-style transition matrix with respect to L1. We analyze the L1distance between IdealRank scores and ApproxRank scores of the subgraph and show that it is within a constant factor of the L1distance of the external pages (e.g., the true PageRank scores and uniform scores assumed by ApproxRank). We compare ApproxRank and a stochastic complementation approach (SC), a current best solution for this problem, on different types of subgraphs. ApproxRank has similar or superior performance to SC and typically improves on the runtime performance of SC by an order of magnitude or better. We demonstrate that ApproxRank provides a good approximation to PageRank for a variety of subgraphs.

Emerging applications on the Web require better management of volatile data in pull-based environments. In a pull based setting, data may be periodically removed from the server. Data may also become obsolete, no longer serving client needs. In both cases, we consider such data to be volatile. To model such constraints on data usability, and support complex user needs we define profiles to specify which data sources are to be monitored and when. Using a novel abstraction of execution intervals we model complex profiles that access simultaneously several servers to gain from the used data. Given some budgetary constraints (e.g., bandwidth), the paper formalizes the problem of maximizing completeness.

This paper presents a middleware data delivery setting with a proxy that is required to maximize the completeness of captured updates, specified in its clients' profiles, while minimizing at the same time the delay in delivering the updates to clients. The two objectives may conflict when the monitoring budget is limited. Therefore, any solution should consider this tradeoff in satisfying both objectives. We term this problem the "proxy dilemma" and formalize it as a biobjective optimization problem. Such problem occurs in many contemporary applications, such as mobile and sensor networks, and poses scalability challenges in delivering up-to-date data from remote resources to meet client specifications. We present a Pareto set as a formal solution to the proxy dilemma. We discuss the complexity of generating a Pareto set for the proxy dilemma and suggest an approximation scheme to this problem.

Authority flow is an effective ranking mechanism for answering queries on a broad class of data. Systems have been developed to apply this principle on the Web (PageRank and topic sensitive PageRank), bibliographic databases (ObjectRank), and biological databases (Hubs of Knowledge project). However, these systems have the following drawbacks: (a) There is no way to explain to the user why a particular result received its current score; (b) The authority flow rates, which have been shown to dramatically affect the results' quality in ObjectRank, have to be set manually by a domain expert; (c) There is no query reformulation methodology to refine the query results according to the user's preferences. In this work, we address these shortcomings by introducing a framework and algorithms to explain query results and reformulate authority flow queries based on the user's feedback. The query reformulation process can be used to learn the user's preferences and automatically adjust the authority flow rates to facilitate personalized authority flow searching. We experimentally evaluate our algorithms in terms of performance and quality.

A WAN environment, such as the Internet, connects a federation of hundreds of servers with tens of thousands of clients, which poses a substantial scalability challenge. Clients may choose among sources that vary in both their content and quality as well as in their access latencies. At the same time, Internet accessible data sources exhibit transient behavior; the unpredictable behavior of a dynamic WAN results in a wide variability in access cost (end-to-end latency). This motivates a need for a source selection strategy that requires maintaining access cost distributions (latency profiles) for each client/server pair. However, in the presence of hundreds of servers and thousands of clients, managing latency profiles cannot scale. We present a scalable methodology to manage latency profiles that use non-random associations between client/server pairs. Such non-random associations may be identified by topology-independent measures such as correlation and mutual information. We propose a Catalog infrastructure that implements our methodology and utilize non-randomly associated latency profiles to estimate access cost distribution for client/server pairs. We perform an extensive experimental study demonstrating feasibility and efficiency of our approach.

We consider a virtual computing environment that provides computational resources on demand to users with multi attribute task descriptions that include a valuation, resource (CPU) needs and a completion deadline. Achieving a high quality of service in this environment depends on finding a balance between processing high priority tasks before their deadlines expire, while maximizing resource utilization. The problem becomes more challenging in an economic setting, where the task valuation is private. We propose a bid-based server that publishes a history of the success rate table (SRT) for processed tasks. Clients use the history to optimize their bid for resources on a (single) multiprocessor server. The server schedules tasks in descending order of their bid- Highest Bid First (HBF) and backfills the schedule with smaller tasks when resources are still available. The scheduler follows a hard deadline model where tasks cannot be processed after their deadline. We propose three variations of the SRT where biding history is publicized at different granularity. Using a simulation based study, we analyze the behavior of clients' bids in respond to the SRT. We compare the best HBF variant with an efficient Earliest Deadline First (EDF) mechanism that charges a fixed price. Our results show that the HBF mechanism is able to exploit price discrimination and therefore complete the execution of more high value jobs under a heavy workload, leading to better weighted throughput. HBF can also maximize server profit and client surplus (the difference between value and the client bid) in different settings. Thus, HBF may yield solutions that benefit both the client and the server.

Wide area data delivery requires timely propagation of up-to-date information to thousands of clients over a wide area network. Applications include web caching, RSS source monitoring, and email access via a mobile network. Data sources vary widely in their update patterns and may experience different update rates at different times or unexpected changes to update patterns. Traditional data delivery solutions are either push-based, which requires servers to push updates to clients, or pull-based, which require clients to check for updates at servers. While push-based solutions ensure timely data delivery, they are not always feasible to implement and may not scale to a large number of clients. In this article, we present adaptive pull-based policies that explicitly aim to reduce the overhead of contacting remote servers, compared to existing pull-based policies, while meeting freshness requirements. We model updates to data sources using update histories, and present two novel history-based policies to estimate when updates occur; they are based on individual history and aggregate history. These policies are presented within an architectural framework that supports their deployment either client-side or server-side. We further develop two adaptive policies to handle objects that initially may have insufficient history or objects that experience changes in update patterns. Extensive experimental evaluation using three data traces from diverse applications shows that history-based policies can reduce contact between clients and servers by up to 60% compared to existing pull-based policies while providing a comparable level of data freshness. Our experiments further demonstrate that our adaptive policies can select the best policy to match the behavior of an object and perform better than any individual policy, thus they dominate standalone policies.

Links in life science sources capture important biological knowledge. However, current simple physical link implementations do not explicitly represent this knowledge so that it can be easily shared among scientists. We develop a methodology for link extraction and generation, and link labeling to produce an enhanced e-link. The e-link associates each existing link with a link label that captures semantics of the link. We develop a machine assisted tool for curators to produce e-links and we develop a search interface for biologists to discover interesting e-links.

The availability of massive datasets, comprising sensor measurements or the results of scientific simulations, has had a significant impact on the methodology of scientific reasoning. Scientists require storage, bandwidth and computational capacity to query and analyze these datasets, to understand physical phenomena or to test hypotheses. This paper addresses the challenge of identifying and selecting resources to develop an evaluation plan for large scale data analysis queries when data processing capabilities and datasets are dispersed across nodes in one or more computing and storage clusters. We show that generating an optimal plan is hard and we propose heuristic techniques to find a good choice of resources. We also consider heuristics to cope with dynamic resource availability; in this situation we have stale information about reusable cached results (datasets) and the load on various nodes.

Life sciences sources are characterized by a complex graph of overlapping sources, and multiple alternate links between sources. A (navigational) query may be answered by traversing multiple alternate paths between a start source and a target source. Each of these paths may have dissimilar benefit, e.g., the cardinality of result objects that are reached in the target source. Paths may also have dissimilar costs of evaluation, i.e., the execution cost of a query evaluation plan for a path. In prior research, we developed ESearch, an algorithm based on a Deterministic Finite Automaton (DFA), which exhaustively enumerates all paths to answer a navigational query. The challenge is to develop heuristics that improve on the exhaustive ESearch solution and identify good utility functions that can rank the sources, the links between sources, and the sub-paths that are already visited, in order to quickly produce paths that have the highest benefit and the least cost. In this paper, we present a heuristic that uses local utility functions to rank sources, using either the benefit attributed to the source, the cost of a plan using the source, or both. The heuristic will limit its search to some Top XX% of the ranked sources. To compare ESearch and the heuristic, we construct a Pareto surface of all dominant solutions produced by ESearch, with respect to benefit and cost. We choose the Top 25% of the ESearch solutions that are in the Pareto surface. We compare the paths produced by the heuristic to this Top 25% of ESearch solutions with respect to precision and recall. This motivates the need for further research on developing a more efficient algorithm and better utility functions.

Recent technology advances have enabled mediated query processing with Internet accessible WebSources. A characteristic of WebSources is that their access costs exhibit transient behavior These costs depend on the network and server workloads, which are often affected by, the time of day,, day, etc. Given transient behavior, an appropriate performance target (PT) for a noisy, environment will correspond to "at least X percentage of queries will have a latency of less than T units of time". In this paper we propose an optimizer strategy that is sensitive to the objective of meeting such performance targets (PT). For each query plan, a PT sensitive optimizer uses both the expected value of the cost distribution of the plan, as well as the expected delay, of the plan. We validate our strategy using a simulation based study of the optimizers behavior. We also experimentally validate the optimizer using traces of access costs for real WebSources.

We consider an architecture of mediators and wrappers for Internet accessible WebSources of limited query capability. Each call to a source is a WebSource Implementation (WSI) and it is associated with both a capability and (a possibly dynamic) cost. The multiplicity of WSIs with varying costs and capabilities increases the complexity of a traditional optimizer that must assign WSIs for each remote relation in the query while generating an (optimal) plan. We present a two-phase Web Query Optimizer (WQO). In a pre-optimization phase, the WQO selects one or more WSIs for a pre-plan; a pre-plan represents a space of query evaluation plans (plans) based on this choice of WSIs. The WQO uses cost-based heuristics to evaluate the choice of WSI assignment in the pre-plan and to choose a good pre-plan. The WQO uses the pre-plan to drive the extended relational optimizer to obtain the best plan for a pre-plan. A prototype of the WQO has been developed. We compare the effectiveness of the WQO, i.e., its ability to efficiently search a large space of plans and obtain a low cost plan, in comparison to a traditional optimizer. We also validate the cost-based heuristics by experimental evaluation of queries in the noisy Internet environment.

Today, scientific data is inevitably digitized, stored in a variety of heterogeneous formats, and is accessible over the Internet. Scientists need to access an integrated view of multiple remote or local heterogeneous data sources. They then integrate the results of complex queries and apply further analysis and visualization to support the task of scientific discovery. Building a digital library for scientific discovery requires accessing and manipulating data extracted from flat files or databases, documents retrieved from the Web, as well as data that is locally materialized in warehouses or is generated by software. We consider several tasks to provide optimized and seamless integration of biomolecular data. Challenges to be addressed include capturing and representing source capabilities; developing a methodology to acquire and represent metadata about source contents and access costs; and decision support to select sources and capabilities using cost based and semantic knowledge, and generating low cost query evaluation plans.

We demonstrate a Web Query Optimizer (WQO) within an architecture of mediators and wrappers, for WebSources of limited capability in a wide area environment. The WQO has several innovative features, including a CBR (capability based rewriting) tool, an enhanced randomized relational optimizer extended to a Web environment, and a WebWrapper cost model that can provide relevant metrics for accessing WebSources. The prototype has been tested against a number of WebSources.

We present a technique for transferring query optimization techniques, developed for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expressed in OQL. The object schema is represented using a logical representation (Datalog). Semantic knowledge about the object data model, e.g., class hierarchy information, relationship between objects, etc., as well as semantic knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic query and query optimization is performed in the Datalog representation. We obtain equivalent (optimized) logic queries, and subsequently obtain equivalent (optimized) OQL queries for each equivalent logic query. We present one optimization technique for semantic query optimization (SQO) based on the residue technique of U. Charavarthy et al. (1990; 1986; 1988). We show that our technique generalizes previous research on SQO for object databases. We handle a large class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain contradictions and simplify queries, e.g., by eliminating joins, or by reducing the access scope for evaluating a query to some specific subclass(es). We also demonstrate how the definition of a method or integrity constraints describing the method, can be used in optimizing a query with a method.

The rapid growth of the Internet and support for interoperability protocols has increased the number of Web accessible sources, WebSources. Current wrapper mediator architectures need to be extended with a Wrapper Cost Model (WCM) for WebSources that can estimate the response time (delays) to access sources as well as other relevant statistics. In this paper we present a Web Prediction Tool (WebPT), that is used by the WCM to estimate delays. We compare WebPT learning with the more traditional Neural Network (NN) learning, for this environment. Both the WebPT and the NN learning is based on query feedback (qfb) of response times from accessing WebSources. Experiment data was collected from several sources, and those dimensions that were significant in estimating the response time were determined This includes Time of day, Day, and Quantilty of data. Both the WebPT and the NN use these dimensions to learn response times (delay) from a particular source, and then to predict the expected response times for some query. We note that the WebPT learning is always online, i.e., it learns from each new query feedback. NN training can be online (per-pattern learning), which is time consuming and can be very sensitive to the choice of training parameters. The more common and robust learning is of fine batch learning (per-epoch). We compared the WebPT learning with both types of NN learning, in a number of experiments. The ease of training the WebPT makes it preferable compared to the per-pattern NN. Further the prediction error of both the WebPT and the NN was comparable We conclude that both the online WebPT and the more sophisticated NN learning are useful in constructing a Wrapper Cost Model for the dynamic Web environment.

There is an increase in the number of data sources that can be queried across the WWW. Such sources typically support HTML forms-based interfaces and search engines query collections of suitably indexed data. The data is displayed via a browser: One drawback to these sources is that there is no standard programming interface suitable for applications to submit queries. Second, the output (answer to a query) is not well structured. Structured objects have to be extracted from the HTML documents which contain irrelevant data and which may be volatile. Third, domain knowledge about the data source is also embedded in HTML documents and must be extracted. To solve these problems, we present technology to define and (automatically) generate wrappers for Web accessible sources. Our contributions are as follows: (1) Defining a wrapper interface to specify the capability of Web accessible data sources. (2) Developing a wrapper generation toolkit of graphical interfaces and specification languages to specify the capability of sources and the functionality of the wrapper (3) Developing the technology to automatically generate a wrapper appropriate to the Web accessible source, from the specifications.

Current mediator and wrapper architectures do not have the flexibility to scale to multiple wrapped sources, where some sources may be redundant, and some sources may provide incomplete answers to a query. We propose a meta-wrapper component which is capable of handling multiple wrapped sources, in a particular domain, where the multiple sources provide related information. The meta-wrapper makes these sources transparent to the mediator and provides a single meta-wrapper interface for all these sources. Source descriptions specify the content and query capability of the sources. These are used to determine the meta-wrapper interface and to decide which queries from a mediator can be accepted. Sources are partitioned into equivalence classes, based on their descriptions. These equivalence classes are partially ordered, and the lattices that correspond to these orderings are used to identify the relevant sources for a query submitted by the mediator. If there is redundancy of the sources, the meta-wrapper identifies alternate sources for the query. A meta-wrapper cost model is then used to select among alternate relevant sources and choose the best plan.

Accessing many data sources aggravates problems for users of heterogeneous distributed databases. Database administrators must deal with fragile mediators, that is, mediators with schemas and views that must be significantly changed to incorporate a new data source. When implementing translators of queries from mediators to data sources, database implementers must deal with data sources that do not support all the functionality required by mediators. Application programmers must deal with graceless failures for unavailable data sources. Queries simply return failure and no further information when data sources are unavailable for query processing. The Distributed Information Search COmponent (Disco) addresses these problems. Data modeling techniques manage the connections to data sources, and sources can be added transparently to the users and applications. The interface between mediators and data sources flexibly handles different query languages and different data source functionality. Query rewriting and optimization techniques rewrite queries so they are efficiently evaluated by sources. Query processing and evaluation semantics are developed to process queries over unavailable data sources. In this article, we describe: 1) the distributed mediator architecture of Disco; 2) the data model and its modeling of data source connections; 3) the interface to underlying data sources and the query rewriting process; and 4) query processing semantics. We describe several advantages of our system.

Presents a technique for semantic query optimization (SQO) for object databases. We use the ODMG-93 (Object Data Management Group) standard ODL (Object Database Language) and OQL (Object Query Language) languages. The ODL object schema and the OQL object query are translated into a DATALOG representation. Semantic knowledge about the object model and the particular application is expressed as integrity constraints. This is an extension of the ODMG-93 standard. SQO is performed in the DATALOG representation, and an equivalent logic query and (subsequently) an equivalent OQL object query are obtained. SQO is based on the residue technique of Chakravarthy et al. (1990). We show that our technique generalizes previous research on SQO for object databases. It can be applied to queries with structure constructors and method application. It utilizes integrity constraints about keys, methods and knowledge of access support relations, to produce equivalent queries, which may have more efficient evaluation plans.

The Distributed Information Search COmponent (DISCO) is a prototype heterogeneous distributed database that accesses underlying data sources. The DISCO prototype currently focuses on three central research problems in the context of these systems. First, since the capabilities of each data source is different, transforming queries into subqueries on data source is difficult. We call this problem the weak data source problem. Second, since each data source performs operations in a generally unique way, the cost for performing an operation may vary radically from one wrapper to another. We call this problem the radical cost problem. Finally, existing systems behave rudely when attempting to access an unavailable data source. We call this problem the ungraceful failure problem.

Access to large numbers of data sources introduces new problems for users of heterogeneous distributed databases. End users and application programmers must deal with unavailable data sources. Database administrators must deal with incorporating new sources into the model. Database implementers must deal with the translation of queries between query languages and schemas. The Distributed Information Search COmponent (Disco) addresses these problems. Query processing semantics are developed to process queries over data sources which do not return answers. Data modeling techniques manage connections to data sources. The component interface to data sources flexibly handles different query languages and translates queries. This paper describes (a) the distributed mediator architecture of Disco, (b) its query processing semantics, (C) the data model and its modeling of data source connections, and (d) the interface to underlying data sources.

We consider Cooperative Information Systems (CIS) that are multidatabase systems (MDBMS), with a common object-oriented model, based on the ODMG standard, together with local databases that may be relational, object-oriented, or dedicated data servers. The MDBMS interface (or mediator interface) that describes this CIS could be different from the union of the local interfaces that describe each local database. In particular, the mediator interface may be defined by semantic knowledge that includes views over particular local databases, integrity constraints, and knowledge about data replication in local databases. We present a methodology for query reformulation which is based on the uniform representation of all semantic knowledge in the form of integrity assertions and mapping rules. A reformulation algorithm exploits this semantic knowledge, and performs semantic rewriting based on pattern-matching, to obtain a query on the union of the local interfaces. A decomposition algorithm then produces a composite query, and local sub-queries, one for each local interface. The reformulation is general enough to re-use the results of previously computed queries in the CIS. We have implemented this reformulation technique in our Flora compiler prototype which we used for validation and experimentation with O2 databases.

In this paper, we present our research on defining a correct semantics for a class of update rule (UR) programs, and discuss implemanting these programs in a DBMS environment. Update rules execute by updating relations in a database which may cause the further execution of rules. A correct semantics must guarantee that the execution of the rules will terminate and that it will produce a minimal updated database. The class of UR programs is syntactically identified, based upon a concept that is similar to stratification. We extend that strict definition of stratification and allow a relaxed criterion for partitioning of the rules in the UR program. This relaxation allows a limited degree of nondeterminism in rule execution. We define an execution semantics based upon a monotonic fixpoint operator T UR , resulting in a set of fixpoints for UR. The monotionicity of the operator is maintained nby explicitly representing the effect of asserting and retracting tuples in the database. A declarative semantics for the update rule program is obtained by associating a normal logic program UR to represent the UR program. We use the stable model semantics which characterize a normal logic program by a set of minimal models which are called stable models. We show the equivalence between the set of fixpoints for UR and the set of stable models for UR. We briefly discuss implementing the fixpoint semantics of the UR program in a DBMS environment. Relations that can be updated by the rules are updatable relations and they are extended with two flags. An update rule is represented by a database query, which queries the updatable relations as well as database relaions, i.e., those relations which are not update by rules. We describe an algorithm to process the queries and compute a fixpoint in the DBMS environment and obtain a final database.

We develop an efficient algorithm for the query interoperation among existing heterogeneous object-oriented and relational databases. Our algorithm utilizes a canonical deductive database as a uniform representation of object-oriented schema and data. High-order object queries are transformed to the canonical deductive database in which they are partially evaluated and optimized, before being translated to relational queries. Our algorithm can be incorporated into object-oriented interfaces to relational databases or object-oriented federated databases to support object queries to heterogeneous relational databases.>

In this paper, we develop techniques for interoperable query processing between object and relational schemas. The objective is to pose a query against a local object schema and be able to share information transparently from target relational databases. Our approach is a mapping approach (as opposed to a global schema approach) and is based on using canonical representations (CR). We use one CR for resolving heterogeneity based on the object and relational query languages. We use a second parameterized CR to resolve representational heterogeneity between object and relational schema, and to build a mapping knowledge dictionary. There is also a set of mapping rules, based on the parameters of the CR, which defines the appropriate mapping between schemas. A query posed against the local object schema is first represented in the CR for queries, and then transformed by the mapping rules, to an appropriate query for the target relational schema, using relevant information from the mapping knowledge dictionary. The use of the parameterized CR allows us to build the mapping knowledge dictionary easily, and allows reusability of the mapping rules.

This paper describes a technique for information mediation when multiple heterogeneous knowledge and data servers are to be accessed during query processing. One problem is building an intelligent interface between each knowledge server (KS) and its processor (KP); and the second is to provide interoperability among multiple KP/KS so that a query may be answered using information from multiple sources. We present example scenarios which highlight these problems and then outline query mapping and transformation techniques that are applicable. The techniques for solving the interoperability problems involve representations in some canonical form. This includes a canonical representation (CR) corresponding to each KP/KS pair and a merged CR (MCR) to represent the mapping among the CRs. The MCR and CRs include relevant information obtained from a source query, and heterogeneous mapping (het-map) information, for all possible mappings among the multiple servers. The knowledge in the canonical form must be represented so that it can be easily during query transformation.

Methods for storing and manipulating large rule bases using a relational database management systems (DBMS) are discussed. An approach to decomposing and storing the condition elements in the antecedents of rules such as those used in production rule-based systems is presented. A set-oriented approach, DBCond, which uses a special data structure that is implemented using relations is proposed. A matching algorithm for DBCond uses the relational structures to efficiently identify rules whose antecedents are satisfied. The performance of DBCond is compared with that of DBRete, a DBMS implementation of the Rete match algorithm developed for use with the production rule language OPS5. DBCond is also compared with DBQuery, a method that is based on evaluating queries corresponding to the conditions in the antecedents of the rules. Improvements to the data structure and the algorithms of the DBCond method are described. An advantage of DBCond is that it is fully parallelizable, thus making it attractive for parallel computing environments.>

Issues pertinent to the concurrent execution of rules in a database management system (DBMS) are studied. Rules are modeled as database transactions. As such, they should follow serializability as their correctness criterion for execution. Rule execution has the additional constraint that the rules, conditions must be true in the database for the actions that execute, and rules must fail when their conditions are not true any longer. Based on this observation, two locking-based protocols are discussed. Information on the possible conflicts between conditions and actions of rules is used to provide greater concurrent access to the relations, based on a new lock paradigm. A simulation testbed was developed in order to study the rule features and database characteristics that play an important role in the performance of concurrent production rule execution.>

Achieving efficiency in database management functions is a fundamental problem underlying many computer applications. Efficiency is difficult to achieve using the traditional general-purpose von Neumann processors. Recent advances in microelectronic technologies have prompted many new research activities in the design, implementation, and application of database machines which are tailored for processing database management functions. To build an efficient system, the software algorithms designed for this type of system need to be tailored to take advantage of the hardware characteristics of these machines. Furthermore, special hardware units should be used, if they are cost- effective, to execute or to assist the execution of these software algorithms.