Background Mining logic rules from structured knowledge bases is the basis of knowledge engineering. Due to the NP‐hardness of the rule mining problem, logic rules cannot be efficiently induced from knowledge bases, especially large‐scale ones. Idea In this article, we propose a compact and efficient index structure for the maintenance of the intermediate data during top‐down rule mining, such that the memory consumption can be reduced and mining efficiency can be improved. Developing Points The index is based on a mapping from constant symbols to integers and the sorting of the mapped integers. Index update has been dissembled into four basic operations. Moreover, the index itself acts as the cache during top‐down mining. Value Most contributions in existing works employ algorithmic and architectural optimizations to improve efficiency. Data‐oriented optimizations have also been explored to some extent, but the data efficiency is relatively low, and the memory consumption is thus becoming a new challenge for state‐of‐the‐art systems. We tackle this challenge in this article, and our technique has been proven more efficient than state‐of‐the‐art systems. We evaluate our method on six datasets which contain up to 160 K records and are frequently used as benchmarks in tasks related to knowledge engineering. The experimental results show that the proposed technique speeds up the rule mining procedure by on average and reduces memory consumption by up to 70%. The space overhead of the data structure is about twice that of the indexed records, which is more than 80% lower than that of the state‐of‐the‐art technique.

Fraud detection has attracted massive research interests due to its broad applications, especially on e-commerce websites, where fraudulent users interact with products unfairly to mislead potential customers for monetary incentives. Previous studies have made significant research progress on fraud detection, while only a few of them pay attention to adaptability and scalability of their methods. As a result, most of prior fraud detectors cannot perform consistently well across different scenarios due to issues such as sparsity, pattern inconsistency and camouflage. To address these issues, this paper proposes an adaptive algorithm called AdaptFD to effectively detect fraudulent users on e-commerce platforms. In particular, we first tackle sparsity issue with finer granularity by inferring relevant coefficients on entity level during runtime. Next, variable regularization terms are designed for pattern inconsistency tolerance. Lastly, we analyze the behavior patterns of users to reveal camouflage of fraudsters. Together, AdaptFD can adapt to different scenarios and handle with large-scale data efficiently. We also provide theoretical guarantees for our algorithm in linear time complexity and training convergence. Extensive experiments on four real-world datasets demonstrate that AdaptFD outperforms other state-of-the-art baselines. It’s worth noticing that our algorithm achieves up to 560x speedup on the real-world dataset, compared with the most related baseline.

Structured knowledge bases are critical for the interpretability of AI techniques. RDF KBs, which are the dominant representation of structured knowledge, are expanding extremely fast to increase their knowledge coverage, enhancing the capability of knowledge reasoning while bringing heavy burdens to downstream applications. Recent studies employ semantic compression to detect and remove knowledge redundancies via semantic models and use the induced model for further applications, such as knowledge completion and error detection. However, semantic models that are sufficiently expressive for semantic compression cannot be efficiently induced, especially for large-scale KBs, due to the hardness of logic induction. In this article, we present estimation-based optimizations for the semantic compression of RDF KBs from the perspectives of input and intermediate data involved in the induction of first-order logic rules. The negative sampling technique selects a representative subset of all negative tuples with respect to the closed-world assumption, reducing the cost of evaluating the quality of a logic rule used for knowledge inference. The number of logic inference operations used during a compression procedure is reduced by a statistical estimation technique that prunes logic rules of low quality. The evaluation results show that the two techniques are feasible for the purpose of semantic compression and accelerate the compression algorithm by up to 47x compared to the state-of-the-art system. • Negative sampling reduces the cost of a single logic inference. • Negative sampling speeds up semantic compression of RDF KBs by more than 2x. • Entailment estimation reduces the number of logic inferences in logic rule mining. • Entailment estimation speeds up semantic compression of RDF KBs by up to 47x. • Entailment estimation reduces up to 99% of memory cost of semantic compression.

Story Ending Generation is a task of generating a coherent and sensible ending for a given story. The key challenges of this task are i) how to obtain a good understanding of context, ii) how to capture hidden information between lines, and iii) how to obtain causal progression. However, recent machine learning models can only partially address these challenges due to the lack of causal entailment and consistency. The key novelty in our proposed approach is to capture the hidden story by generating transitional commonsense sentences between each adjacent context sentence, which substantially enriches causal and consistent story flow. Specifically, we adopt a soft causal relation using people’s everyday commonsense knowledge to mimic the cognitive understanding process of readers. We then enrich the story with causal reasoning and utilize dependency parsing to capture long range text relations. Finally, we apply multi-level Graph Convolutional Networks to deliver enriched contextual information across different layers. Both automatic and human evaluation results show that our proposed model can significantly improve the quality of generated story endings.

Abstract Knowledge data has been widely applied to artificial intelligence applications for interpretable and complex reasoning. Modern knowledge bases are constructed via automatic knowledge extraction from open‐accessible sources. Thus the sizes of KBs are continuously growing, heavily burdening the maintenance and application of the knowledge data. Besides the grammatical redundancies, semantically repeated information also frequently appears in knowledge bases but is still under‐explored. Existing semantic compressors fail to efficiently discover expressive patterns and thus perform unsatisfyingly on knowledge data. This article proposes SInC, a semantic inductive compressor, to efficiently induce first‐order Horn rules and semantically compress knowledge bases. SInC improves the scalability of top‐down rule mining by batching correlated records in the cache and further optimizes the pruning of duplication and specialization via an identifier structure of Horn rules. SInC was evaluated on real‐world and synthetic datasets and compared against the state‐of‐the‐art. The results show that the batched caching speed up the rule mining procedure by more than two orders while consuming fewer than three times memory space. The identifier technique speeds up the duplication and specialization pruning by orders of magnitude with less than 5‰ and 15% error rates, respectively. SInC outperforms the state‐of‐the‐art from the perspective of overall compression on both scalability and compression effect.

