Automated fact-checking aims to verify the veracity of claims based on related evidence, and has become increasingly important as large language models (LLMs) make it easier to generate and disseminate misinformation at scale. In open settings, effective fact-checking requires models to iteratively retrieve relevant evidence and reason over noisy and incomplete information. While recent LLM-based approaches have shown promising reasoning capabilities, prompt-based methods remain limited by the inherent behaviors of base LLMs, and supervised fine-tuning methods typically require costly annotated reasoning trajectories. In this paper, we propose R3Check, a rule-guided reinforcement learning framework that enables LLMs to perform iterative retrieval–reasoning for multi-hop fact-checking. R3Check formulates the retriever as an external environment and optimizes the model using Group Relative Policy Optimization, relying only on final veracity labels and format-based rewards rather than explicit reasoning annotations. To mitigate the mutual interference between retrieval and reasoning that arises under joint training, we introduce a two-stage curriculum that first trains structured reasoning under closed fact-checking with gold evidence, and then jointly optimizes retrieval and reasoning with real-time retrieval. An importance-based sampling strategy further strengthens effective supervision signals during training. Despite using only a 7B backbone, R3Check outperforms existing baselines and even powerful reasoning LLMs, under both given-evidence and real-time retrieval settings, while producing interpretable reasoning chains. This work demonstrates the potential of pure reinforcement learning to induce effective retrieval–reasoning behaviors for fact-checking under weak supervision.

Predicting disease progression is key to provide stratified patient care and enable good utilization of healthcare resources. The availability of longitudinal images has enabled image-based disease progression prediction. In this work, we propose a framework called DP-GAT to identify regions containing significant biological structures and model the relationships among these regions as a graph along with their respective contexts. We perform reasoning via Graph Attention Network to generate representations that enable accurate disease progression prediction. We further extend DP-GAT to perform 3D medical volume segmentation. Experiments on real world medical image datasets demonstrate the advantage of our approach over strong baseline methods for both disease progression prediction and 3D segmentation tasks.

The broad adoption of electronic health records (EHRs) has led to vast amounts of data being accumulated on a patient’s history, diagnosis, prescriptions, and lab tests. Advances in recommender technologies have the potential to utilize this information to help doctors personalize the prescribed medications. However, existing medication recommendation systems have yet to make use of all these information sources in a seamless manner, and they do not provide a justification on why a particular medication is recommended. In this work, we design a two-stage personalized medication recommender system called PREMIER that incorporates information from the EHR. We utilize the various weights in the system to compute the contributions from the information sources for the recommended medications. Our system models the drug interaction from an external drug database and the drug co-occurrence from the EHR as graphs. Experiment results on MIMIC-III and a proprietary outpatient dataset show that PREMIER outperforms state-of-the-art medication recommendation systems while achieving the best tradeoff between accuracy and drug-drug interaction. Case studies demonstrate that the justifications provided by PREMIER are appropriate and aligned to clinical practices.

Posts by users on microblogs such as Twitter provide diverse real-time updates to major events. Unfortunately, not all the information are credible. Previous works that assess the credibility of information in Twitter have focused on extracting features from the Tweets. In this work, we present an interactive framework called iFACT for assessing the credibility of claims from tweets. The proposed framework collects independent evidence from web search results (WSR) and identify the dependencies between claims. It utilizes features from the search results to determine the probabilities that a claim is credible, not credible or inconclusive. Finally, the dependencies between claims are used to adjust the likelihood estimates of a claim being credible, not credible or inconclusive. iFACT allows users to be engaged in the credibility assessment process by providing feedback as to whether the web search results are relevant, support or contradict a claim. Experiment results on multiple real world datasets demonstrate the effectiveness of WSR features and its ability to generalize to claims of new events. Case studies show the usefulness of claim dependencies and how the proposed approach can give explanation to the credibility assessment process.

In this demonstration, we showcase MAROON+, a system that builds historical profiles of real-world target entities by integrating their publicly available information from different Web sites. We face two challenges when building such a system. First, an entity may change its attribute values over time and it is thus hard to decide if distinct values actually describe the same entity but at different times. Second, the Web sites may provide inaccurate information or fail to update their contents in a timely manner. MAROON+ employs a source-aware matching algorithm that jointly considers the evolution of entities and the source quality to link temporal records to a target entity. We characterize a source by its precision which measures the probability that a published value conforms to the real world, recall which measures the probability that a change in real world is captured by a source, and freshness which measures the timeliness of a published value.

