Over the past decade, GPUs have demonstrated significant potential in accelerating Online Analytical Processing (OLAP) operations. However, there remains a substantial gap in their application to Online Transaction Processing (OLTP), as GPUs were traditionally considered unsuitable for such workloads. Despite this perception, the massive parallelism and high memory bandwidth of GPUs offer a unique opportunity to process thousands of transactions concurrently, making them promising candidates for OLTP acceleration. Concurrency control schemes, which play a critical role in determining the performance of OLTP systems, may behave differently on GPUs due to their architectural differences from CPUs. This raises a key question: How well do concurrency control schemes designed for CPUs adapt to GPU environments? To answer this, we present gCCTB, the first testbed designed to evaluate concurrency control schemes on GPUs. We implement and benchmark eight CC schemes, including six classic CPU-oriented schemes and two designed specifically for GPUs, on both the YCSB and TPC-C benchmarks under varied contention levels and GPU configurations. Our findings reveal that GPU-optimized schemes do not consistently outperform CPU-oriented schemes, particularly under specific workloads and contention levels. Moreover, GPU-specific parameters, such as the number of threads per warp and warps per block, significantly impact performance and require careful tuning. Finally, we find that conflict resolution overhead is a crucial factor influencing the performance of CPU-oriented schemes on GPUs, with optimistic concurrency control consistently minimizing this overhead and outperforming other CPU-oriented schemes across all workloads.

Query memory prediction is an essential yet underexplored problem in self-driving databases, particularly for high-concurrency workload scheduling where efficient resource utilization is critical. Existing works mainly focus on cost and latency estimation (e.g., using plan representation learning), while memory prediction poses new challenges such as requiring (1) numerous memory-specific training data, (2) memory-relevant query plan featurization strategies, and (3) a prediction model suitable for capturing the complexities of memory usage in query operations. Moreover, most learning-based approaches do not consider transferability across different datasets and database systems. This paper introduces Mem$Q$, a graph-based memory prediction framework designed for effective workload scheduling. First, we build a comprehensive training dataset for memory prediction by executing diverse query workloads across multiple datasets and recording their diverse peak memory consumptions. Second, our MemQ model leverages operator-level features of query plans, achieving high prediction accuracy, compact model size, and fast training and inference times. Third, we integrate the MemQ model into memory-aware First Fit Decreasing (FFD) and Bidrectional Fit (BF) scheduling strategy to optimize resource utilization. Extensive experiments demonstrate the effectiveness of our homogeneous query plan graph model. Moreover, our FFD scheduling strategy reduces makespan (total query execution time) by up to 55% and decreases retry counts by over 99% compared to default strategies when batch executing analytical queries on PostgreSQL. Furthermore, our novel BF strategy reduces makespan by 15.17% and reduces sum of total time by 41.41% compared with FFD strategy when batch executing mixed workloads.

Deciding query equivalence has played an essential role in many real-world applications, including evaluating the accuracy of text-to-SQL models, where one needs to compare model-generated queries against ground truth queries. Although query equivalence is undecidable in general, researchers have developed two significant approaches to check query equivalence: formal verification-based and test-case-based. Verification-based solutions ensure correctness but may lack support for advanced SQL features and cross-database adaptability. Test cases are versatile but suffer from ad-hoc constraints and potential incorrectness (false positives). In this paper, we propose ParSEval, a Plan-aware SQL Equivalence evaluation framework to generate test database instances for given queries. We observed that existing test data generation methods fail to fully explore the query structure. To address this limitation, ParSEval formally models specific behaviors of each query operator and considers all possible execution paths of the logical query plan by adapting the notion of branch coverage. We validated the effectiveness and efficiency of ParSEval on four datasets with AI-generated and human-crafted queries. The experimental results show that ParSEval supports up to 40% more query pairs than state-of-the-art verification-based approaches. Compared to existing test-case-based approaches, ParSEval reveals more non-equivalent pairs while being 21× faster.

Query rewrite is essential for optimizing SQL queries to improve their execution efficiency without changing their results. Traditionally, this task has been tackled through heuristic and learning-based methods, each with its limitations in terms of inferior quality and low robustness. Recent advancements in LLMs offer a new paradigm by leveraging their superior natural language and code comprehension abilities. Despite their potential, directly applying LLMs like GPT-4 has faced challenges due to problems such as hallucinations, where the model might generate inaccurate or irrelevant results. To address this, we propose R-Bot , an LLM-based query rewrite system with a systematic approach. We first design a multi-source rewrite evidence preparation pipeline to generate query rewrite evidences for guiding LLMs to avoid hallucinations. We then propose a hybrid structure-semantics retrieval method that combines structural and semantic analysis to retrieve the most relevant rewrite evidences for effectively answering an online query. We next propose a step-by-step LLM rewrite method that iteratively leverages the retrieved evidences to select and arrange rewrite rules with self-reflection. We conduct comprehensive experiments on real-world datasets and widely used benchmarks, and demonstrate the superior performance of our system, R-Bot , surpassing state-of-the-art query rewrite methods. The R-Bot system has been deployed at Huawei and with real customers, and the results show that the proposed R-Bot system achieves lower query latency.

Data scientists today often need to analyze data from various places. This makes it necessary for corresponding engines to support query federation (i.e., the ability to perform SQL queries over data hosted in different sources). Although many systems come with federation capabilities, their implementations are tightly coupled with the core engine design. This not only increases complexity and reduces portability across engines, but also often leads to performance issues by missing optimization opportunities. This paper proposes Accio, a new "bolt-on" approach to query federation. Accio is a middleware library that decouples query federation from the target system. It enables two key optimizations—join pushdown and query partitioning—via a declarative interface that can be easily leveraged by different engines. Our experience of adapting five popular data science query engines shows that Accio can outperform existing approaches by orders of magnitude in various scenarios without the need for any intrusive changes or extra maintenance.

Evolutionary multitask optimization (EMTO) has been increasingly employed in addressing high-dimensional feature selection challenges, but current EMTO algorithms still have three deficiencies: First, in task generation, they just consider the linear correlation among features but ignore the nonlinear correlation. Second, they commonly encounter negative knowledge transfer. Third, they are hard to strike an optimal balance between global search capability and computational efficiency. This paper proposes an adaptive aggregative multitask competitive swarm optimization (AAMCSO) for high-dimensional feature selection, which contains three novel and effective strategies to address the above deficiencies. Firstly, AAMCSO proposes a linear-and-nonlinear-correlation-based task generation strategy to generate multiple tasks while considering both linear and nonlinear correlation between features and labels. Secondly, AAMCSO proposes an adaptive aggregative knowledge transfer strategy to adaptively transfer positive knowledge among related tasks. Thirdly, AAMCSO proposes a bi-directional asymmetric flip strategy to guide the population to search for a smaller feature subset with better classification performance. We have conducted extensive comparative experiments on AAMCSO and multiple state-of-the-art feature selection algorithms in high-dimensional feature selection problems with up to 10000 dimensions. The results show that AAMCSO achieves significantly superior performance to the state-of-the-art comparison algorithms in terms of both classification accuracy and feature number.