The current wave of AI is heavily driven by data, especially for cognitive capabilities. Minimization of data semantics not only reveals core information but also becomes a guide in a wide range of domains. However, scalability is theoretically weak in pure semantic methodologies. In order to cooperate with large DBs, expressiveness is over-sacrificed in existing techniques. Thus, the quality of discovered patterns and redundancies are far from satisfactory. In this article, we formalize symbolic minimization on relational DBs and prove its NP-Completeness. A lossless technique is proposed by inducing generic first-order Horn rules that infer a subset of records from the others. More importantly, we further improve the scalability via effective caching and pruning without sacrificing the expressiveness of first-order Horn rules. A concrete system is implemented and comprehensively evaluated. Experiments show that our technique removes up to 70% contents and outperforms the state-of-the-art on minimization and scalability. The optimizations reduce up to 96% memory consumption and accelerate the performance by two orders. Our technique shows the practicality of pure semantic approaches in database mining.

Modelling popularity for academic fields have been an ongoing study. This is especially important for emerging fields as accurate models allow efforts and resources to be efficiently utilised on promising research directions. Existing modelling methods mainly face at least one of the following three challenges: Using domain specific binary classifications on topics to be ether emerging or non-emerging leading to low generalizability. Having a biased and restricted scope of investigation due to topic terms requiring manual mining from a limited number of documents. Neglecting the effect of "cold start" when utilising a field’s historical features as inputs for popularity forecasting especially when the field is emerging and possesses limited historical data. In this paper, we build upon existing work to propose a forecasting algorithm addressing all three challenges. Firstly, we define popularity forecasting as a multivariate regression problem. Next, by combining the utilisation of existing academic databases, time specific node embeddings, and dynamic time warping, we extract concurrently trending neighbour fields whose trending pattern are similar to the field of interest. Lastly, multivariate forecasting is conducted using long short-term memory (LSTM) and dual attention recurrent neural networks (DA-RNN). Experimental results on 10 emerging and non-emerging fields of study showcases the existence and various dynamics of "cold start". Additionally, the proposed algorithm is also shown to greatly reduce RMSE, MAE, and MAPE against traditional methods for emerging fields while retaining similar performance for non-emerging fields. This validates the significance of these challenges against existing methods and provides insight on the dependency structure of emerging topics with their historical features.

E-commerce platforms heavily rely on automatic personalized recommender systems, e.g., collaborative filtering models, to improve customer experience. Some hybrid models have been proposed recently to address the deficiency of existing models. However, their performances drop significantly when the dataset is sparse. Most of the recent works failed to fully address this shortcoming. At most, some of them only tried to alleviate the problem by considering either user side or item side content information. In this article, we propose a novel recommender model called Hybrid Variational Autoencoder (HVAE) to improve the performance on sparse datasets. Different from the existing approaches, we encode both user and item information into a latent space for semantic relevance measurement. In parallel, we utilize collaborative filtering to find the implicit factors of users and items, and combine their outputs to deliver a hybrid solution. In addition, we compare the performance of Gaussian distribution and multinomial distribution in learning the representations of the textual data. Our experiment results show that HVAE is able to significantly outperform state-of-the-art models with robust performance.

Many recent relation extraction methods are proposed based on distantly supervised learning to address the issue of expensive human labelling. They automatically align relation instances from a knowledge base with unstructured text. Although these methods solve the problem of insufficient labelled data and are scalable, due to automatic labelling, they suffer from a large amount of noisy data. In this paper, we propose a relation extraction method based on a BiLSTM approach to alleviate the noise by automatic labelling. It firstly performs unsupervised pretraining for word embeddings, dependency path tokens and entity embeddings. The attention mechanism we employed in the pretraining module helps select relevant information. As pretraining denoise and encode the semantic information, the relation types can be more efficiently classified by supervised learning using less labelled training data. Experiments show that our approach significantly outperforms previous state-of-the-art baselines when labelled training data is insufficient.

Relation extraction is an important task for information extraction aiming to detect and extract semantic relationships between entity pairs in sentences. A lot of recently proposed methods for relation extraction have gained remarkable results using deep neural networks. However, a deep network usually requires expensive computational power and is time-consuming when training. To address this problem, we introduce a novel neural relation extraction model that jointly trains a seq2seq regulariser with a classification module. As the regulariser and the classification module share the encoder, the whole model is less complicated compared to novel approaches like BERT. We show that our model achieves the same or better performance than the pre-trained BERT model using sufficient labelled data in much less training time.

Although matrix factorization and its variants have proved their effectiveness in learning user preferences, they violate the triangle inequality and may fail to capture the inner grained preference information. Thus, metric learning based models have attracted increasing interests in recommender systems. However, most of these models only measure the distance in Euclidean space, though it is known to limit the prediction performance. To address this problem, this paper proposes curvilinear collaborative metric learning (CCML) as a solution. Rather than learning from Euclidean distance, CCML measures the “path” (i.e. curvilinear distance) between the user and items. Therefore, it is able to better infer information (in geometrical representation) and user-item relations behind the observed data points. Under this setting, the relations between the user and items are not linearly reflected by the relation vector. In order to effectively learn the representation of items, we propose to fuse macro features of categories and micro representations of items to form their latent vectors. Our model can be less prone to be affected by the noise commonly presented in datasets by separately learning macro and micro features. Experimental results on eight public recommendation datasets demonstrate that CCML produces a outstanding performance compared with five competitive baselines. Finally, quantitative analysis is included to verify the efficiency and effectiveness of CCML and the macro-micro module.

