Over the last few decades, simple graphs have been extensively used for studying complex systems of interacting entities from diverse disciplines, such as social networks, transportation, epidemiology, etc. However, when studying data with multiple types of entities, relationships, and features, simple (or even attributed) graphs are not always sufficient. For example, to study accident patterns to take mitigating actions, one needs to explore accident patterns based on factors like weather (rain, sunny, sleet, etc.), light, and road surface conditions in different geographical regions. As another example, to find individuals who are influential across multiple social media, a single graph approach is not well-suited. Indeed, to model such multiple relationships, multiple related graphs are useful. This can be done using multilayer networks (MLNs). Any complex data analysis can immensely benefit from interactive graphic tools rather than working with raw data in command prompt mode. This is especially true as data and models become increasingly complex. To interpret and understand the results of analysis, drill-down, and visualization become critical. The MLN-Dashboard (called MLN-geeWhiz) presented in this demo paper aims to facilitate all aspects of MLN layer generation, analysis, and visualization through an intuitive, interactive web-based dashboard. In this paper, we discuss the dashboard, its architecture, the functionality currently supported, and some use cases.

Covid Wizard or CoWiz is a Covid-19 visualization dashboard based on Multilayer Network (MLN) analysis underneath1. Online dashboards typically plot/visualize statistical information gleaned from raw data, such as daily cases, deaths, recoveries, tests, etc. However, for a better understanding, we need aggregate analysis (e.g., community, centrality) and its visualization which is the purpose of CoWiz. As an example, grouping counties across a country/region based on similarity of increase/decrease in cases, deaths, hospitalizations over intervals is not possible without aggregate analysis. This is where CoWiz utilizes community and other concepts over MLNs that are inferred from Covid and other relevant data sets for visualization.This demo presents a flexible, interactive dashboard which is capable of visualizing various aspects of Covid-19 data, including composition of Covid data with demographics (population density, education level, average earning, vehicle movements, and change in purchase patterns) at the granularity of county for USA. This paper elaborates on the types of analysis, underlying model, and how a flexible visualization dashboard has been developed using open source software and data sets. As new data becomes available, they can be incorporated into the visualization with no manual intervention.

At the core of graph mining lies independent expansion of substructures where a substructure (also referred to as a subgraph) independently grows into a number of larger substructures in each iteration. Such an independent expansion, invariably, leads to the generation of duplicates. In the presence of graph partitions, duplicates are generated both within and across partitions. Eliminating these duplicates (for correctness) not only incurs generation and storage cost but also additional computation for its elimination. Our primary aim is to design techniques to reduce generating duplicate substructures as we show that they cannot be eliminated. This paper introduces three constraint-based optimization techniques, each significantly improving the overall mining cost by reducing the number of duplicates generated. These alternatives provide flexibility to choose the right technique based on graph properties. We establish theoretical correctness of each technique as well as its analysis with respect to graph characteristics such as degree, number of unique labels, and label distribution. We also investigate the applicability of their combination for improvements in duplicate reduction. Finally, we discuss the effects of the constraints with respect to the partitioning schemes used in graph mining. Our experiments demonstrate significant benefits of these constraints in terms of storage, computation, and communication cost (specific to partitioned approaches) across graphs with varied characteristics.

With the emergence of the deep web, searching web databases in domains such as vehicles, real estate, etc., has become a routine task. One of the problems in this context is ranking the results of a user query. Earlier approaches for addressing this problem have used frequencies of database values, query logs, and user profiles. A common thread in most of these approaches is that ranking is done in a user- and/or query-independent manner. This paper proposes a novel query- and user-dependent approach for ranking query results in web databases. We present a ranking model, based on two complementary notions of user and query similarity, to derive a ranking function for a given user query. This function is acquired from a sparse workload comprising of several such ranking functions derived for various user-query pairs. The model is based on the intuition that similar users display comparable ranking preferences over the results of similar queries. We define these similarities formally in alternative ways and discuss their effectiveness analytically and experimentally over two distinct web databases.

Social tagging recommendation is an urgent and useful enabling technology for Web 2.0. In this paper, we present a systematic study of low-order tensor decomposition approach that are specifically targeted at the very sparse data problem in tagging recommendation problem. Low-order polynomials have low functional complexity, are uniquely capable of enhancing statistics and also avoids over-fitting than traditional tensor decompositions such as Tucker and Parafac decompositions. We perform extensive experiments on several datasets and compared with 6 existing methods. Experimental results demonstrate that our approach outperforms existing approaches.