Site recommendation, which aims at predicting the optimal location for brands to open new branches, has demonstrated an important role in assisting decision-making in modern business. In contrast to traditional recommender systems that can benefit from extensive information, site recommendation starkly suffers from extremely limited information and thus leads to unsatisfactory performance. Therefore, existing site recommendation methods primarily focus on several specific name brands and heavily rely on fine-grained human-crafted features to avoid the data sparsity problem. However, such solutions are not able to fulfill the demand for rapid development in modern business. Therefore, we aim to alleviate the data sparsity problem by effectively utilizing data across multiple cities and thereby propose a novel Optimal Transport enhanced Cross-city (OTC) framework for site recommendation. Specifically, OTC leverages optimal transport (OT) on the learned embeddings of brands and regions separately to project the brands and regions from the source city to the target city. Then, the projected embeddings of brands and regions are utilized to obtain the inference recommendation in the target city. By integrating the original recommendation and the inference recommendations from multiple cities, OTC is able to achieve enhanced recommendation results. The experimental results on the real-world OpenSiteRec dataset, encompassing thousands of brands and regions across four metropolises, demonstrate the effectiveness of our proposed OTC in further improving the performance of site recommendation models.

As a representative information retrieval task, site recommendation, which aims at predicting the optimal sites for a brand or an institution to open new branches in an automatic data-driven way, is beneficial and crucial for brand development in modern business. However, there is no publicly available dataset so far and most existing approaches are limited to an extremely small scope of brands, which seriously hinders the research on site recommendation. Therefore, we collect, construct and release an open comprehensive dataset, namely OpenSiteRec, to facilitate and promote the research on site recommendation. Specifically, OpenSiteRec leverages a heterogeneous graph schema to represent various types of real-world entities and relations in four international metropolises. To evaluate the performance of the existing general methods on the site recommendation task, we conduct benchmarking experiments of several representative recommendation models on OpenSiteRec. Furthermore, we also highlight the potential application directions to demonstrate the wide applicability of OpenSiteRec. We believe that our OpenSiteRec dataset is significant and anticipated to encourage the development of advanced methods for site recommendation. OpenSiteRec is available online at https://OpenSiteRec.github.io/.

Index tuning plays a crucial role in facilitating the efficiency of data retrieval within database systems, which adjusts index settings to optimize the database performance. Recently, with the growth of data volumes, the complexity of workloads, and the diversification of database applications, various Automatic Index Tuning (AIT) methods have been proposed to address these challenges. In this paper, we provide a comprehensive survey on Automatic Index Tuning. First, we overview the AIT techniques from multiple aspects, includingi)problem definition,ii)workflow,iii)framework,iv)index types,v)index interaction,vi)changing factors,vii)automation level, and show the development history. Second, we summarize techniques in the main modules of AIT, includingpreprocessing,index benefit estimation, andindex selection.Preprocessinginvolves workload compression, index candidate generation, feature representation of workloads and databases, and workload reduction.Index benefit estimationapproaches are categorized into empirical methods and machine learning based methods.Index selectioninvolves algorithms of offline AIT and online AIT. Moreover, we summarize the commonly-used datasets in AIT and discuss the applications of index tuning in commercial and opensource database products. Finally, we outline potential future research directions. Our survey aims to enhance both general knowledge and in-depth insights into AIT, and inspire researchers to address the ongoing challenges.

The bursting of media sharing platforms like TikTok, YouTube, and Kwai enables normal users to create and share content with worldwide audiences. The most popular YouTuber can attract up to 100 million followers. Since there are multiple popular platforms, it’s quite common that a YouTuber publishes the same media to multiple platforms, or replicates all media from one platform to another. However, the users of different platforms have different tastes. The media that is popular on one platform may not be a great vogue on other platforms. Observing such cross-platform variance, we propose a new task: estimating the user engagement score of a media on one platform given its popularity on other platforms. This task can benefit both the YouTubers and the platform. On one hand, YouTubers can use the predicted engagement to guide the media reworking; on the other hand, the platform can use the predicted engagement to establish promotion and advertising plans. Therefore, this task is of great practical value. To tackle this task, we propose a disentangled neural network that can separate the general media adorability from platform inclinations. In this manner, by substituting the inclination from the source platform to the target platform, we are able to predict the user engagement in the target platform. To validate the proposed model, we manage to build a dataset of micro-videos which are published on four platforms TikTok, Kwai, Bilibili, and WESEE. The experimental results prove the effectiveness of the proposed model.

Accurate prediction of drug-drug interaction (DDI) is crucial to achieving effective decision-making in medical treatment for both doctors and patients. Recently, many deep learning based methods have been proposed to learn from drug-related features and conduct DDI prediction. These works have achieved promising results. However, the extreme imbalance of medical data poses a serious problem to DDI prediction, where a small fraction of DDI types occupy the majority training data. A straightforward way is to develop an appropriate policy to sample the data. Due to the high complexity and speciality of medical science, a dynamic learnable policy is required instead of a heuristic, uniform or static one. Therefore, we propose a REinforced Student-Teacher curriculum learning model (REST) for effective sampling to tackle this imbalance problem. Specifically, REST consists of two interactive parts, which are a heterogeneous graph neural network as the student and a reinforced sampler as the teacher. In each interaction, the teacher model takes action to sample an appropriate batch to train the student model according to the student model state while the cumulated improvement in performance of the student model is treated as the reward for policy gradient of the teacher model. The experimental results on two benchmarking datasets have demonstrated the significant effectiveness of our proposed model in DDI prediction, especially for the DDI types with low frequency.

The aim of ICD coding is to assign International Classification of Diseases (ICD) codes to unstructured clinical notes or discharge summaries. Numerous methods have been proposed for automatic ICD coding in an effort to reduce human labor and errors. However, existing works disregard the data imbalance problem of clinical notes. In addition, the noisy clinical note issue has not been thoroughly investigated. To address such issues, we propose a knowledge enhanced Graph Attention Network (GAT) under multi-task learning setting. Specifically, multi-level information transitions and interactions have been implemented. On the one hand, a large heterogeneous text graph is constructed to capture both intra- and inter-note correlations between various semantic concepts, thereby alleviating the data imbalance issue. On the other hand, two auxiliary healthcare tasks have been proposed to facilitate the sharing of information across tasks. Moreover, to tackle the issue of noisy clinical notes, we propose to utilize the rich structured knowledge facts and information provided by medical domain knowledge, thereby encouraging the model to focus on the clinical notes' noteworthy portion and valuable information. The experimental results on the widely-used medical dataset, MIMIC-III, demonstrate the advantages of our proposed framework.