Big data has been transformed into knowledge by information systems to add value in businesses. Enterprises relying on it benefit from risk management to a certain extent. The value, however, depends on the quality of data. The quality needs to be verified before any use of the data. Specifically, measuring the quality by simulating the real life situation and even forecast it accurately turns into a hot topic. In recent years, there have been numerous researches on the measurement and assessment of data quality. These are yet to utilize a scientific computational method for the measurement and prediction. Current methods either fail to make an accurate prediction or do not consider the correlation and time sequence factors of the data. To address this, we design a model to extend machine learning technique to business applications predicting this. Firstly, we implement the model to detect data noises from a risk dataset according to an international data quality standard from banking industry and then estimate their impacts with Gaussian and Bayesian methods. Secondly, we direct sequential learning in multiple deep neural networks for the prediction with an attention mechanism. The model is experimented with various network methodologies to show the predictive power of machine learning technique and is evaluated by validation data to confirm the model effectiveness. The model is scalable to apply to any industries utilizing big data other than the banking industry.

Statistical divergence is widely applied in multimedia processing, basically due to regularity and interpretable features displayed in data. However, in a broader range of data realm, these advantages may no longer be feasible, and therefore a more general approach is required. In data detection, statistical divergence can be used as a similarity measurement based on collective features. In this paper, we present a collective detection technique based on statistical divergence. The technique extracts distribution similarities among data collections, and then uses the statistical divergence to detect collective anomalies. Evaluation shows that it is applicable in the real world.

Many recently proposed relation extraction methods are based on distantly supervised learning. They use data from existing knowledge bases as training data. Although the methods solve the problem of insufficient labelled data and are highly scalable, they suffer from a large amount of incorrectly labelled data. Instead of using these distantly supervised approaches, this paper proposes an alternative relation extraction method. It firstly performs unsupervised learning to train relation embeddings by a neural network. As the relation embeddings encode the semantic information of the original sentences and their entity pairs, these embeddings can be efficiently classified by supervised learning. Since the relation embedding phase is based on unsupervised learning, labelled data is only required in the classification phase. Experiments show that our proposed approach significantly outperforms the state-of-the-art baselines when labelled training data is insufficient.

Summary Provenance is information about the origin and creation of data. In data science and engineering related with cloud environment, such information is useful and sometimes even critical. In data analytics, it is necessary for making data‐driven decisions to trace back history and reproduce final or intermediate results, even to tune models and adjust parameters in a real‐time fashion. Particularly, in cloud, users need to evaluate data and pipeline trustworthiness. In this paper, we propose a solution: LogProv, toward realizing these functionalities for big data provenance, which needs to renovate data pipelines or some of big data software infrastructure to generate structured logs for pipeline events, and then stores data and logs separately in cloud space. The data are explicitly linked to the logs, which implicitly record pipeline semantics. Semantic information can be retrieved from the logs easily since they are well defined and structured beforehand. We implemented and deployed LogProv in Nectar Cloud,* associated with Apache Pig, Hadoop ecosystem, and adopted Elasticsearch to provide query service. LogProv was evaluated and empirically case studied. The results show that LogProv is efficient since the performance overhead is no more than 10%; the query can be responded within 1 second; the trustworthiness is marked clearly; and there is no impact on the data processing logic of original pipelines.

We present a new summary evaluation approach that does not require human model summaries. Our approach exploits the compositional capabilities of corpus-based and lexical resource-based word embeddings to develop the features reflecting coverage, diversity, informativeness, and coherence of summaries. The features are then used to train a learning model for predicting the summary content quality in the absence of gold models. We evaluate the proposed metric in replicating the human assigned scores for summarization systems and summaries on data from query-focused and update summarization tasks in TAC 2008 and 2009. The results show that our feature combination provides reliable estimates of summary content quality when model summaries are not available.

ROUGE is one of the first and most widely used evaluation metrics for text summarization.However, its assessment merely relies on surface similarities between peer and model summaries.Consequently, ROUGE is unable to fairly evaluate summaries including lexical variations and paraphrasing.We propose a graph-based approach adopted into ROUGE to evaluate summaries based on both lexical and semantic similarities.Experiment results over TAC AESOP datasets show that exploiting the lexico-semantic similarity of the words used in summaries would significantly help ROUGE correlate better with human judgments.

Geolocated social media data provide a powerful source of information about places and regional human behavior. Because only a small amount of social media data have been geolocation‐annotated, inference techniques play a substantial role to increase the volume of annotated data. Conventional research in this area has been based on the text content of posts from a given user or the social network of the user, with some recent crossovers between the text‐ and network‐based approaches. This paper proposes a novel approach to categorize highly‐mentioned users (celebrities) into Local and Global types, and consequently use Local celebrities as location indicators. A label propagation algorithm is then used over the refined social network for geolocation inference. Finally, we propose a hybrid approach by merging a text‐based method as a back‐off strategy into our network‐based approach. Empirical experiments over three standard Twitter benchmark data sets demonstrate that our approach outperforms state‐of‐the‐art user geolocation methods.

One of the fundamental problem in data management and data integration fields is Record Matching, which refers to identifying records that relate to the same entities across different data sources. In recent literature, active learning has demonstrated to be effective for record matching. One of the key steps of active learning is to build a proper initial classifier, with which active learning algorithms can quickly locate informative examples for training accurate models. However, in this process, example labelling for model training is usually expensive. Even worse, if a weak initial classifier is used, the labelling cost can be significantly increased. In this paper, we propose an unsupervised algorithm to determine the initial classifier. The process of classifier initialization requires no labelling cost. Then on our proposed algorithm, we present an active sampling method for selecting informative examples. The experiments show that our approach achieves competitive learning performance with much less labelling cost than other approaches of active learning.