The diffusion of rumors is a major concern for web users. Limiting the spread of rumor on social networks has become an important task. One approach is to identify nodes to start a truth campaign such that when users are aware of the truth, they would not believe or propagate the rumor. However, existing works do not take into account the delays of information diffusion or the time point beyond which propagation of misinformation is no longer critical. In this paper, we consider a more realistic situation where information is propagated with delays and the goal is to reduce the number of rumor-infected users before a deadline. We call this the Temporal Influence Blocking (TIB) problem. We propose a two-phase solution called TIB-Solver to select k nodes to start a truth campaign such that the number of users reached by a rumor is minimized. Experiments show that the proposed TIBSolver outperforms the state-of-the-art algorithms in terms of both effectiveness and efficiency.

Paul Johannesson; Mong Li Lee; Liddle, S.; Opdahl, A.; Pastor López, O. (2017). Special issue on conceptual modeling - 34th International Conference on Conceptual Modeling (ER 2015). Data & Knowledge Engineering. 109:1-2. doi:10.1016/j.datak.2017.03.001

To harness the rich amount of information available on the web today, many organizations aggregate public (and private) data to derive knowledge repositories for real-world entities. This paper aims to build historical profiles of real-world entities by integrating temporal records collected from different sources. This problem is challenging not only because entities may change their attribute values over time, but also because information provided by the sources could be unreliable. In this paper, we present a new solution for profiling entities over time. To understand the evolution of entities, we describe a novel transition model which gives the probability that an entity will change to a particular attribute value after some time period. Next, a set of quality metrics are defined for the data sources to capture the exactness and timeliness of their provided values. The transition model and the quality metrics are then built into a source-aware temporal matching algorithm that can link temporal records to entities at the right time and augment entity profiles with correct values. Our suite of experiments demonstrate that the proposed approach is able to outperform the state-of-the-art techniques by constructing more complete and accurate profiles for entities.

Influence maximization (IM) problem asks for a set of k nodes in a given graph G, such that it can reach the largest expected number of remaining nodes in G. Existing methods have either considered that the influence be targeted to meet certain deadline constraint, or be restricted to specific geographical region. However, if an event organizer wants to disseminate some event information on a social platform, s/he would want to select a set of users who can influence the most number of people within the neighborhood of the event location, and this influence should occur before the event takes place. Considering the location and deadline independently may lead to a less than optimal set of users. In this paper, we formalize the problem targeted influence maximization in social networks. We adopt a login model where each user is associated with a login probability and he can be influenced by his neighbors only when he is online. We develop a sampling based algorithm that returns a (1-1/e-ε)-approximate solution, as well as an efficient heuristic algorithm that focuses on nodes close to the target location. Experiments on real-world social network datasets demonstrate the effectiveness and efficiency of our proposed method.

Keyword search over relational databases has gained popularity as it provides a user-friendly way to explore structured data. Current research in keyword search has largely ignored queries to retrieve statistical information from the database. The work in [13] extends keywords by supporting aggregate functions in their SQAK system. However, SQAK does not consider the semantics of objects and relationships in the database, and thus suffers from the problems of returning incorrect answers. In this work, we propose a semantic approach to answer keyword queries involving aggregates and GROUPBY. Our approach utilizes the ORM schema graph to capture the Object-Relationship-Attribute (ORA) semantics in the database, and determines the various interpretations of a query before generating the corresponding SQL statements. These semantics enable us to distinguish objects with the same attribute value and detect duplications of objects in relationships to compute the answers correctly. Our approach can also handle unnormalized relations in the database and GROUPBY in keyword queries which SQAK cannot. Experiments on the TPC-H and ACM Digital Library publication datasets demonstrate the advantages of the proposed semantic approach in retrieving correct statistical information for users.

Keyword search over relational databases has gained popularity due to its ease of use. Current research has focused on the efficient computation of results from multiple tuples, and largely ignores queries to retrieve statistical information from databases. The work in [5] developed a system that allows aggregate functions to be expressed using simple keywords. However, this system may return incorrect answers because it does not consider the semantics of objects and relationships in the database. In this paper, we present an interactive keyword search engine called PowerQ to answer queries involving aggregate functions and GROUPBY. PowerQ utilizes an ORM schema graph to capture the Object-Relationship-Attribute (ORA) semantics in the database. Given a keyword query, PowerQ identifies the various interpretations of the query and applies aggregate functions and GROUPBY on the appropriate attributes of objects/relationships. Each query interpretation is denoted as an annotated query pattern, whose meaning can be described in natural language to facilitate user understanding. Through user interactions, PowerQ can determine the user’s search intention, and translate the corresponding patterns into SQLs to compute the answers correctly. The PowerQ prototype is available at http://powerq.comp.nus.edu.sg.

The theory of brokerage in sociology suggests if contacts between two parties are enabled through a third party, the latter occupies a strategic position of controlling information flows. Such individuals are called brokers and they play a key role in disseminating information. However, there is no systematic approach to identify brokers in online social networks. In this paper, we formally define the problem of detecting top-$k$ brokers given a social network and show that it is NP-hard. We develop a heuristic algorithm to find these brokers based on the weak tie theory. In order to handle the dynamic nature of online social networks, we design incremental algorithms: WeakTie-Local for unidirectional networks and WeakTie-Bi for bidirectional networks. We use two real world datasets, DBLP and Twitter, to evaluate the proposed methods. We also demonstrate how the detected brokers are useful in diffusing information across communities and propagating tweets to reach more distinct users.