Link prediction aims to identify potential missing triples in knowledge graphs. To get better results, some recent studies have introduced multimodal information to link prediction. However, these methods utilize multimodal information separately and neglect the complicated interaction between different modalities. In this paper, we aim at better modeling the inter-modality information and thus introduce a novel Interactive Multimodal Fusion (IMF) model to integrate knowledge from different modalities. To this end, we propose a two-stage multimodal fusion framework to preserve modality-specific knowledge as well as take advantage of the complementarity between different modalities. Instead of directly projecting different modalities into a unified space, our multimodal fusion module limits the representations of different modalities independent while leverages bilinear pooling for fusion and incorporates contrastive learning as additional constraints. Furthermore, the decision fusion module delivers the learned weighted average over the predictions of all modalities to better incorporate the complementarity of different modalities. Our approach has been demonstrated to be effective through empirical evaluations on several real-world datasets. The implementation code is available online at https://github.com/HestiaSky/IMF-Pytorch.

Blockchain has been extensively used on the Internet of Things (IoT). However, several problems exist in current blockchain systems that limit their usability in IoT networks. First, Proof-of-Work (PoW) consensus most used in current blockchain systems generates excessive energy consumption. Second, the single digital token system limits the development of blockchain in multiple IoT applications. Finally, the large amount of data generated by IoT devices and stored in blockchains has huge storage requirements. To deal with these problems, we propose HuaBaseChain—an extensible blockchain with high performance. HuaBaseChain has three features. First, HuaBaseChain uses a novel Proof-of-Participation (PoP) consensus to reduce energy consumption. Second, HuaBaseChain extends the single digital token model to a multidimensional digital token model, enabling more varied applications that can be tailored to the needs of IoT device managers. Third, HuaBaseChain devises an underlying Merkle forest data structure to reduce storage requirements. HuaBaseChain is suited for IoT applications that contain a variety of IoT devices and generate massive amounts of data. We demonstrate the efficiency of HuaBaseChain on IoT data sets and the significantly larger Bitcoin data set. Our experiments show that HuaBaseChain runs efficiently, with significantly reduced energy consumption, greater efficiency, lower storage requirements, and higher query speed.

Structural graph clustering (SCAN) is a classic graph clustering algorithm. In SCAN, a key step is to compute the structural similarity between vertices according to the overlap ratio of one-hop neighborhoods. Given two vertices u and v, existing studies only consider the case when u and v are neighbors. However, the structural similarity between non-neighboring vertices in SCAN is always zero, and using only one-hop neighbors on weighted graphs discards the weights on each edge. Both may not reflect the true closeness of two vertices and may fail to return high-quality clustering results. To tackle this issue, we define and study the distance-based structural graph clustering problem. Given a distance threshold d and two vertices u and v, the structural similarity between u and v is defined as the ratio of their respective neighbors within a distance of no more than d. We show that the newly defined distance-based SCAN achieves better clustering results compared to the vanilla version of SCAN. However, the new definition brings challenges in the computation of final clustering results. To tackle this efficiency issue, we propose DistanceSCAN, an efficient approximate algorithm for solving the distance-based SCAN problem. The main idea of DistanceSCAN is to use all-distances bottom-k sketches (ADS) to speed up the computation of similarities. Given the ADS, we can derive the similarity between two vertices with a bounded cost of O(k). However, to ensure that the estimated similarity has an approximation guarantee, the value of k still needs to be set to as large as thousands. This brings high computational costs when computing the similarities between neighboring vertices. To tackle this issue, we further construct histograms to prune the structural similarity computations of vertices pairs. Extensive experiments on real datasets validate the effectiveness and efficiency of DistanceSCAN.

As a robust similarity measurement, Earth Mover's Distance (EMD) has been widely adopted in many real-world applications, such as machine learning, computer vision and natural language processing. In this paper, we study the problem of EMD-based similarity search, which aims at finding all histogram objects from a dataset whose EMD is within a pre-defined threshold from the given query. Since the time complexity of computing EMD is rather high, it is essential to devise effective techniques to accelerate the query processing. To this end, we propose a filter-and-verification framework: In the filter step, we devise three effective strategies to prune dissimilar objects in batch by sharing the computation between multiple objects. In the verification step, we develop novel flow adjustment techniques to incrementally calculate the EMD of candidates and enable early termination. We justify our proposed framework by conducting both theoretical analysis and extensive experiments. The results on four real world datasets show that our proposed techniques achieve up to an order of magnitude performance gain than state-of-the-art approaches.

Recent studies have shown that strong Natural Language Understanding (NLU) models are prone to relying on annotation biases of the datasets as a shortcut, which goes against the underlying mechanisms of the task of interest. To reduce such biases, several recent works introduce debiasing methods to regularize the training process of targeted NLU models. In this paper, we provide a new perspective with causal inference to find out the bias. On one hand, we show that there is an unobserved confounder for the natural language utterances and their respective classes, leading to spurious correlations from training data. To remove such confounder, the backdoor adjustment with causal intervention is utilized to find the true causal effect, which makes the training process fundamentally different from the traditional likelihood estimation. On the other hand, in inference process, we formulate the bias as the direct causal effect and remove it by pursuing the indirect causal effect with counterfactual reasoning. We conduct experiments on large-scale natural language inference and fact verification benchmarks, evaluating on bias sensitive datasets that are specifically designed to assess the robustness of models against known biases in the training data. Experimental results show that our proposed debiasing framework outperforms previous state-of-the-art debiasing methods while maintaining the original in-distribution performance.

Cross-Domain Recommendation (CDR) has attracted increasing attention in recent years as a solution to the data sparsity issue. The fundamental paradigm of prior efforts is to train a mapping function based on the overlapping users/items and then apply it to the knowledge transfer. However, due to the commercial privacy policy and the sensitivity of user data, it is unrealistic to explicitly share the user mapping relations and behavior data. Therefore, in this paper, we consider a more practical cross-domain scenario, where there is no explicit overlap between the source and target domains in terms of users/items. Since the user sets of both domains are drawn from the entire population, there may be commonalities between their user characteristics, resulting in comparable user preference distributions. Thus, without the mapping relations at user level, it is feasible to model this distribution-level relation to transfer knowledge between domains. To this end, we propose a novel framework that improves the effect of representation learning on the target domain by aligning the representation distributions between the source and target domains. In addition, GWCDR can be easily integrated with existing single-domain collaborative filtering methods to achieve cross-domain recommendation. Extensive experiments on two pairs of public bidirectional datasets demonstrate the effectiveness of our proposed framework in enhancing the recommendation performance.