Most state-of-the-art service selection approaches assume user preferences can be provided by the target user with sufficient precision and ignore historical service usage data for all users. It is desirable for ordinary users to possess a new service selection approach that can recommend satisfactory services to them even when their service selection preferences are specified imprecisely in terms of vagueness, inaccuracy, and incompleteness. This paper proposes a novel service selection approach that resolves the imprecise characteristics of user preferences and can recommend satisfactory services for users with varying cognitive levels in terms of service experience. The proposed service selection approach is comprised of four major tasks: 1) employ user-friendly linguistic variables to collect apparent user preferences (AUP) and convert the linguistic variables to standardized fuzzy weights as AUP weights; 2) evaluate all users' respective cognitive levels for the target service type and obtain the cognitive level threshold for that type of services; 3) adjust the AUP weights based on the calculated cognitive levels and the threshold, and supplement the potential user preferences weights; and 4) prioritize candidate services per a user satisfaction maximization objective. In-depth comparative experimental evaluations were performed using two real-world datasets. The results show that our service selection model outperforms three other representative ones and could provide a stable and reliable selection of services for the users with low service cognitive levels.

Due to the popularity of web services on the Internet, it is important to have a clear view of their utilization behaviors. Despite asynchronous service invocations and distributed executions can provide better user experience, our views are blurred by out-of-order and fragmented service logs. Researchers have been trying various methods to reveal emerging service orchestration patterns, but nearly all of them have taken deterministic approaches. Hence, they do not natively cater for incomplete data and noises. In this paper, we propose to address these problems by using topic models aiming to reveal service orchestration patterns from sparse service logs. Probabilistic approaches do not only tolerate data defects, but their associated approximation methods also overcome combinatorial explosion. We first investigate the implications of sparsity on topic models. Secondly, we propose an extended time-series form of susceptible-infectious-recovered model to monitor the dynamics of emerging service orchestrations. We quantify their emerging-potential by estimated effective-reproduction-number, which is obtained incrementally by Bayesian parameter estimations. Guided by our proposed emerging-potential measure, one can profile and categorize emerging service orchestration patterns, and generate automated alerts on upcoming consumption peaks. In practice, our model enables service providers to better allocate their resources to meet demands dynamically. While our findings affirm that biterm topic model can be applied to service logs with short and sparse log entries, the effectiveness of our proposed monitoring solutions is also shown by experiments.

Service recommendation systems have been trying to utilize context-aware information to recommend services that better meet the needs of the service consumers. However, current context-aware service recommendation techniques are mainly based on individual intelligence or the local knowledge of users, and do not take into consideration the common knowledge among different users. To address this, recent research has attempted to use role-based approaches to recommend services to other members within the same context group. However, these proposed algorithms are inefficient and may not scale to cope with the large amount of mobile traffic in the real-world. This paper proposes novel algorithms with better runtime complexity, and further extends them to a MapReduce style to take advantage of popular distributed computing platforms. Experiments running on a medium-sized high performance computing cluster demonstrate that our proposed algorithms outperform previous work in runtime complexity and scalability.

Multi Sentence Compression (MSC) is of great value to many real world applications, such as guided microblog summarization, opinion summarization and newswire summarization. Recently, word graph-based approaches have been proposed and become popular in MSC. Their key assumption is that redundancy among a set of related sentences provides a reliable way to generate informative and grammatical sentences. In this paper, we propose an effective approach to enhance the word graph-based MSC and tackle the issue that most of the state-of-the-art MSC approaches are confronted with: i.e., improving both informativity and grammaticality at the same time. Our approach consists of three main components: (1) a merging method based on Multiword Expressions (MWE); (2) a mapping strategy based on synonymy between words; (3) a re-ranking step to identify the best compression candidates generated using a POS-based language model (POS-LM). We demonstrate the effectiveness of this novel approach using a dataset made of clusters of English newswire sentences. The observed improvements on informativity and grammaticality of the generated compressions show an up to 44% error reduction over state-of-the-art MSC systems.

Aggregation operation plays an important role in time series database management. As the amount of data increases, current solutions such as summary table and MapReduce-based methods struggle to respond to such queries with low latency. Other approaches such as segment tree based methods have a poor insertion performance when the data size exceeds the available memory. This paper proposes a new segment tree based index called PISA, which has fast insertion performance and low latency for aggregation queries. PISA uses a forest to overcome the performance disadvantages of insertions in traditional segment trees. By defining two kinds of tags, namely code number and serial number, we propose an algorithm to accelerate queries by avoiding reading unnecessary data on disk. The index is stored on disk and only takes a few hundred bytes of memory for billions of data points. PISA can be easily implemented on both traditional databases and NoSQL systems, examples including MySQL and Cassandra. It handles aggregation queries within milliseconds on a commodity server for a time range that may contain tens of billions of data points.

When making clinical decisions, practitioners need to rely on the most relevant evidence available. However, accessing a vast body of medical evidence and confronting with the issue of information overload can be challenging and time consuming. This paper proposes an effective summarizer for medical evidence by utilizing both UMLS and WordNet. Given a clinical query and a set of relevant abstracts, our aim is to generate a fluent, well-organized, and compact summary that answers the query. Analysis via ROUGE metrics shows that using WordNet as a general-purpose lexicon helps to capture the concepts not covered by the UMLS Metathesaurus, and hence significantly increases the performance. The effectiveness of our proposed approach is demonstrated by conducting a set of experiments over a specialized evidence-based medicine (EBM) corpus - which has been gathered and annotated for the purpose of biomedical text summarization.

Big Data though it is a hype up-springing many technical challenges that confront both academic research communities and commercial IT deployment, the root sources of Big Data are founded on data streams and the curse of dimensionality. It is generally known that data which are sourced from data streams accumulate continuously making traditional batch-based model induction algorithms infeasible for real-time data mining. Feature selection has been popularly used to lighten the processing load in inducing a data mining model. However, when it comes to mining over high dimensional data the search space from which an optimal feature subset is derived grows exponentially in size, leading to an intractable demand in computation. In order to tackle this problem which is mainly based on the high-dimensionality and streaming format of data feeds in Big Data, a novel lightweight feature selection is proposed. The feature selection is designed particularly for mining streaming data on the fly, by using accelerated particle swarm optimization (APSO) type of swarm search that achieves enhanced analytical accuracy within reasonable processing time. In this paper, a collection of Big Data with exceptionally large degree of dimensionality are put under test of our new feature selection algorithm for performance evaluation.