Locating nodes to immunize in computer/social networks to control the spread of virus or rumors has become an important problem. In real world contagions, nodes may get infected by external sources when the propagation is underway. While most studies formalize the problem in a setting where contagion starts at one time point, we model a more realistic situation where there are likely to be many breakouts of contagions over a time window. We call this the node immunization over infectious period (NIIP) problem. We show that the NIIP problem is NP-hard and remains so even in directed acyclic graphs. We propose a NIIP algorithm to select $k$ nodes to immunize over a time period. Simulation is performed to estimate a good distribution of $k$ over the time period. For each time point, the NIIP algorithm will make decisions which nodes to immunize given the estimated value of $k$ for that time point. Experiments show that the proposed NIIP algorithm outperform the state-of-the-art algorithms in terms of both effectiveness and efficiency.

To harness the rich amount of information available on the Web today, many organizations start to aggregate public (and private) data to derive new knowledge bases. A fundamental challenge in constructing an accurate integrated knowledge repository from different data sources is to understand how facts across different sources are related to one another over time. This challenge, referred to as the temporal record linkage problem, goes far beyond the traditional record linkage problem as it requires a fine-grained analysis of how two facts are temporally related if they both refer to the same entity.

Keyword search in relational databases has gained popularity due to its ease of use. However, the challenge to return query answers that satisfy users' information need remains. Traditional keyword queries have limited expressive capability and are ambiguous. In this work, we extend keyword queries to enhance their expressive power and describe an semantic approach to process these queries. Our approach considers keywords that match meta-data such as the names of relations and attributes, and utilizes them to provide the context of subsequent keywords in the query. Based on the ORM schema graph which captures the semantics of objects and relationships in the database, we determine the objects and relationships referred to by the keywords in order to infer the search target of the query. Then, we construct a set of minimal connected graphs called query patterns, to represent user's possible search intentions. Finally, we translate the top-k ranked query patterns into SQL statements in order to retrieve information that the user is interested in. We develop a system prototype called ExpressQ to process the extended keyword queries. Experimental results show that our system is able to generate SQL statements that retrieve user intended information effectively.

The rapid growth of information sources on the Web has intensified the problem of data quality. In particular, the same real world entity may be described by different sources in various ways with overlapping information, and possibly conflicting or even erroneous values. In order to obtain a more complete and accurate picture for a real world entity, we need to collate the data records that refer to the entity, as well as correct any erroneous values. We observe that these two tasks are often tightly coupled: rectifying erroneous values will facilitate data collation, while linking similar records provides us with a clearer view of the data and additional evidence for error correction. In this paper, we present a framework called Comet that interleaves record linkage with error correction, taking into consideration the source reliabilities on various attributes. The proposed framework first utilizes confidence based matching to discriminate records in terms of ambiguity and source reliability. Then it performs adaptive matching to reduce the impact of erroneous values. Experiment results demonstrate that Comet outperforms the state-of-the-art techniques and is able to build complete and accurate profiles for real world entities.

Advances in Web 2.0 technology has led to the rising popularity of many social network services. For example, there are over 500 million active users in Twitter. Given the huge number of users, user recommendation has gained importance where the goal is to find a set of users whom a target user is likely to follow. Content-based approaches that rely on tweet content for user recommendation have low precision as tweet contents are typically short and noisy, while collaborative filtering approaches that utilize follower-followee relationships lead to higher precision but data sparsity remains a challenge. In this work, we propose a community-based approach to user recommendation in Twitter-style social networks. Forming communities enables us to reduce data sparsity as the focus is on discover the latent characteristics of communities instead of individuals. We employ an LDA-based method on the follower-followee relationships to discover communities before applying the state-of-the-art matrix factorization method on each of the communities. This approach proves effective in improving the conversion rate (by as much as 20%) as demonstrated by the results of extensive experiments on two real world data sets Twitter and Weibo. In addition, the community-based approach is scalable as the individual community can be analyzed separately.

Existing recommendation algorithms assume that users make their purchase decisions solely based on individual preferences, without regard to the type of users nor the products' maturity stages. Yet, extensive studies have shown that there are two types of users: innovators and imitators. Innovators tend to make purchase decisions based solely on their own preferences; whereas imitators' purchase decisions are often influenced by a product's stage of maturity. In this paper, we propose a framework that seamlessly incorporates the type of user and product maturity into existing recommendation algorithms. We apply Bass model to classify each user as either an innovator or imitator according to his/her previous purchase behavior. In addition, we introduce the concept of tipping point of a user. This tipping point refers to the point on the product maturity curve beyond which the user is likely to be more receptive to purchasing the product. We refine two widely-adopted recommendation algorithms to incorporate the effect of product maturity in relation to the user type. Experiment results on a real-world dataset obtained from an E-commerce website show that the proposed approach outperforms existing algorithms.