Measuring Sentence Textual Similarity (STS) is a classic task that can be applied to many downstream NLP applications such as text generation and retrieval. In this paper, we focus on unsupervised STS that works on various domains but only requires minimal data and computational resources. Theoretically, we propose a light-weighted Expectation-Correction (EC) formulation for STS computation. EC formulation unifies unsupervised STS approaches including the cosine similarity of Additively Composed (AC) sentence embeddings, Optimal Transport (OT), and Tree Kernels (TK). Moreover, we propose the Recursive Optimal Transport Similarity (ROTS) algorithm to capture the compositional phrase semantics by composing multiple recursive EC formulations. ROTS finishes in linear time and is faster than its predecessors. ROTS is empirically more effective and scalable than previous approaches. Extensive experiments on 29 STS tasks under various settings show the clear advantage of ROTS over existing approaches. Detailed ablation studies prove the effectiveness of our approaches.

As a robust similarity measurement, Earth Mover's Distance (EMD) has been widely adopted in many real-world applications, such as machine learning, computer vision and natural language processing. In this paper, we study the problem of EMD-based similarity search, which aims at finding all histogram objects from a dataset whose EMD is within a pre-defined threshold from the given query. Since the time complexity of computing EMD is rather high, it is essential to devise effective techniques to accelerate the query processing. To this end, we propose a filter-and-verification framework: In the filter step, we devise effective strategies to prune dissimilar objects in batch by sharing the computation between multiple objects. In the verification step, we develop novel flow adjustment techniques to incrementally calculate the EMD of candidates and enable early termination. We justify our proposed framework by conducting both theoretical analysis and extensive experiments. The results on four real world datasets show that our proposed techniques achieve up to an order of magnitude performance gain than state-of-the-art approaches.

Click-Through Rate (CTR) prediction, estimating the probability of a user clicking on items, plays a key fundamental role in sponsored search. E-commerce platforms display organic search results and advertisements (ads), collectively called items, together as a mixed list. The items displayed around the predicted ad, i.e. external items, may affect the user clicking on the predicted. Previous CTR models assume the user click only relies on the ad itself, which overlooks the effects of external items, referred to as external effects, or externalities. During the advertising prediction, the organic results have been generated by the organic system, while the final displayed ads on multiple ad slots have not been figured out, which leads to two challenges: 1) the predicted (target) ad may win any ad slot, bringing about diverse externalities. 2) external ads are undetermined, resulting in incomplete externalities. Facing the above challenges, inspired by the Transformer, we propose EXternality TRansformer (EXTR) which regards target ad with all slots as query and external items as key&value to model externalities in all exposure situations in parallel. Furthermore, we design a Potential Allocation Generator (PAG) for EXTR, to learn the allocation of potential external ads to complete the externalities. Extensive experimental results on Alibaba datasets demonstrate the effectiveness of externalities in the task of CTR prediction and illustrate that our proposed approach can bring significant profits to the real-world e-commerce platform. EXTR now has been successfully deployed in the online search advertising system in Alibaba, serving the main traffic.

The healthcare industry faces serious problems with health data. Firstly, health data is fragmented and its quality needs to be improved. Data fragmentation means that it is difficult to integrate the patient data stored by multiple health service providers. The quality of these heterogeneous data also needs to be improved for better utilization. Secondly, data sharing among patients, healthcare service providers and medical researchers is inadequate. Thirdly, while sharing health data, patients' right to privacy must be protected, and patients should have authority over who can access their data. In traditional health data sharing system, because of centralized management, data can easily be stolen, manipulated. These systems also ignore patient's authority and privacy. Researchers have proposed some blockchain-based health data sharing solutions where blockchain is used for consensus management. Blockchain enables multiple parties who do not fully trust each other to exchange their data. However, the practice of smart contracts supporting these solutions has not been studied in detail. We propose CrowdMed-II, a health data management framework based on blockchain, which could address the above-mentioned problems of health data. We study the design of major smart contracts in our framework and propose two smart contract structures. We also introduce a novel search contract for searching patients in the framework. We evaluate their efficiency based on the execution costs on Ethereum. Our design improves on those previously proposed, lowering the computational costs of the framework. This allows the framework to operate at scale and is more feasible for widespread adoption.

Among diverse parts in database systems, database prefetching, which aims at predicting future page access patterns and fetching pages to be accessed ahead of time to mitigate blocked I/O operations, plays a crucial role in the overall performance tuning. Existing approaches just use simple heuristic-based methods and suffer from the low hit rate and extra I/O overhead. Recently, with the emerging success of machine learning in different applications, attempts using learning-based models to augment or improve components for database systems have shed some light on this tough problem. Impressed by the enormous potential of machine learning in data management, we present an end-to-end deep learning-based framework to predict page access patterns. We model the prediction of page access as a classification problem and evaluate several variants of neural networks on the accuracy of prediction. On the basis of it, we propose a new Multi-Model framework to construct an accurate model for prefetching. On a suite of real-world database benchmarks, our neural network based prefetching model consistently outperforms existing widely used solutions in real-world database systems.

The number of maximal cliques could be exponentially large with respect to the number of vertices. A clique summary is a subset of all the maximal cliques and can somehow represent all the maximal cliques. Finding such a summary is deemed important in information distribution, influence estimation, cost-effective marketing, etc. The existing approach that finds a maximal clique summary suffers from long running time due to the excessive number of costly bound calculations that are used to estimate the size of to-be-found cliques during the enumeration process. Furthermore, we found that, sometimes, the bound calculation is not necessary at all. As a result, in order to provide the best study of the problem, we propose four strategies in two directions to speed up the process of finding a maximal clique summary by (1) restricting the bound calculation operation to a particular subset of all search branches and (2) making the best use of the bounds that have been previously calculated. Extensive experiments are conducted on eight real-world datasets to validate our strategies. Results demonstrate that the proposed method can reduce the number of bound calculations by 3 ~ 5 orders of magnitude, and each run of our algorithm can be up to 2.x times faster than the state-of-the-art algorithm while still keeping the summary concise. Our method can potentially benefit other large-output enumeration based problems, such as frequent itemset mining, when a summary of results is needed.