In the real-world applications, heterogeneous interdependent attributes that consist of both discrete and numerical variables can be observed ubiquitously. The usual representation of these data sets is an information table, assuming the independence of attributes. However, very often, they are actually interdependent on one another, either explicitly or implicitly. Limited research has been conducted in analyzing such attribute interactions, which causes the analysis results to be more local than global. This paper proposes the coupled heterogeneous attribute analysis to capture the interdependence among mixed data by addressing coupling context and coupling weights in unsupervised learning. Such global couplings integrate the interactions within discrete attributes, within numerical attributes and across them to form the coupled representation for mixed type objects based on dimension conversion and feature selection. This work makes one step forward towards explicitly modeling the interdependence of heterogeneous attributes among mixed data, verified by the applications in data structure analysis, data clustering evaluation, and density comparison. Substantial experiments on 12 UCI data sets show that our approach can effectively capture the global couplings of heterogeneous attributes and outperforms the state-of-the-art methods, supported by statistical analysis.

A recent study on collective attention in Twitter shows that an epidemic spreading of hashtags is predominantly driven by external factors. We extend a time-series form of susceptible-infectious-recovered (SIR) model to monitor microblog emerging outbreaks by considering both endogenous and exogenous drivers. In addition, we adopt partially labeled Dirichlet allocation (PLDA) model to generate both background latent topics and hashtag topics. It overcomes the problem of small available samples in hashtag analysis by including related but unlabeled tweets through inference. We standardize hashtag topic contagiousness measure as the estimated effective-reproduction-number R derived from epidemiology. It is obtained by Bayesian parameter estimation. Guided by R, one can profile and categorize emerging topics, and generate alerts on potential outbreaks. Experiment results confirm the effectiveness of this approach.

Due to the popularity of using web services to deliver services on the Web, a clear view of how they are being consumed is becoming critical. Researchers have been trying multiple methods to reveal actual service orchestration patterns from service logs. However, most of the discovery methods have taken deterministic approaches, and hence, they do not provide enough allowance to cater for incomplete data and noises. On the other hand, most investigations do not take combinatorial explosion into consideration leading to scalability problem. Moreover, asynchronous web service invocations and distributed executions also make it difficult to identify service patterns due to the randomness in log record generation. In this paper, probabilistic topic mining class of solutions are applied to reveal web service orchestration patterns from service logs, in which robust approximation methods are available to provide scalability. Data sparsity problem in service log is also investigated by using biterm topic model (BTM) and comparing its results with traditional latent Dirichlet allocation (LDA) model. In addition, a topic matching method is introduced based on the Hungarian method on Jensen-Shannon divergence matrix, whilst notions of aggJSD and autoJSD are also introduced to measure topic diversity between matched topic sets and within a single topic set respectively. Experiment results confirm that BTM can be used for service logs with short log entries and with sparsity larger than 90% approximately.

Cloud computing platforms facilitate efficiently processing complicated computing problems of which the time cost used to be unacceptable. Recent research has attempted to use role-based approaches for context-aware service recommendation, yet role mining problem has been proven to be difficult to compute. Currently proposed role-mining algorithms are inefficient and may not scale to cope with the huge amount of data in the real-world. This paper proposes a novel algorithm with much better runtime complexity, and in MapReduce style to take advantage of popular distributed computing platforms. Experiments running on a medium-sized high performance computing cluster demonstrate that our proposed algorithm works well with both running time complexity and scalability.

Due to the popularity of smartphones, finding and recommending suitable services on mobile devices are increasingly important. Recent research has attempted to use role-based approaches to recommend mobile services to other members among the same group in a context dependent manner. However, the traditional role mining approaches originated from the domain of security control tend to be rigid and may not be able to capture human behaviors adequately. In particular, during the course of role mining process, these approaches easily result in over-fitting, i.e., too many roles with slightly different service consumption patterns are found. As a result, they fail to reveal the true common preferences within the user community. This paper proposes an online role mining algorithm with a residual term that automatically group users according to their interests and habits without losing sight of their individual preferences. Moreover, to resolve the over-fitting problem, we relax the role mining mechanism by introducing quasi-roles based on the concept of quasi-bicliques. Most importantly, the new concept allows us to propose a monitoring framework to detect and correct over-fitting in online role mining such that recommendations can be made based on the latest and genuine common preferences. To the best of our knowledge, this is a new area in service recommendation that is yet to be fully explored.

Non-Functional (NF) requirement is very important for the success of a software service. Considering that there could be multiple services implementing a same function, it is crucial for software providers to understand the real NF demands from consumers so that they can meet these demands and attract users. It is also crucial for consumers to know what is being offered so that they can pose realistic NF requests. We address both issues here by proposing a NF requirement analysis and recommendation system which works for both providers and consumers. NF requirements from various sources are first collected, and then we apply the factor analysis technique to identify those independent latent factors which contribute to those observable NF values. Finally we use cluster analysis to summarize the popular NF demands. Our experiment result shows the effectiveness of this approach.

While many process mining algorithms have been proposed recently, there does not exist a widely accepted benchmark to evaluate and compare these process mining algorithms. As a result, it can be difficult to choose a suitable process mining algorithm for a given enterprise or application domain. Some recent benchmark systems have been developed and proposed to address this issue. However, evaluating available process mining algorithms against a large set of business models (e.g., in a large enterprise) can be computationally expensive, tedious, and time-consuming. This paper investigates a scalable solution that can evaluate, compare, and rank these process mining algorithms efficiently, and hence proposes a novel framework that can efficiently select the process mining algorithms that are most suitable for a given model set. In particular, using our framework, only a portion of process models need empirical evaluation and others can be recommended directly via a regression model. As a further optimization, this paper also proposes a metric and technique to select high-quality reference models to derive an effective regression model. Experiments using artificial and real data sets show that our approach is practical and outperforms the traditional approach.