Given the vast amount of information on the World Wide Web, recommender systems are increasingly being used to help filter irrelevant data and suggest information that would interest users. Traditional systems make recommendations based on a single domain e.g., movie or book domain. Recent work has examined the correlations in different domains and designed models that exploit user preferences on a source domain to predict user preferences on a target domain. However, these methods are based on matrix factorization and can only be applied to two-dimensional data. Transferring high dimensional data from one domain to another requires decomposing the high dimensional data to binary relations which results in information loss.

Existing recommender systems model user interests and the social influences independently. In reality, user interests may change over time, and as the interests change, new friends may be added while old friends grow apart and the new friendships formed may cause further interests change. This complex interaction requires the joint modeling of user interest and social relationships over time. In this paper, we propose a probabilistic generative model, called Receptiveness over Time Model (RTM), to capture this interaction. We design a Gibbs sampling algorithm to learn the receptiveness and interest distributions among users over time. The results of experiments on a real world dataset demonstrate that RTM-based recommendation outperforms the state-of-the-art recommendation methods. Case studies also show that RTM is able to discover the user interest shift and receptiveness change over time

Personalized recommender systems aim to push only the relevant items and information directly to the users without requiring them to browse through millions of web resources. The challenge of these systems is to achieve a high user acceptance rate on their recommendations. In this paper, we aim to increase the user acceptance of recommendations by providing more intuitive tag-based explanations of why the items are recommended. Tags are used as intermediary entities that not only relate target users to the recommended items but also understand users' intents. Our system also allows tag-based online relevance feedback. Experiment results on the Movielens dataset show that the proposed approach is able to increase the acceptance rate of recommendations and improve user satisfaction.

Many frequent pattern mining algorithms have been developed for categorical, numerical, time series, or interval data. However, little attention has been given to integrate these algorithms so as to mine frequent patterns from multiple domain datasets for classification. In this paper, we introduce the notion of a heterogenous pattern to capture the associations among different kinds of data. We propose a unified framework for mining multiple domain datasets and design an iterative algorithm called HTMiner. HTMiner discovers essential heterogenous patterns for classification and performs instance elimination. This instance elimination step reduces the problem size progressively by removing training instances which are correctly covered by the discovered essential heterogenous pattern. Experiments on two real world datasets show that the HTMiner is efficient and can significantly improve the classification accuracy.

Trajectory classification has many useful applications. Existing works on trajectory classification do not consider the duration information of trajectory. In this paper, we extract duration-aware features from trajectories to build a classifier. Our method utilizes information theory to obtain regions where the trajectories have similar speeds and directions. Further, trajectories are summarized into a network based on the MDL principle that takes into account the duration difference among trajectories of different classes. A graph traversal is performed on this trajectory network to obtain the top-k covering path rules for each trajectory. Based on the discovered regions and top-k path rules, we build a classifier to predict the class labels of new trajectories. Experiment results on real-world datasets show that the proposed duration-aware classifier can obtain higher classification accuracy than the state-of-the-art trajectory classifier.

The development of Web 2.0 technology has led to huge economic benefits and challenges for both e-commerce websites and online shoppers. One core technology to increase sales and consumers' satisfaction is the use of recommender systems. Existing product recommender systems consider the order of items purchased by users to obtain a list of recommended items. However, they do not consider the time interval between the products purchased. For example, there is often an interval of 2-3 months between the purchase of printer ink cartridges or refills. Thus, recommending appropriate ink cartridges one week before the user needs to replace the depleted ink cartridges would increase the likelihood of a purchase decision. In this paper, we propose to utilize the purchase interval information to improve the performance of the recommender systems for e-commerce. We design an efficient algorithm to compute the purchase intervals between product pairs from users' purchase history and integrate this information into the marginal utility model. We evaluate our approach on a real world ecommerce dataset. Experimental results demonstrate that our approach significantly improves the conversion rate and temporal diversity compared to state-of-the-art algorithms.

The MaxBRNN problem finds a region such that setting up a new service site within this region would guarantee the maximum number of customers by proximity. This problem assumes that each customer only uses the service provided by his/her nearest service site. However, in reality, a customer tends to go to his/her k nearest service sites. To handle this, MaxBRNN can be extended to the MaxBRkNN problem which finds an optimal region such that setting up a service site in this region guarantees the maximum number of customers who would consider the site as one of their k nearest service locations. We further generalize the MaxBRkNN problem to reflect the real world scenario where customers may have different preferences for different service sites, and at the same time, service sites may have preferred targeted customers. In this paper, we present an efficient solution called MaxFirst to solve this generalized MaxBRkNN problem. The algorithm works by partitioning the space into quadrants and searches only in those quadrants that potentially contain an optimal region. During the space partitioning, we compute the upper and lower bounds of the size of a quadrant's BRkNN, and use these bounds to prune the unpromising quadrants. Experiment results show that MaxFirst can be two to three orders of magnitude faster than the state-of-the-art algorithm.