Online social networking companies devote much effort to maximize the engagement of users. Most existing methods assume that the budget is already known and focus on heuristic solutions to maximize the number of users that keep engaged. However, many real-life applications aim to keep the engagement of the majority of users in the social network. In such scenarios, the budget is flexible, and the goal is to minimize the budget used to keep these users active. In this paper, we define and study the anchored k-core budget minimization problem. Given an undirected graph G, a degree constraint k and a quota q for engaged users, this problem aims to minimize the budget that assures at least q users not in k-core keeping engaged.We propose CLOCK, an efficient greedy algorithm to solve the anchored k-core budget minimization problem. The main idea is to delete the anchored vertex with the lowest score in every iteration while maintaining the required number of engaged users. By considering the influence among the anchored vertices, a scoring function is well designed to identify the anchored vertices with high quality. Then we propose two merging strategies to get better anchored vertices. In addition, we dynamically maintain all anchored vertices by a local update strategy which avoids many redundant calculations. Finally, we conduct extensive experiments on real world datasets, demonstrating the effectiveness and efficiency of CLOCK.

Index plays an essential role in modern database engines to accelerate the query processing. The new paradigm of "learned index" has significantly changed the way of designing index structures in DBMS. The key insight is that indexes could be regarded as learned models that predict the position of a lookup key in the dataset. While such studies show promising results in both lookup time and index size, they cannot efficiently support update operations. Although recent studies have proposed some preliminary approaches to support update, they are at the cost of scarifying the lookup performance as they suffer from the overheads brought by imprecise predictions in the leaf nodes. In this paper, we propose LIPP, a brand new framework of learned index to address such issues. Similar with state-of-the-art learned index structures, LIPP is able to support all kinds of index operations, namely lookup query, range query, insert, delete, update and bulkload. Meanwhile, we overcome the limitations of previous studies by properly extending the tree structure when dealing with update operations so as to eliminate the deviation of location predicted by the models in the leaf nodes. Moreover, we further propose a dynamic adjustment strategy to ensure that the height of the tree index is tightly bounded and provide comprehensive theoretical analysis to illustrate it. We conduct an extensive set of experiments on several real-life and synthetic datasets. The results demonstrate that our method consistently outperforms state-of-the-art solutions, achieving by up to 4X for a broader class of workloads with different index operations.

Recently unsupervised Bilingual Lexicon Induction(BLI) without any parallel corpus has attracted much research interest.One of the crucial parts in methods for the BLI task is the matching procedure.Previous works impose a too strong constraint on the matching and lead to many counterintuitive translation pairings.Thus, We propose a relaxed matching procedure to find a more precise matching between two languages.We also find that aligning source and target language embedding space bidirectionally will bring significant improvement.We follow the previous iterative framework to conduct experiments.Results on standard benchmark demonstrate the effectiveness of our proposed method, which substantially outperforms previous unsupervised methods.

Computing the distance among linguistic objects is an essential problem in natural language processing. The word mover’s distance (WMD) has been successfully applied to measure the document distance by synthesizing the low-level word similarity with the framework of optimal transport (OT). However, due to the global transportation nature of OT, the WMD may overestimate the semantic dissimilarity when documents contain unequal semantic details. In this paper, we propose to address this overestimation issue with a novel Wasserstein-Fisher-Rao (WFR) document distance grounded on unbalanced optimal transport theory. Compared to the WMD, the WFR document distance provides a trade-off between global transportation and local truncation, which leads to a better similarity measure for unequal semantic details. Moreover, an efficient prune strategy is particularly designed for the WFR document distance to facilitate the top-k queries among a large number of documents. Extensive experimental results show that the WFR document distance achieves higher accuracy that WMD and even its supervised variation s-WMD.

Semi-supervision is a promising paradigm for Bilingual Lexicon Induction (BLI) with limited annotations.However, previous semisupervised methods do not fully utilize the knowledge hidden in annotated and nonannotated data, which hinders further improvement of their performance.In this paper, we propose a new semi-supervised BLI framework to encourage the interaction between the supervised signal and unsupervised alignment.We design two message-passing mechanisms to transfer knowledge between annotated and non-annotated data, named prior optimal transport and bi-directional lexicon update respectively.Then, we perform semi-supervised learning based on a cyclic or a parallel parameter feeding routine to update our models.Our framework is a general framework that can incorporate any supervised and unsupervised BLI methods based on optimal transport.Experimental results on MUSE and VecMap datasets show significant improvement of our models.Ablation study also proves that the two-way interaction between the supervised signal and unsupervised alignment accounts for the gain of the overall performance.Results on distant language pairs further illustrate the advantage and robustness of our proposed method.

Set similarity search is a fundamental operation in a variety of applications [3] , [5] , [2] . There is a long stream of research on the problem of set similarity search. Given a collection of set records, a query and a similarity function, the algorithm will return all the set records that are similarity with the query. There are many metrics to measure the similarity between two sets, such as Overlap, Jaccard, Cosine and Dice. In this paper we use the widely applied Jaccard to quantify the similarity between two sets, but our proposed techniques can be easily extended to other set-based similarity functions. Previous approaches require users to specify a threshold of similarity. However, in many scenarios it is rather difficult to specify such a threshold. For example, when users types some keywords in the search engine, they will pay more attention for the results which rank in the front, say the top five ones. In this case, if we use threshold-based search instead of KNN similarity search, it is difficult to find the results that are more attractive for users.

Next Point-of-Interest (POI) recommendation plays an important role in location-based services. State-of-the-art methods learn the POI-level sequential patterns in the user's check-in sequence but ignore the subsequence patterns that often represent the socio-economic activities or coherence of preference of the users. However, it is challenging to integrate the semantic subsequences due to the difficulty to predefine the granularity of the complex but meaningful subsequences. In this paper, we propose Adaptive Sequence Partitioner with Power-law Attention (ASPPA) to automatically identify each semantic subsequence of POIs and discover their sequential patterns. Our model adopts a state-based stacked recurrent neural network to hierarchically learn the latent structures of the user's check-in sequence. We also design a power-law attention mechanism to integrate the domain knowledge in spatial and temporal contexts. Extensive experiments on two real-world datasets demonstrate the effectiveness of our model.

Health knowledge graph provides an ideal technical means to integrate heterogeneous data resources and enhance knowledge-based services. There are many challenges for the construction of health knowledge graph such as complex concepts and relationships, various medical standards, heterogeneous data structures, poor data quality, highly accurate and interpretable services, etc. In this paper, firstly, we propose Health Knowledge Graph Builder (HKGB), an end-to-end platform which could be used to construct disease-specific and extensible health knowledge graphs from multiple sources. Secondly, we analyze the capabilities and requirements of clinicians, design the tasks to involve the clinicians and implement a clinician-in-the-loop toolset to integrate the clinicians prior knowledge into the construction of health knowledge graphs. Thirdly, we design an extensible mechanism to add new diseases to an existing knowledge graph. Fourthly, we present a quantitative effort estimation algorithm to quantitatively evaluate the effort of clinicians during the construction, and use it to calculate the workloads such as 44.27 person days for knee osteoarthritis domain. Finally, we have developed several knowledge graph based tools to facilitate real applications.

