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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.