Social network systems such as FaceBook and YouTube have played a significant role in capturing both explicit and implicit user preferences for different items in the form of ratings and tags. This forms a quaternary relationship among users, items, tags and ratings. Existing systems have utilized only ternary relationships such as users-items-ratings, or users-items-tags to derive their recommendations. In this paper, we show that ternary relationships are insufficient to provide accurate recommendations. Instead, we model the quaternary relationship among users, items, tags and ratings as a 4-order tensor and cast the recommendation problem as a multi-way latent semantic analysis problem. A unified framework for user recommendation, item recommendation, tag recommendation and item rating prediction is proposed. The results of extensive experiments performed on a real world dataset demonstrate that our unified framework outperforms the state-of-the-art techniques in all the four recommendation tasks.

The increasing infectious disease outbreaks has led to a need for new research to better understand the disease's origins, epidemiological features and pathogenicity caused by fast-mutating, fast-spreading viruses. Traditional sequence analysis methods do not take into account the spatio-temporal dynamics of rapidly evolving and spreading viral species. They are also focused on identifying single-point mutations. In this paper, we propose a novel approach that incorporates space-time relationships for studying changes in protein sequences from fast mutating viruses. We aim to detect both single-point mutations as well as k-mutations in the viral sequences. We define the problem of mutation chain pattern mining and design algorithms to discover valid mutation chains. Compact data structures to facilitate the mining process as well as pruning strategies to increase the scalability of the algorithms are devised. Experiments on both synthetic datasets and real world influenza A virus dataset show that our algorithms are scalable and effective in discovering mutations that occur geographically over time.

Users often do not require a complete answer to their query but rather only a sample. They expect the sample to be either the largest possible or the most representative (or both) given the resources available. We call the query processing techniques that deliver such results 'approximate'. Processing of queries to streams of data is said to be 'progressive' when it can continuously produce results as data arrives. In this paper, we are interested in the progressive and approximate processing of queries to data streams when processing is limited to main memory. In particular, we study one of the main building blocks of such processing: the progressive approximate join. We devise and present several novel progressive approximate join algorithms. We empirically evaluate the performance of our algorithms and compare them with algorithms based on existing techniques. In particular we study the trade-off between maximization of throughput and maximization of representativeness of the sample.

Compared to relational data models, the hierarchical structure of semi-structured data such as XML provides semantically meaningful neighbourhoods advancing data cleaning problems such as outlier detection. In this paper, we introduce the concept of correlated subspace that leverages on the hierarchical relationships between XML attributes to provide contextually informative neighbourhoods for attribute outlier detection. We also design two correlation-based attribute outlier metrics for XML, namely the xO-Measure and xQ-Measure. The effectiveness of our XML outlier detection approach is supported with experimental results.

Existing temporal pattern mining assumes that events do not have any duration. However, events in many real world applications have durations, and the relationships among these events are often complex. These relationships are modeled using a hierarchical representation that extends Allen's interval algebra. However, this representation is lossy as the exact relationships among the events cannot be fully recovered. In this paper, we augment the hierarchical representation with additional information to achieve a lossless representation. An efficient algorithm called IEMiner is designed to discover frequent temporal patterns from interval-based events. The algorithm employs two optimization techniques to reduce the search space and remove non-promising candidates. From the discovered temporal patterns, we build an interval-based classifier called IEClassifier to differentiate closely related classes. Experiments on both synthetic and real world datasets indicate the efficiency and scalability of the proposed approach, as well as the improved accuracy of IEClassifier.

Biological networks such as the protein-protein interaction (PPI) network have been found to contain small recurring subnetworks in significantly higher frequencies than in random networks. Such network motifs are useful for uncovering structural design principles of complex biological networks. However, current network motif finding algorithms models the PPI network as a uni-labeled graph, discovering only unlabeled and thus relatively uninforma-tive network motifs as a result. Our objective is to exploit the currently available biological information that are associated with the vertices (the proteins) to capture not only the topological shapes of the motifs, but also the biological context in which they occurred in the PPI networks for network motif applications. We present a method called LaMoFinder to label network motifs with gene ontology terms in a PPI network. We also show how the resulting labeled network motifs can be used to predict unknown protein functions. Experimental results showed that the labeled network motifs extracted are biologically meaningful and can achieve better performance than existing PPI topology based methods for predicting unknown protein functions.