Set similarity search is a fundamental operation in a variety of applications. While many previous studies focus on threshold based set similarity search and join, few efforts have been paid for KNN set similarity search. In this paper, we propose a transformation based framework to solve the problem of KNN set similarity search, which given a collection of set records and a query set, returns k results with the largest similarity to the query. We devise an effective transformation mechanism to transform sets with various lengths to fixed length vectors which can map similar sets closer to each other. Then, we index such vectors with a tiny tree structure. Next, we propose efficient search algorithms and pruning strategies to perform exact KNN set similarity search. We also design an estimation technique by leveraging the data distribution to support approximate KNN search, which can speed up the search while retaining high recall. Experimental results on real world datasets show that our framework significantly outperforms state-of-the-art methods in both memory and disk based settings.

Given two collections of objects, metric similarity join finds all similar pairs of objects according to a particular distance function in metric space. There is an increasing demand to provide a scalable similarity join algorithm which can support efficient query and analytical services in the era of Big Data. In this paper, we propose SMS-Join, a parallel framework to support similarity join in metric space based on the MapReduce paradigm. The overall workflow of SMS-Join is that it first finds some records as pivots in the preprocessing phase and then splits the data into partitions based on them with a map job. Finally the join results are obtained via a reduce job. To ensure load balancing between the partitions, we devise a light-weighted sampling technique to obtain high quality samples while maintaining the high performance. To reduce the partition cost, we develop an iterative partition strategy in the map phase. We implement our framework upon Apache Spark platform and conduct extensive experiments on four real world datasets. The results show that our method significantly outperforms state-of-the-art methods.

Location-aware services have become widely available on a variety of devices. The resulting fusion of spatio-textual data enables the kind of top-k query that takes into account both location proximity and text relevance. Considering both the misspellings in user input and the data quality issues of spatiotextual databases, it is necessary to support error-tolerant spatial keyword search for end-users. Existing studies mainly focused on set-based textual relevance, but they cannot find reasonable results when the input tokens are not exactly matched with those from records in the database. In this paper, we propose a novel framework to solve the problem of top-k location-aware similarity search with fuzzy token matching. We propose a hierarchical index HGR-Tree to capture signatures of both spatial and textual relevance. Based on such an index structure, we devise a best-first search algorithm to preferentially access nodes of HGR-Tree with more similar objects while those with dissimilar ones can be pruned. We further devise an incremental search strategy to reduce the overhead brought by supporting fuzzy token matching. Experimental results on real world POI datasets show that our framework outperforms state-of-the-art methods by one to two orders of magnitude.

Document classification is an essential task in many real world applications. Existing approaches adopt both text semantics and document structure to obtain the document representation. However, these models usually require a large collection of annotated training instances, which are not always feasible, especially in low-resource settings. In this paper, we propose a multi-task learning framework to jointly train multiple related document classification tasks. We devise a hierarchical architecture to make use of the shared knowledge from all tasks to enhance the document representation of each task. We further propose an inter-attention approach to improve the task-specific modeling of documents with global information. Experimental results on 15 public datasets demonstrate the benefits of our proposed model.

OLAP is a core functionality in database systems and the performance is crucial to enable on-time decisions. However, OLAP queries are rather time consuming, especially on large datasets, and traditional exact solutions usually cannot meet the high-performance requirement. Recently, approximate query processing (AQP) has been proposed to enable approximate OLAP. However, existing AQP methods have some limitations. First, they may involve unacceptable errors on skewed data (e.g., long-tail distribution). Second, they require to store large amount of data and have no significant performance improvement. Third, they only support a small subset of SQL aggregation queries. To overcome these limitations, we propose a bounded approximate query processing framework BAQ. Given a predefined error bound and a set of queries, BAQ judiciously selects high-quality samples from the data to generate a unified synopsis offline, and then uses the synopsis to answer online queries. Compared with existing methods, BAQ has the following salient features. (1) BAQ does not need to generate a synopsis for each query while it only generates a unified synopsis, and thus BAQ has much smaller synopsis. (2) BAQ achieves much smaller error than existing studies. Specifically, BAQ can provide deterministic approximate results (i.e., the estimated query results must be within the error bound with 100 percent confidence) for SQL aggregation queries that do not contain selection conditions on numerical columns. For queries with selection conditions on numerical columns, we propose effective grouping-based techniques and the estimated results are also within the error bound in practice. Experimental results on both real and synthetic datasets show that BAQ significantly outperforms state-of-the-art approaches. For example, on a Microsoft production dataset (a real dataset with synthetic queries), BAQ has 10-100× improvement on synopsis size and 10-100× improvement on the error compared with state-of-the-art algorithms.

Electronic Health Records (EHRs) store a large amount of clinical data associated with each patient.Information extraction on unstructured clinical notes in EHRs is important which could contribute to huge improvement in patient health management.Previous studies mainly focused on English corpus.However, at the same time there are very limited research work on Chinese EHRs.Due to the challenges brought by the characteristics of Chinese, it is difficult to apply existing techniques for English on Chinese corpus.In this paper, we propose a deep learning based framework for information extraction from clinical notes in Chinese EHRs.Our framework consists of three components: data preprocessing, feature generation and entity and relation extractor.For clinical entity recognition, we propose a novel Conditional Random Field (CRF) based model and introduce effective features by leveraging the characteristics of Chinese language.For relation extraction, we utilize Convolutional Neural Network (CNN)to obtain high quality entity-relation facts.To the best of our knowledge, this is the first framework to apply deep learning to information extraction from clinical notes in Chinese EHRs.We conduct extensive sets of experiments on real-world datasets from hospital.The experimental results show the effectiveness of our framework, indicating its practical application value.

Recently, ride-sharing services are becoming more popular in commercially application, which have attracted many researchers' attention.The ride-sharing provides significant economic, societal and environmental benefits in a sharing economy, such as reducing pollution, travel costs and traffic congestions.This kind of problem essentially is to maximize the matched ride-sharing pairs, and obviously is an optimization problem.There are lots of platforms for dynamic peer to peer ride-sharing, however, existing researches can be improved better.For example, how to reduce the algorithm computing time, and maximize the matching effectiveness to gain more economic benefits.In this work, we first introduce the problem of ridesharing with time guarantee on road network, and then design a novel heuristic simulated annealing genetic algorithm.In addition, we carefully adjust the parameters with different constraints, and conduct extensive verification experiments with realistic datasets derived from Beijing car services, the results demonstrate the advancement of our methodologies.