The Burrows Wheeler transform (BWT) has become popular in text compression, full-text search, XML representation, and DNA sequence matching. It is very efficient to perform a full-text search on BWT encoded text using backward search. This paper aims to study different approaches for applying BWT on multi-byte encoded (e.g. UTF-16) text documents. While previous work has studied BWT on word-based models, and BWT can be applied directly on multi-byte encodings (by treating the document as single-byte coded), there has been no extensive study on how to utilize BWT on multi-byte encoded documents for efficient full-text search. Therefore, in this paper, we propose several ways to efficiently backward search multi-byte text documents. We demonstrate our findings using Chinese text documents. Our experiment results show that our extensions to the standard BWT method offer faster search performance and use less runtime memory.

While many process mining algorithms have been proposed recently, there does not exist a widely-accepted benchmark to evaluate and compare these process mining algorithms. As a result, it can be difficult to choose a suitable process mining algorithm for a given enterprise or application domain. Some recent benchmark systems have been developed and proposed to address this issue. However, evaluating available process mining algorithms against a large set of business models (e.g., in a large enterprise) can be computationally expensive, tedious and time-consuming. This paper proposes a novel framework that can efficiently select the process mining algorithms that are most suitable for a given model set. In particular, it attemptsto investigate how we can avoid evaluating numerous process mining algorithms on all given process models.

We propose a framework for mobile advertising covering Value-Added Services where an ad-database is maintained on the device and both selection and display are dictated by the device. Advantages over existing mobile marketing are that ads are more timely, viable on a variety of use cases, can be both location-sensitive and personalized with minimal privacy concerns, and provide an obvious means for subsidizing users' service costs. We construct a suitable selection algorithm and evaluate its execution, accuracy and scalability. We show that ad-serving can be done under the processing constraints imposed by mobiles, which may lead to improvements in mobile marketing effectiveness.

Efficient XML filtering has been the fundamental technique in recent Web service and XML publish/subscribe applications. In this article, we consider the problem of filtering a streaming XML data efficiently against a large number of branch XPath queries. To improve the performance of XML filtering, branch queries are grouped into similar queries, and the common paths between queries in the same group are identified. After performing structural matching of queries, queries are organized in a way that multiple queries can be evaluated simultaneously in the post-processing phase. In the post-processing phase, join operations are executed in a pipeline fashion, and intermediate join results are shared amongst the queries in the same group. As a result, the total number of join operations performed in the post-processing phase is significantly reduced. In addition, we also present how to efficiently return all matching elements for each matching branch query. Experiments show that our proposal is efficient and scalable compared to previous work.

We present an approach for discovery of groups of unusual data points that are anomalous for similar reasons. This differs from clustering in that the points that are grouped may be quite 'distant' and can use categorical attributes, and differs from anomaly detection in that we are not looking for individual outliers.

Collaborative tagging is the aggregate effort by a community of online users to annotate web content with metadata labels called tags. It is a simple activity that enriches our knowledge about digital content, and has gained popularity with services such as Del.icio.us. Del.icio.us has a large repository that evolves daily, presenting interesting new problems for IR. We present TagScore, a scoring function to rate the goodness of Del.icio.us tags for their associated web page. It gives us a succinct synopsis for a page that we can use to efficiently find similar pages. Using real Del.icio.us data, we show that our approach gives good correlation to cosine similarity but is several hundred times faster and requires minimal storage overhead.