Estimating the result sizes of XML queries is important in query optimization and is useful in providing a quick feedback about the queries. Existing works have focused on the selectivity estimation of XML queries without order-based axes. In this work, we develop a framework to estimate the result sizes of XPath expressions with order-based axes. We describe how the path and order information of XML elements can be captured and summarized in compact data structures. We also describe methods to estimate the selectivity of XPath queries. The results of extensive experiments on both synthetic and real-world datasets demonstrate the effectiveness and accuracy of the proposed approach.

Existing techniques to mine periodic patterns in time series data are focused on discovering full-cycle periodic patterns from an entire time series. However, many useful partial periodic patterns are hidden in long and complex time series data. In this paper, we aim to discover the partial periodicity in local segments of the time series data. We introduce the notion of character density to partition the time series into variable-length fragments and to determine the lower bound of each character’s period. We propose a novel algorithm, called DPMiner, to find the dense periodic patterns in time series data. Experimental results on both synthetic and real-life datasets demonstrate that the proposed algorithm is effective and efficient to reveal interesting dense periodic patterns.

Existing graph mining algorithms typically assume that databases are relatively static and can fit into the main memory. Mining of subgraphs in a dynamic environment is currently beyond the scope of these algorithms. To bridge this gap, we first introduce a partition-based approach called PartMiner for mining graphs. The PartMiner algorithm finds the frequent subgraphs by dividing the database into smaller and more manageable units, mining frequent subgraphs on these smaller units and finally combining the results of these units to losslessly recover the complete set of subgraphs in the database. Next, we extend PartMiner to handle updates in the dynamic environment. Experimental results indicate that PartMiner is effective and scalable in finding frequent subgraphs, and outperforms existing algorithms in the presence of updates.

Recent works in network analysis have revealed the existence of network motifs in biological networks such as the protein-protein interaction (PPI) networks. However, existing motif mining algorithms are not sufficiently scalable to find meso-scale network motifs. Also, there has been little or no work to systematically exploit the extracted network motifs for dissecting the vast interactomes.We describe an efficient network motif discovery algorithm, NeMoFinder, that can mine meso-scale network motifs that are repeated and unique in large PPI networks. Using NeMoFinder, we successfully discovered, for the first time, up to size-12 network motifs in a large whole-genome S. cerevisiae (Yeast) PPI network. We also show that such network motifs can be systematically exploited for indexing the reliability of PPI data that were generated via highly erroneous high-throughput experimental methods.

Many real world objects have states that change over time. By tracking the state sequences of these objects, we can study their behavior and take preventive measures before they reach some undesirable states. In this paper, we propose a new kind of pattern called progressive confident rules to describe sequences of states with an increasing confidence that lead to a particular end state. We give a formal definition of progressive confident rules and their concise set. We devise pruning strategies to reduce the enormous search space. Experiment result shows that the proposed algorithm is efficient and scalable. We also demonstrate the application of progressive confident rules in classification.

In spatial data exploration and analysis, the system would present a user with initial promising results and empower the user to modify runtime query parameters. The high degree of interactivity would significantly reduce users’ waiting time for results that are not useful, and then having to re-issue a new query. To support this level of interaction during query processing, it necessitates the study of adaptive and progressive spatial query processing techniques that can deliver initial results quickly and adapt to run-time fluctuations during the delivery of remote data. Our goal is to design a generic framework for adaptive and progressive spatial query processing. In this paper, we present our ongoing work on designing progressive spatial join algorithm as an initial step.

This work addresses the problem of finding boundary points in multidimensional data sets. Boundary points are data points that are located at the margin of densely distributed data such as a cluster. We describe a novel approach called BORDER (a BOundaRy points DEtectoR) to detect such points. BORDER employs the state-of-the-art database technique - the Gorder kNN join and makes use of the special property of the reverse k nearest neighbor (RkNN). Experimental studies on data sets with varying characteristics indicate that BORDER is able to detect the boundary points effectively and efficiently.

Mining topological patterns in spatial databases has received a lot of attention. However, existing work typically ignores the temporal aspect and suffers from certain efficiency problems. They are not scalable for mining topological patterns in spatio-temporal databases. In this paper, we study the problem for mining topological patterns by incorporating the temporal aspect in the mining process. We introduce a summary-structure that records the instances' count information of a feature in a region within a time window. Using this structure, we design an algorithm, TopologyMiner, to find interesting topological patterns without the need to generate candidates. Experimental results show that TopologyMiner is effective and scalable in finding topological patterns and outperforms Apriori-like algorithm by a few orders of magnitudes.