This paper presents a novel framework for multi-folder email classification using graph mining as the underlying technique. Although several techniques exist (e.g., SVM, TF-IDF, n-gram) for addressing this problem in a delimited context, they heavily rely on extracting high-frequency keywords, thus ignoring the inherent structural aspects of an email (or document in general) which can play a critical role in classification. Some of the models (e.g., n-gram) consider only the words without taking into consideration where in the structure these words appear together. This paper presents a supervised learning model that leverages graph mining techniques for multi-folder email classification. A ranking formula is presented for ordering the representative - common and recurring - substructures generated from pre-classified emails. These ranked representative substructures are then used for categorizing incoming emails. This approach is based on a global ranking model that incorporates several relevant parameters for email classification and overcomes numerous problems faced by extant approaches used for multi-folder classification. A number of parameters which influence the generation of representative substructures are analyzed, reexamined, and adapted to multiple folders. The effect of graph representations has been analyzed. The effectiveness of the proposed approach has been validated experimentally.

Most of the routing and replication algorithms assume the network to be large and therefore, the architecture and algorithms are designed to be scalable. These algorithms however may not perform well with limited number of nodes in a network of UAVs. It is better to design and simulate such algorithms to increase the efficiency in a small network as scalability is no longer an issue. For such networks, we present design and simulation of some effective routing and replication algorithms to route packets, disseminate information, and replicate data among nodes.

Algorithms defining similarities between objects of an information network are important of many IR tasks. SimRank algorithm and its variations are popularly used in many applications. Many fast algorithms are also developed. In this note, we first reformulate them as random walks on the network and express them using forward and backward transition probably in a matrix form. Second, we show that P-Rank (SimRank is only the special case of P-Rank) has a unique solution of eeT when decay factor c is equal to 1. We also show that SimFusion algorithm is a special case of P-Rank algorithm and prove that the similarity matrix of SimFusion is the product of PageRank vector. Our experiments on the web datasets show that for P-Rank the decay factor c doesn't seriously affect the similarity accuracy and accuracy of P-Rank is also higher than SimFusion and SimRank.

Network fault management has been an active research area for a long period of time because of its complexity, and the returns it generates for service providers. However, most fault management systems are currently custom-developed for a particular domain. As communication service providers continuously add greater capabilities and sophistication to their systems in order to meet demands of a growing user population, these systems have to manage a multi-layered network along with its built-in legacy logical processing procedure. Stream processing has been receiving a lot of attention to deal with applications that generate large amounts of data in real-time at varying input rates and to compute functions over multiple streams, such as network fault management. In this paper, we propose an integrated inter-domain network fault management system for such a multi-layered network based on data stream and event processing techniques. We discuss various components in our system and how data stream processing techniques are used to build a flexible system for a sophisticated real-world application. We further identify a number of important issues related to data stream processing during the course of the discussion of our proposed system, which will further extend the boundaries of data stream processing.

In this paper we propose a novel approach that uses structure as well as the content of emails in a folder for email classification. Our approach is based on the premise that representative - common and recurring -structures/patterns can be extracted from a pre-classified email folder and the same can be used effectively for classifying incoming emails. A number of factors that influence representative structure extraction and the classification are analyzed conceptually and validated experimentally. In our approach, the notion of inexact graph match is leveraged for deriving structures that provide coverage for characterizing folder contents. Extensive experimentation validate the selection of parameters and the effectiveness of our approach for email classification.

No abstract available.

Currently, stream data processing is an active area of research, which includes everything from algorithms and architectures for stream processing to modelling, and analysis of various components of a stream processing system. In this paper, we present an analysis of relational operators used for stream processing using queueing theory and study behaviors of streaming data in a query processing system. Our approach enables us to compute the fundamental performance metrics of relational operators ---select, project, and join over data streams. Furthermore, this approach establishes a way to find the probability distribution functions of both the number of tuples and the waiting time of tuples in the system. Finally, we designed and implemented a number of experiments to validate the accuracy and effectiveness of our analysis.

This work addresses data warehouse maintenance, i.e. how changes to autonomous, heterogeneous, and distributed sources should be detected and propagated to a warehouse. The research community has mainly addressed issues relating to the internal operation of data warehouse servers. Work related to data warehouse maintenance has received less attention and only a limited set of maintenance alternatives are considered while ignoring the autonomy and heterogeneity of sources.In this paper, we extend work on single source view maintenance to views with multiple heterogeneous sources. We present a tool (PAM) which allows for comparison of a large number of relevant maintenance policies under different configurations. Based on such analysis and previous studies we propose a set of heuristics to guide in policy selection. The quality of these heuristics is evaluated empirically using a test-bed developed for this purpose. This is done for a number of different criteria and for different data sources and computer systems. The performance gained using the policy selected through the heuristics is compared with the performance of all identified policies. Based on these experiments we claim that heuristic-based selections are good.