Social tagging describes a community of users labeling web content with tags. It is a simple activity that enriches our knowledge about resources on the web. For a computer to help users search the tagged repository, it must know when tags are good or bad. We describe TagScore, a scoring function that rates the goodness of tags. The tags and their ratings give us a succinct synopsis for a page. We `find similar' pages in Del.icio.us by comparing synopses. Our approach gives good correlation to the full cosine similarity but is hundreds of times faster.

Most geometric routing algorithms for ad-hoc wire- less networks rely on greedy forwarding strategies to deliver messages from their sources to destinations. However, there is no guarantee that paths produced by these protocols are optimal. In this paper, we present a Path Regression approach which improves the qualities of paths produced by all geometric routing protocols. Furthermore, we show the use of Path Regression in RFR which progressively looks for an optimal path that can only be produced by DSR. Extensive experiments show that the proposed algorithm out-performs other approaches such as GOAFR+ by a significant margin.

This demonstration aims to illustrate a new prototype for presenting remote data from heterogeneous data sources, which includes searching, collecting, transforming, summarizing and collating query results from these remote data sources. This prototype will then automatically transform the query results from the remote data sources into a suitable form that can be presented in the remote device. The transformation will address all the requirements, preferences and constraints associated with a user, device or enterprise.

As XML database sizes grow, the amount of space used for storing the data and auxiliary data structures becomes a major factor in query and update performance. This paper presents a new storage scheme for XML data that supports all navigational operations in near constant time. In addition to supporting efficient queries, the space requirement of the proposed scheme is within a constant factor of the information theoretic minimum, while insertions and deletions can be performed in near constant time as well. As a result, the proposed structure features a small memory footprint that increases cache locality, whilst still supporting standard APIs, such as DOM, and necessary database operations, such as queries and updates, efficiently. Analysis and experiments show that the proposed structure is space and time efficient.

New means of communication are constantly emerging, some of which may constitute resource misuse of an organisation's network system. Identifying the protocols used is straight-forward when inspecting network logs, but we focus on the problem of identifying the underlying protocol present in an unknown TCP connection. Actions are difficult to detect if the underlying protocol is encrypted and tunneled through a proxy server or SSH. We use a graph-comparison approach to build profiles of several protocols, and attempt to classify an unknown, encrypted protocol against these profiles using only the visible behaviour of the protocol being tunneled - the size, timing and direction of packets

With the recent adoption of marketing activities outsourcing, there have been increasing demands and concerns for privacy control. The traditional approach of a bulk transmission of the customers' information to a marketing company cannot meet such demands, especially in the finance and healthcare businesses. Therefore, we propose a layered architecture and a development methodology for end-to-end privacy control over the export of each individual customer's records through a Web services platform, according to the corresponding enterprise's privacy control policies. A Web services system, with up-dated security and privacy facilities, can provide a suitable interoperation platform for required application-to-application interactions over the Internet. We further develop a conceptual model and an interaction protocol to send only the required part of a customer's records at a time. We illustrate our approach for end-to-end privacy control with a tele-marketing case study and show how the software of the outsourced call center can be integrated effectively with the Web services of a bank to protect privacy. Copyright 2005 ACM.

Web services are becoming important in applications from electronic commerce to application interoperation. While numerous efforts have focused on service composition, service selection among similar services from multiple providers has not been addressed. Such issue is more serious when services are embraced in Grid platforms, which are usually resource-conscious. Experimental results show that our considerations are valid and our preliminary solution works well in our Globus grid network.

Collaborative editing systems allow multiple users to edit the same set of documents collaboratively over the computer networks synchronously or asynchronously. Although they face technical challenges similar to those addressed in the literature of distributed computing and database systems, they present a unique set of problems and issues that have not been addressed. For example, timely propagation of user operations across computer networks is needed to promote mutual awareness of users and user activities. This paper presents our prototyped collaborative editing system with a novel and yet extremely efficient mechanism for synchronizing updates from concurrent editors, which has been integrated with the SODA native XML database management system.

While numerous efforts have focused on service composition in the Grid environment, service selection among similar services from multiple providers has not been addressed. In particular, all service composition work done so far are based on a given selection of services under a well set environment. As a result, uncertainty (e.g., server load, network traffic, computation time of the services due to changing memory and other unexpected conditions) under a real, dynamic environment has never been considered. This paper prototypes the service selection under a Grid environment and proposes an uncertainty framework to address the issue. Experimental results show that our considerations are valid and our preliminary solution works well in our Globus Grid network.

Based on the Reserved Graph Grammar (RGG), this paper presents a unified framework to manage model-based information on the Web in a hierarchical structure. The framework allows models, schemas, and data instances to be represented explicitly and uniformly. The uniform representation of the framework also enables simple user-defined graph transformation rules for different Web data models to translate schemas and data instances between different formats. In addition, the framework implements a set of prototype tools for users to identify meta-primitives at the meta-model level, to define a model or schema by specifying a set of graph grammar rules and to draw the structure of data instances. These features promote a wide scope of Web-related applications, such as information exchange between different organizations, and integration of data coming from heterogeneous information sources.

Ability to keep track of records for various biological experiments allows for future validation of the current experiments and other non-experimental laboratory procedures. With the increasing popularity of publishing biological data in XML format, there arises the need for the control and management of this data, as well as dynamically exporting this data to various formats for reporting purposes. As such data is constantly changing, users want to be able to query previous versions, plotting data across different versions from history, query changes in documents, as well as to retrieve a particular document version efficiently. This paper proposes an XML-based version management system for tracking and analyzing data obtained from any laboratory experiments in an effective and meaningful manner. This includes experiments ranging from genomic, proteomic and protein structural. We also present methods for importing non XML data into the system as well as generating reports in multiple formats dynamically.

Automating the process of information retrieval and integration of heterogeneous biological data is complex and difficult. This paper describes an approach to solve this problem by using XML technologies such as XML Schema and an XML-based active rules system. Current limitations of active rule system for XML databases are discussed. We then propose a template for defining rules that is consistent with the current XQuery specification, a defacto standard language for querying XML data. Finally, an example scenario is used to illustrate how these techniques can come together in integrating heterogeneous biological data sources.

With the increasing popularity of XML, there arises the need for managing and querying information in this form. Several query languages, such as XQuery, have been proposed which return their results in document order. However, most recent efforts focused on query optimization have disregarded order. This paper presents a simple yet elegant method to maintain document ordering for XML data. Analysis of our method shows that it is indeed efficient and scalable, even for changing data.

The richness of semi-structured data allows data of varied and inconsistent structures to be stored in a single database. Such data can be represented as a graph, and queries can be constructed using path expressions, which describe traversals through the graph. Instead of providing optimal performance for a limited range of path expressions, we propose a mechanism which is shown to have consistent and high performance for path expressions of any complexity, including those with descendant operators (path wildcards). We further detail mechanisms which employ our index to perform more complex processing, such as evaluating both path expressions containing links and entire (sub) queries containing path based predicates. Performance is shown to be independent of the number of terms in the path expression, even where these contain wildcards. Experiments show that our index is faster than conventional methods by up to two orders of magnitude for certain query types, is small, and scales well.

The development of high-throughput genome sequencing and protein structure determination techniques have provided researchers with a wealth of biological data. Integrated analysis of such data is difficult due to the disparate nature of the repositories used to store this biological data and of the software used for its analysis. This paper presents a framework based upon the use of semi-structured database management systems that would provide an integrated interface for the collection, storage and retrieval of biological data from existing repositories and of biological information generated by existing analysis programs. A simple implementation that integrates information from databases and analytical programs is presented as a proof of concept. In particular, this paper focuses on the data transformation, data integration, and the support of active rules for biological data.

Many handheld applications receive data from a primary database server and operate in an intermittently connected environment these days. They maintain data consistency with data sources through sychronization. In certain applications such as sales force automation, it is highly desirable if updates on the data source can be reflected at the handheld applications immediately. This paper proposes an efficient method to synchronize XML data on multiple mobile devices. Each device retrieves and caches a local copy of data from the database source based on a regular path expression. These local copies may be overlapping or disjoint with each other. An efficient mechanism is proposed to find all the disjoint copies to avoid unnecessary synchronizations. Each update to the data source will then be checked to identify all handheld applications which are affected by the update. Communication costs can be further reduced by eliminating the forwarding of unnecessary operations to groups of mobile clients.

With the increasing popularity of storing content on the WWW and intranet in XML form, there arises the need for the control and management of this data. As this data is constantly evolving, users want to be able to query previous versions, query changes in documents, as well as to retrieve a particular document version efficiently. This paper proposes a version management system for XML data that can manage and query changes in an effective and meaningful manner.

Biological databanks have proven useful to bioscience researchers, especially in the analysis of raw data. Computational tools for sequence identification, structural analysis, and visualization have been built to access these databanks. This paper describes a way to utilize these resources (both data and tools) by integrating different biological databanks into a unified XML framework. An interface to access the embedded bioinformatic tools for this common model is built by leveraging the query language of XML database management system. The proposed framework has been implemented with the emphasis of reusing the existing bioinformatic data and tools. This paper describes the overall architecture of this prototype and some design issues.

The richness of the XML data format allows data to be structured in a way which precisely captures the semantics required by the author. It is the structure of the data, however, which forms the basis of all XML query languages. Without at least some notion of the structure, a user cannot meaningfully query the data. This problem is compounded when one considers that heterogeneous data adhering to different schema are likely to exist in the database(s) being queried. This paper proposes a solution based on an efficient proximity index. In particular, we describe a family of encoding and compression schemes which enable us to build an index to efficiently implement the proximity search. Our index is extremely small, and can reflect updates in the underlying database in modest time. Experiments show that our algorithm and implementation are fast and scale well.

A08- "+\t-'(+-(+> -+3CB@D E\t"!F GH( 8- 28530 - %#J+HI$-(+\tK-%0L7\t"-+?\t->+\t-%\t%$&$, J+08M 28530 - \t$O&0P-%%\t-(!08-QR+$2+%\t35SL 'TUEVDW708N 7W0P-\t)+:X.++-("Y\t"W 7"+K'7%\t-(E-(F+$& F ;%$\t&-Z-%0#\tHIY&0P[\t"+- 3J\\]Z-('^ -+) :XMH:_#^R\t#! $,\t.$&%\t+'E\t-[\t"M %"@ #% -%06'%\t&$L0P+3`B@\t"=(%+\tEJ7\t"-A08- H(%$&%\t'\t" $,\t-%0%A0P+[- M0a-(b-(N \t\t-(#%$1$&+'(+& $,\t-%0%A0P+[- M0a-(b-(N 29000-3 %$'(-,\t"+)++$#++'.Ff-\t"7:Z\t"+ag+h -++MF M+ %#\t"-( K08-(i+H-(+:5-/f3MjX-("+ HI6RfN \t\t-(EHI$<-(+k+:l" F+&\t"-m)F Yf-(\t$, HI$-f?-+\t%\t-(2\t"+ag+)\t-WFfn\t"h-( \t$, 28810 1.

Multidimensional information is pervasive in many computer applications including time series, spatial information, data warehousing, and visual data. While semistructured data or XML is becoming more and more popular for information integration and exchange, not much research work has been done in the design and implementation of semistructured database systems to manage multidimensional information efficiently. In this paper, dimension operators have been defined based on a multidimensional logic which we call ML(/spl omega/). It can be used in applications such as multidimensional spreadsheets and multidimensional databases usually found in decision support systems and data warehouses. Finally a multidimensional, an XML database system is prototyped and described in detail. Technologies such as XSL are used to transform or visualise data from different dimensions.

XQL has been argued as just a model for asking for specific sets of elements with very limited query capability. This paper proposes several extensions of XQL to address the issues. The extensions include full-text indexed search, path variables, joins, session-based navigations, and updates. Effort has been spent to preserve the conciseness of the language syntax. Its corresponding query processor with optimization mechanism has been prototyped and available online. Finally, implementation issues are discussed.

The emergence of the Extensible Markup Language (XML) as a new standard for data representation and exchange on the World Wide Web has created a new information revolution. Several proposals have been made to formulate molecular sequences in XML, however none of them mentioned the efficient storage and management of the resultant XML sequence data. This paper addresses some implementation issues of an XML repository for molecular sequence data.

XML has recently attracted many software vendors, business organizations and research institutions over the world as a promising way to represent Web information. The availability of large amounts of XML data on the Web raises several issues that the XML standard does not address. In particular, access control and authorization issues have seldom been addressed. Since XML are usually stored in multiple sources or repositories, discretionary access control is desirable, if it is not necessary. In this paper, we propose a role-based access control (RBAC) model for XML repositories. The resultant RBAC scheme is in XML and heavily relies on XPath.

Although the concept of roles is becoming a popular research issue in object oriented databases and has been proven to be useful for dynamic and evolving applications, it has only been described conceptually in most of the previous work. Moreover, the important issues such as the semantics of roles (e.g., message passing) are seldom discussed. Furthermore, none of the previous work has investigated the idea of role player qualification, which models the fact that not every object is qualified to play a particular role. We present a data model and the semantics of roles. We discuss each of the above issues and illustrate the ideas with examples. From these examples, we can easily see that the problems we discussed are fundamental and indeed exist in many complex applications.

To investigate the underlying principles of a robotic system's design and applications, appropriate specification and modeling tools which can facilitate the quantitative analysis as well as the qualitative analysis involving complex and/or dynamic data and relationships are essential. In this paper, advanced features embodied by dynamic role facilities have been introduced into a conventional object-oriented model, which facilitates the specification and modeling of robotic systems in a natural, incremental and systematic way. The model supports both the top-down and bottom-up design methodologies, as well as the computation of forward kinematics of the robots. With the analysis based on the communications among different roles, one can have further information about the cooperative behaviour and activities among multiple robots. The prototype system has been implemented in Lisp.