The Reverse k-Nearest Neighbors (RkNN) queries are important in profile-based marketing, information retrieval, decision support and data mining systems. However, they are very expensive and existing algorithms are not scalable to queries in high dimensional spaces or of large values of k. This paper describes an efficient estimation-based RkNN search algorithm (ERkNN) which answers RkNN queries based on local kNN-distance estimation methods. The proposed approach utilizes estimation-based filtering strategy to lower the computation cost of RkNN queries. The results of extensive experiments on both synthetic and real life datasets demonstrate that ERkNN algorithm retrieves RkNN efficiently and is scalable with respect to data dimensionality, k, and data size.

Efficient evaluation of XML queries requires the determination of whether a relationship exists between two elements. A number of labeling schemes have been designed to label the element nodes such that the relationships between nodes can be easily determined by comparing their labels. With the increased popularity of XML on the Web, finding a labeling scheme that is able to support order-sensitive queries in the presence of dynamic updates becomes urgent. We propose a new labeling scheme that take advantage of the unique property of prime numbers to meet this need. The global order of the nodes can be captured by generating simultaneous congruence values from the prime number node labels. Theoretical analysis of the label size requirements for the various labeling schemes is given. Experiment results indicate that the prime number labeling scheme is compact compared to existing dynamic labeling schemes, and provides efficient support to order-sensitive queries and updates.

Caching the results of frequent query patterns can improve the performance of query evaluation. This paper describes a 2-pass mining algorithm called 2PXMiner to discover frequent XML query patterns. We design 3 data structures to expedite the mining process. Experiments results indicate that 2PXMiner is both efficient and scalable.

As XML prevails over the Internet, the efficient retrieval of XML data becomes important. Research to improve query response times has been largely concentrate on indexing XML documents and processing regular path expressions. Another approach is to discover frequent query patterns since the answers to these queries can be stored and indexed. Mining frequent query patterns requires more than simple tree matching since the XML queries involves special characters such as "*" or "//". In addition, the matching process can be expensive since the search space is exponential to the size of XML schema. In this paper, we present two mining algorithms, XQPMiner and XQPMinerTID, to discover frequent query pattern frees from a large collection of XML queries efficiently. Both algorithms exploit schema information to guide the enumeration of candidate subtrees, thus eliminating unnecessary node expansions. Experiments results show that the proposed methods are efficient and have good scalability.

The increasing number of image repositories has made image mining an important task because of its potential in discovering useful image patterns from a large set of images. In this paper, we introduce the notion of viewpoint patterns for image databases. Viewpoint patterns refer to patterns that capture the invariant relationships of one object from the point of view of another object. These patterns are unique and significant in images because the absolute positional information of objects for most images is not important, but rather, it is the relative distance and orientation of the objects from each other that is meaningful. We design a scalable and efficient algorithm to discover such viewpoint patterns. Experiments results on various image sets demonstrate that viewpoint patterns are meaningful and interesting to human users.

Traditionally, XML documents are processed at where they are stored. This allows the query processor to exploit pre-computed data structures (e.g., index) to retrieve the desired data efficiently. However, this mode of processing is not suitable for many applications where the documents are frequently updated. In such situations, efficient evaluation of multiple queries over streaming XML documents becomes important. This paper introduces a new operator, mqX-scan, which efficiently evaluates multiple queries with a single pass on streaming XML data. To facilitate matching, mqX-scan utilizes templates containing paths that have been traversed to match regular path expression patterns in a pool of queries. Results of the experiments demonstrate the efficiency and scalability of the mqX-scan operator.

It is increasingly important to develop scalable integration techniques for the growing number of XML data sources. A practical starting point for the integration of large numbers of Document Type Definitions (DTDs) of XML sources would be to first find clusters of DTDs that are similar in structure and semantics. Reconciling similar DTDs within such a cluster will be an easier task than reconciling DTDs that are different in structure and semantics as the latter would involve more restructuring. We introduce XClust, a novel integration strategy that involves the clustering of DTDs. A matching algorithm based on the semantics, immediate descendents and leaf-context similarity of DTD elements is developed. Our experiments to integrate real world DTDs demonstrate the effectiveness of the XClust approach.

With the increasing popularity of data-centric XML, data warehousing and mining applications are being developed for rapidly burgeoning XML data repositories. Data quality will no doubt be a critical factor for the success of such applications. Data cleaning, which refers to the processes used to improve data quality, has been well researched in the context of traditional databases. In earlier work we developed a knowledge-based framework for data cleaning relational databases. In this work, we present a novel attempt to apply this framework to XML databases. Our experimental dataset is the DBLP database, a popular online XML bibliography database used by many researchers.