We address data warehouse maintenance, i.e. how changes to autonomous sources should be detected and propagated to a warehouse. We have extended our work on source characteristics and timings relevant to single source views by exploring data integration from (multiple) heterogeneous sources. We identify relevant maintenance policies and develop a set of heuristics to guide policy choice. On the basis of empirical (testbed) experiments, we claim that resulting selections are good.

Event-condition-action (or ECA) rules are used to capture active capability. While a number of research prototypes of active database systems have been built, ECA rule capability in relational DBMSs is still very limited. We address the problem of turning a traditional database management system into a full-fledged active database system without changing the underlying system. The advantages of this approach are: transparency; ability to and active capability without changing the client programs; retain relational DBMS's underlying functionality; and persistence of ECA rules using the native database functionality. We describe how complete active database semantics can be supported on an existing SQL server (Sybase, in our case) by adding a mediator, termed ECA Agent, between the SQL server and the clients. ECA rules are fully supported through the ECA Agent without changing applications or the SQL server. Composite events are detected in the ECA Agent and actions are invoked in the SQL server. Events are persisted in the native database system. ECA Agent is designed to connect to SQL server by using Sybase connectivity products. The architecture, design, and implementation details are presented.

Languages for event specification in centralized systems and their semantics have received considerable attention in the literature. In contrast, very little work exists on extending the semantics of event specification languages to distributed environments. The paper provides a well-defined notion of distributed composite time stamps and their least restricted strict ordering are defined. The ordering is carefully chosen based on mathematical reasoning to ensure the best semantics. The concurrence and weaker-less-than-or-equal temporal relations are also introduced for the expressiveness of ECA rules. Furthermore, a Max operator is introduced for propagating the composite event time stamps. Based on this partial ordering and the Max operator on the time stamps, the semantics of Sentinel composite events is described for distributed event detection.

The utility and functionality of active capability (event-condition-action or ECA rules) has been well established in the context of databases. Today, most of the commercial relational database management systems (RDBMSs) offer some form of ECA rule capability. In addition, there are several research prototypes that have extended the ECA rule capability to object-oriented database management systems (OODBMSs). Sentinel, developed at the University of Florida is one such prototype that supports an expressive composite event specification language (Snoop), efficient event detection (using generated wrappers), conditions and actions (as a combination of OQL and C++), multiple and cascaded rule processing (using a rule scheduler and nested transactions), a visualization tool, and an editor for dynamic creation and management of rules. In order for the active capability to be useful for a large class of advanced applications, it is necessary to go beyond what has been proposed/developed in the literature. Specifically, the extensions needed beyond the current state-of-the-art active capability are: (i) support active capability for non-database applications as well, (ii) support active capability for distributed environments; that is, allow ECA across applications, and (iii) support active capability for heterogeneous sources of events (whether they are databases or not). The authors address how they are planning on addressing some of the above extensions using a combination of existing components (COTS) and new functionality/services that are culled from their experience in designing and implementing Sentinel.