The Global Positioning System(GPS) is used to find a specific point on the real earth although GPS positioning technology is becoming more and more mature, GPS always exists with equipment inherent errors or measurement methods errors. so map matching step is a very important preprocessing for lots of applications, such as traffic flow control, taxi mileage calculation, and finding some people. However, many current methods only deal with distance variables and do not handle angle variables between two segments. In this paper, we propose a new road network map matching algorithm, considering not only the distance between two sample points but also taking into account the angle between two candidate segments using the Hidden Markov Model (HMM) which is a popular solution for map matching. Subsequently, to solve the HMM problem, we make use of dynamic programming Viterbi algorithm to find the maximum probability road segments. The experiments are implemented on BEIJING CITY map real dataset and display that our map matching algorithm significantly improve the accuracy compared with ST-Matching global algorithm.

Similarity search is an essential operation in many applications. Given a collection of set records and a query, the exact set similarity search aims at finding all the records that are similar to the query from the collection. Existing methods adopt a filter-and-verify framework, which make use of inverted indexes. However, as the complexity of verification is rather low for setbased similarity metrics, they always fail to make a good tradeoff between filter power and filter cost. In this paper, we proposed an efficient framework for exact set similarity search based on tree index structure. We defined a hash-based ordering to effectively import data into the index structure and then make optimizations to reduce the filter cost. To further improve the filter power, we proposed a dynamic algorithm to partition the dataset into several parts and propose a multiple-index framework. Experimental results on real-world datasets show that our method significantly outperform the state-of-the-art algorithms.

Chinese hacker communities are of interest to cybersecurity researchers and investigators. When examining Chinese hacker communities, researchers and investigators face many challenges, including understanding the Chinese language, detecting variations in topic evolution, and identifying key hackers with their specialty areas. Therefore, we are motivated to develop a framework for analyzing key hackers and emerging threats in Chinese hacker communities. Specifically, we develop a set of topic models for extracting popular topics, tracking topic evolution, and identifying key hackers with their specialty topics. We applied our framework to 19 major Chinese hacker communities. As a result, we identified five major popular topics, including trading, fraud prevention & identification, calling for cooperation, casual chat, and monetizing. Moreover, we found several trends related to new communication channels, new stolen cards of interest, and new operating mechanism. Further, we also found the key hackers in each extracted area. Our work contributes to the cybersecurity literature by providing an advanced and scalable framework for analyzing Chinese hacker communities.

With the rapid growth of online population, China has become the world's largest online market. This also gives rise to the Chinese underground market, which has facilitated many of the cybercrimes in China. Consequently, there is a need for research scrutinizing Chinese underground markets. One major challenge facing cybersecurity researchers is to understand the unfamiliar cybercriminal jargons. To this end, we are motivated to analyze jargons in Chinese underground market. Particularly, we utilize the recent advancements in unsupervised machine learning methods, word embedding and Latent Dirichlet Allocation. We evaluate our work on a research testbed encompassing 29 exclusive underground market QQ groups with 23,000 members. Specifically, we test the ability of the proposed approach to learn semantically similar words of known cybersecurity-related jargons. Results suggest the state-of-the-art unsupervised learning approaches can help better understand cybercriminal language, providing promising insights for future research on Chinese underground markets.

Tourism has become the world's largest economy industry. More and more people share their travelogues on travel websites. Recommender system is an effective tool to provide travel services (e.g., Landscapes selection) for tourists. Many recommender systems are based on travel data that are supplied by travel agencies, and provide travel packages from a fixed package set, which bring two challenges for travel package recommender system. One is how to generate more travel packages. The other is how to measure more fine-grained user similarity. To address these challenges, we develop a package generation and recommendation framework to help travelers select landscapes. Firstly, we propose a Fuzzy Clustering based Package Generation algorithm (FCPG) to generate new travel packages to improve the overall recommendation effectiveness. Then, we develop a Dual Topic Model based Package Recommendation algorithm (DTMPR). It considers two user-related topics (travel seasons and areas), and provides more fine-grained user similarity measure. Experimental results show the superiority of our framework in comparison with the state-of-the-art methods.

Influence maximization modeling and analyzing is an important problem in Online Social Networks (OSNs). Influential nodes provide information on hot topics and forward interesting information, which can yield great influence on other nodes in OSNs. For word-of-mouth viral marketing, it is critical to find influential nodes within budgets. However, finding the optimal solution to maximize the influence spread in a given OSN has been proven to be NP-Hard. The existing algorithms suffer the following three defects: (1) need acquire the topological structure of the network, which is impractical for the continuously changing networks in real life, (2) are easy to get trapped in Rich Club phenomena, (3) can not balance very well between influence spread and running time. To solve this challenging problem, based on the randomly heuristic algorithm and the scale-free property of Complex Networks, we propose RMDN (Random Maximal Degree Neighbor) and its improved version RMDN++. We prove the feasibility and scalability of RMDNs in theory. Five real datasets are used to test the effectiveness and efficiency of RMDNs under two different influence diffusion models. The result shows that our methods have a comparable performance in terms of influence spread as state-of-the-art algorithms, but decrease the time by 1-2 orders of magnitude.

String similarity search is a fundamental operation in data cleaning and integration. It has two variants, threshold-based string similarity search and top-k string similarity search. Existing algorithms are efficient either for the former or the latter; most of them can't support both two variants. To address this limitation, we propose a unified framework. We first recursively partition strings into disjoint segments and build a hierarchical segment tree index (HS-Tree) on top of the segments. Then we utilize the HS-Tree to support similarity search. For threshold-based search, we identify appropriate tree nodes based on the threshold to answer the query and devise an efficient algorithm (HS-Search). For top-k search, we identify promising strings with large possibility to be similar to the query, utilize these strings to estimate an upper bound which is used to prune dissimilar strings, and propose an algorithm (HS-Topk). We also develop effective pruning techniques to further improve the performance. Experimental results on real-world datasets show our method achieves high performance on the two problems and significantly outperforms state-of-the-art algorithms.

With the flourish of Web-based large Online Social Networks (OSNs), people on OSNs can easily yield influence on others.Finding how the influence spreads and maximizing influence spread within OSNs have been extensively studied.State-of-the-art researches suffer two defects: (a) need to acquire the topological structure of the network, which is impractical for the continuously changing networks in real life and thus can not balance very well between influence spread and running time; (b) assign the same cost for every node in OSN which cannot reflect the reality.To solve these problems we firstly propose PageRank Based Cost (PRBC) model to assess the cost of nodes in OSN according to their importance (influence); secondly we present Budgeted Random Maximal Degree Neighbor (BRMDN) algorithm by exploiting the scale free property.Results from extensive experiments show that BRMDN can well balance influence spread and running time.