Advances in imaging techniques have led to large repositories of images. There is an increasing demand for automated systems that can analyze complex medical images and extract meaningful information for mining patterns. Here, we describe a real-life image mining application to the problem of tumour cell counting. The quantitative analysis of tumour cells is fundamental to characterizing the activity of tumour cells. Existing approaches are mostly manual, time-consuming and subjective. Efforts to automate the process of cell counting have largely focused on using image processing techniques only. Our studies indicate that image processing alone is unable to give accurate results. In this paper, we examine the use of extracted features rules to aid in the process of tumor cell counting. We propose a robust local adaptive thresholding and dynamic water immersion algorithms to segment regions of interesting from background. Meaningful features are then extracted from the segmented regions. A number of base classifiers are built to generate features rules to help identify the tumor cell. Two voting strategies are implemented to combine the base classifiers into a meta-classifier. Experiment results indicate that this process of using extracted features rules to help identify tumor cell leads to better accuracy than pure image processing techniques alone.

If XML is to play the critical role of the lingua franca for Internet data interchange that many predict, it is necessary to start designing and adopting benchmarks allowing the comparative performance analysis of the tools being developed and proposed. The effectiveness of existing XML query languages has been studied by many, with a focus on the comparison of linguistic features, implicitly reflecting the fact that most XML tools exist only on paper. In this paper, with a focus on efficiency and concreteness, we propose a pragmatic first step toward the systematic benchmarking of XML query processing platforms with an initial focus on the data (versus document) point of view. We propose XOO7, an XML version of the OO7 benchmark. We discuss the applicability of XOO7, its strengths, limitations and the extensions we are considering. We illustrate its use by presenting and discussing the performance comparison against XOO7 of three different query processing platforms for XML.

XML is increasingly being adopted for information publishing on the World Wide Web. However, the underlying data is often stored in the relational databases. Some mechanism is needed to convert the relational data into XML data. In this work we employ a semantically rich semistructured data model, the object-relationship-attribute model for semistructured data, as a middleware to support the schema conversion from semantically enriched relational schema to XML schema. This approach allows us to handle the translation of a set of related relations and to distinguish attributes of relationship types from attributes of object classes, multivalued attributes, and different types of relationships such as binary, n-ary, recursive and ISA. The resulting XML structures are able to reflect the inherent semantics and implicit structure in the underlying relational database. We also show that the appropriate use of references is able to avoid unnecessary redundancy and the proliferation of disconnected XML elements.

Semistructured data has become prevalent with the growth of the Internet. The development of new web applications that require efficient design and maintenance of large amounts of data makes it increasingly important to design "good" semistructured databases to prevent data redundancy and updating anomalies. However, it is not easy, even impossible, for current semistructured data models to capture the semantics traditionally needed for designing databases. In this paper, we show how an object-relationship-attribute model for semistructured data (ORA-SS) can facilitate the design of "good" semistructured databases. This is accomplished via the normalization of ORA-SS. An XML DTD or Schema generated from a normal form ORA-SS schema diagram has no undesirable redundancy, and thus no updating anomalies for the complying semistructured databases. The general design methodology and detailed steps for converting an ORA-SS schema diagram into a normal form ORA-SS schema diagram are presented. These steps can also be used as guidelines for designing semistructured databases using the ORA-SS model.

Real-life data mining applications are interesting because they often present a different set of problems for data miners.One such real-life application that we have done is on the diabetic patients databases.Valuable lessons are learnt from this application.In particular, we discover that the often neglected pre-processing and post-processing steps in knowledge discovery are the most critical elements in determining the success of a real-life data mining application.In this paper, we shall discuss how we carry out knowledge discovery on this diabetic patient database, the interesting issues that have surfaced, as well as the lessons we have learnt from this application.We will describe a semi-automatic means for cleaning the diabetic patient database, and present a step-by-step approach to help the health doctors explore their data and to understand the discovered rules better.While it is important to generate understandable rules, it is also important to the medical doctors to have a complete picture of all

Existing data cleaning methods work on the basis of computing the degree of similarity be t ween nearby records in a sorted database.High recall is achieved by accepting records with low degrees of similarity as duplicates, at the cost of lower precision.High precision is achieved analogously at the cost of lower recall.This is the r e c all-pr ecision dilemma.In this paper, we propose a generic knowledge-based framework for eective data cleaning that implements existing cleaning strategies and more.We develop a new method to compute transitive closure under uncertaint ywhich handles the merging of groups of inexact duplicate records.Experimental results show that this framework can identify duplicates and anomalies with high recall and precision.

There is an increasing demand for systems that can automatically analyze images and extract semantically meaningful information. IRIS, an Integrated Retinal Information system, has been developed to provide medical professionals easy and unified access to the screening, trend and progression of diabetic-related eye diseases in a diabetic patient database. This paper shows how mining techniques can be used to accurately extract features in the retinal images. In particular, we apply a classification approach to determine the conditions for tortuousity in retinal blood vessels.

Parallel database systems are increasingly being deployed to support the performance demands of end-users. While declustering data across multiple nodes facilitates parallelism, initial data placement may not be optimal due to skewed workloads and changing access patterns. To prevent performance degradation, the placement of data must be reorganized, and this must be done on-line to minimize disruption to the system.