IntroductionActive or reactive database management systems (DBMSS) provide an event-based rule capability that can be used to support a number of database functionality (e.g., integrity enforcement, view materialization, management of index structures, applicability of compiled query plane when access methods change) in a uniform way.Rules used for supporting active capability consists ofi au event expression, one or more conditions, an action, and a set of attributes.An event expression specifies the sequence of events whose occurrence triggers the evaluation of the condlt ion.A condition is a aide effect-free boolean computation (set computation in general) on the database state and an action is an arbitrary sequence of operations.Attributes, typically, specify rule characteristics such as coupling mode, event consumption mode, and precedence relationahlp among rules.A rule with these.components is termed an ECA or eventcondition-action rule in the literature [3].2 Paradigm Differences C1early,there is a paradigm shift when we move horn the relational model to an object-oriented one.The dflerences between the two data models profoundly influence how the concepts and techniques are carried over from one model to the other.Below, we enumerate some of the differences between the data models that led to the design choices made for Sentinel 1.In contrast to a fixed number of pm-defied primitive system events in the relational model (e.g., update, insert, delete), every method/mesaage is a potential event in an 00DBMS.These methods are defined in application classes, making detection potentially more dimcult.2. The principle of encapsulation and further the distinctions between features supported (e.g., private, pro-"This work was supported in par-t by the Office of Naval Technol-Ogy and the NaVY Command, Control and Ocean Surveillance Center RDT&E Division, and by the Rome Laboratory.Some of the earlier work was supported by the the NSF Grant (IR1-901 1216), Texas Instruments, Dallas, and Sofr6avia Services, France.

Coordination and collaboration are naturally used by groups for carrying out activities and solving problems that require cooperation. However, getting a set of computer agents to do the same has been a problem – primarily addressed by the AI community and recently by the database community as workflow and process management problems (for example, in business processes, electronic commerce, logistics). Not surprisingly, the problem has been addressed at different levels of abstraction by the two communities. Coordination protocols as well as task and result sharing have been investigated by the AI community; specification of alternative transaction models to meet the requirements of non-traditional applications, and their execution have been addressed by the database community. It is evident that there is a need for bringing the two approaches together to develop systems that support cooperative problem solving. This paper – argues for the use of active databases in general and active capability in particular as an enabling technology for cooperative problem solving and cooperative information systems – details a novel approach for supporting task sharing, a key aspect of CPS, using active capability – elaborates on a methodology for mapping task shared protocols expressed in high level speech acts to Event Condition-Action (ECA) rules.

Making a database system active entails not only the specification of expressive ECA (event-condition-action) rules, algorithms for the detection of composite events, and rule management, but also a viable architecture for rule execution that extends a passive DBMS, and its implementation. We propose an integrated active DBMS architecture for incorporating ECA rules using the Open OODB Toolkit (from Texas Instruments). We then describe the implementation of the composite event detector, and rule execution model for object-oriented active DBMS. Finally, the functionality supported by this architecture and its extensibility are analyzed along with the experiences gained.>

Over the past few years, the topic of active databases has become an important area of research. A number of efforts-both research prototypes and commercial database management systems (DBMSs)-have addressed support for event-condition-action (ECA) rules in databases. This paper examines the motivations for providing this capability, identifies features that form the basis for supporting active functionality, and provides a capsule summary of active database features of early commercial systems as well as research prototypes. Three broad categories-rule expressiveness, execution semantics and efficiency-are used for the capsule summary.

This paper proposes a new approach for supporting reactive capability in an objectoriented database. We introduce an event interface, which extends the conventional object semantics to include the role of an event generator. The proposed design of this interface enables objects to propagate events relevant to that class asynchronously. This interface provides a basis for the specification of events spanning sets of objects, possibly from different classes, and detection of primitive and complex events. This approach clearly separates event detection from rules. New rules can be added and use existing objects, enabling objects to react to their own changes as well as to the changes of other objects. We use a runtime subscription mechanism, between rules and objects to selectively monitor particular objects dynamically. This elegantly supports class level as well as instance level rules. Moreover, we propose a design for the specification and detection of simple as well as co...

Real-time databases are an important component of embedded real-time systems. In a real-time database context, transactions must not only maintain the consistency constraints of the database but must also satisfy the timing constraints specified for each transaction. Although several approaches have been proposed to integrate real-time scheduling and database concurrency control methods, none of them take into account the dynamic cost of scheduling a transaction. In this paper, we propose a new cost conscious real-time transaction scheduling algorithm which considers dynamic costs associated with a transaction. Our dynamic priority assignment algorithm adapts to changes in the system load without causing excessive numbers of transaction restarts. Our simulations show its superiority over EDF-HP algorithm.

Cooperative problem solving can be viewed as a complex activity requiring harmonious and dynamic interaction between active agents and passive agents. This problem is currently being addressed by the research community at various levels of abstraction. Broadly, this paper analyzes the problem of cooperative problem solving from a database perspective and argues that recent advances in database technology facilitate development of a viable solution to the above problem. Specifically, in this paper, we first analyze the problem of cooperative problem solving to identify its underlying key characteristics. Based upon our analysis, we partition the problem space into classes along a spectrum and indicate the level of cooperation required. We propose near-term as well as long-term solutions for cooperative problem solving that progressively enhances the functionality of database systems by synthesizing appropriate abstractions and techniques. Furthermore, we identify problems, such as agent capability modeling that require further research to address the most general form of cooperative problem solving.

An approach for adding a new component without radically changing an existing single-query optimizer (SQO) is proposed. A new way of organizing the strategy space of a set of queries being optimized is proposed for developing a multiple-query optimizer (MQO) architecture. The architecture relies on the generation of two strategy spaces using subsumption and equivalence of subexpressions at the logical level. Heuristics for pruning the space of multistrategies are also presented. It is shown that the partitioned organisation of the strategy space not only reduces the size of the strategy space but also lends itself to division of labor, thereby leading to a simpler MQO design. Clear separation of the module specific to multistrategy generation provides an easy migration path from SQOs to MQOs. In the decomposition algorithm, selections are propagated down the operator tree (counterintuitively) enabling the detection and creation of larger common subexpressions.>