Big Data boosts the development of data management and analysis in database systems but it also poses a challenge to traditional database. NoSQL databases are provided to deal with the new challenges brought by Big Data because of its high performance, storage, scalability and availability. In NoSQL databases, it is an essential requirement to provide scalable and efficient index services for real-time data analysis. Most existing index solutions focus on improving write throughput, but at the cost of poor read performance. We designed a new plug-in system PuntStore with pLSM (Punt Log Structured Merge Tree) index engine. To improve read performance, Cache Oblivious Look-ahead Array (COLA) is adopted in our design. We also presented a novel compact algorithm in bulk deletion to support migration of data from temporary storage to data warehouse for further analysis.

For the massive remote image file's management, we build the file catalog system of data application based on the part whole ontology of spatial relation. The method is that we analyzed the attributed item of image metadata and calculated the weight for application, then build the catalog concept level relation, calculated the similitude degree of the image attributed item and catalogue node to build the catalog system, stored the file into the corresponding directory of catalog. We design and realize the catalog system, the experiment show that the method of data integration based on the subdivision of part whole ontology is effective for image data's high efficient integrative management.

We propose a dual hash tables algorithm which can realize the durable top-k search. Two hash tables are constructed to keep the core information, such as score and time in the inverted lists. We use the key-value relationships between the two hash tables to calculate the scores which measure the correlations between a keyword and documents, and search the versioned objects that are consistent in the top-k results throughout a given query interval. Finally, we use data from Wikipedia to demonstrate the efficiency and performance of our algorithm.

With the development of cloud computing technologies, big data processing is becoming more and more important. How to mine and analyze massive data is facing a very big challenge. In this paper, we proposed an efficient massive data mining and analysis framework Data Cloud on large clusters. The most important part of Data Cloud is the Rabbit. It is a kind of massive data mining and analysis processing plan framework on the large clusters like the Pig and Hive. We make a detail analysis about the Rabbit plan.

Link prediction is an important problem in social network mining. Traditional neighborhood based methods such as Common neighbors, Jaccard Coefficient and Adamic/Adar are well studied in link prediction. However, the concept of structural holes does not receive significant attention in link prediction. As a preliminary work in studying structural holes, we focus on bipartite social networks, which is a special class of social networks that consists of two distinct roles for the users, and links are between users of different roles. In this study, a few implementations of structural holes are proposed, which are then validated with extended neighborhood based methods on a real dataset derived from IMDb network. The results show that structural holes help in improving accuracies in link prediction.

Primary-backup replication based on shared storage is a classical approach to ensuring high availability and data durability of stock trading systems, but it is difficult to further reduce the system latency due to persistence bottleneck. To solve this problem, a memory data replication approach based on Paxos algorithm is proposed, which accomplishes primary-backup replication through messaging, ensures the strong consistency of data replicas and tolerates possible benign failures. Experiment results have shown that this approach, compared with the shared storage approach, manages to greatly reduce the order processing latency of trading systems and achieve hot failover correctly in the case of server failure.

With the development of IoT technologies, more and more medial sensors have been used to monitor people's health. In this paper, we design a kind of semantic medical monitoring system model in the cloud based on the IoT sensors. Lots of IoT sensors will accept the massive sensor data every time. All these massive sensor data will be stored in the HDFS and some information will be stored into the HUADING-S, a column-based database. All these HUADING-S data will connect to the medical rule engine. When the users' or patients' health indicators' data is beyond the normal range, the medical rule engine will send the alert information to the users or patients. We design two algorithms: (1) massive semantic medical rules processing algorithm without external communication and (2) massive semantic medical rules processing algorithm with external communication. Our simulation experiment shows that the algorithm 2 will reduce the time cost a lot and improve the executive efficiency.

In this paper, we design a kind of big data processing framework SemanMR (Semantic MapReduce). SemanMR is a programming framework based on the Hadoop MapReduce programming model. SemanMR provide a kind of bid data processing mechanism based on the metadata cluster of distributed file systems or cloud databases. In addition, we add some semantic index on the big data, and so it will improve our processing efficiency in SemanMR. SemanMR is a kind of big data processing internetware in the cloud environment.

Massive rules processing has attracted more attention in recently years. Firstly, we propose a rule description language that can express all kind of rules by structured nature language. We design a set of graphical symbols for rule nodes. We also propose a rule traffic flow model and a rule cost model. Thought these models, it is easier to process massive numbers rules and optimize them.

Internet brings more flexibility and possibilities to software. How to develop and maintain the software conveniently and easily is a big challenge for the developers of Internet applications. The purpose of this paper is to create a systemic framework for object oriented design (OOD) and map between the program and the reality. This paper investigates the things, relations and interactions between things, and defines a set of concepts: universal, particular, perspective, perspective transfer, nature, feature, rule and triggering mechanism. These concepts are used to explain the basic structure of the framework. Some important problems in object oriented programming (OOP) and aspect oriented programming (AOP) are investigated in detail. A prototype system has been implemented and tested. The experiments prove that the new thought is realistic and efficient.

In XML databases, materializing queries and their results into views in a semantic cache can improve the performance of query evaluation by reducing computational complexity and I/O cost. Although there are a number of proposals of semantic cache for XML queries, the issues of fast cache lookup and compensation query construction could be further studied. In this paper, based on sequential XPath queries, we propose fastCLU, a fast Cache LookUp algorithm and effiCQ, an efficient Compensation Query constructing algorithm to solve these two problems. Experimental results show that our algorithms outperform previous algorithms and can achieve good performance of query evaluation.

Existing studies for mining frequent XML query patterns mainly introduce a straightforward candidate generate-and-test strategy and compute frequencies of candidate query patterns from scratch periodically by checking the entire transaction database, which consists of XML query patterns transformed from user queries. However, it is nontrivial to maintain such discovered frequent patterns in real XML databases because there may incur frequent updates that may not only invalidate some existing frequent query patterns but also generate some new frequent ones. Accordingly, existing proposals are inefficient for the evolution of the transaction database. To address these problems, this paper presents an efficient algorithm IPS-FXQPMiner for mining frequent XML query patterns without candidate maintenance and costly tree-containment checking. We transform XML queries into sequences through a one- to-one mapping and then mine the frequent sequences to generate frequent XML query patterns. More importantly, based on IPS-FXQPMiner, an efficient incremental algorithm, Incre-FXQPMiner is proposed to incrementally mine frequent XML query patterns, which can minimize the I/O and computation requirements for handling incremental updates. Our experimental study on various real-life datasets demonstrates the efficiency and scalability of our algorithms over previous known alternatives.