The rapid development and widespread adoption of open source software, facilitated and accelerated by the web, have fostered a vibrant ecosystem for collaborative development and innovation. GitHub, a leading platform for collaborative software development, currently hosts more than 100 million registered users, creating a substantial ecosystem for examining open source community behaviors. Existing tools for measuring open source communities primarily focus on metrics such as issue response time, pull request response time, or incremental stars to provide insights into community activity. However, these tools are limited in their ability to assess the influence of communities from the perspective of collaboration networks. Moreover, current data collection solutions offer fixed functionalities and lack the flexibility to support multi-source, fine-grained, and customizable data acquisition, which is essential for comprehensive analysis of Open Source Ecosystems (OSEs). In this paper, we present OpenDigger, a framework for multi-dimensional assessment of collaboration activities in OSEs. To enable scalable, modular, and continuous acquisition of OSE data, we developed OpenCrawler, a one-line service providing customizable, fine-grained control over data collection. Using the collected data, OpenDigger computes 20 statistical and 2 network-based metrics, and our empirical analysis further verifies their effectiveness in enabling a comprehensive assessment of trends in OSEs. By continuously collecting logs from GitHub and Gitee, OpenDigger has now accumulated over 9 billion records. Our framework has already been deployed across multiple industrial environments, including Alibaba Group, Ant Group, Apache Foundation, and Mulan Open Source Community.

Natural Language Processing (NLP) aims to analyze text or speech via techniques in the computer science field. It serves applications in the domains of healthcare, commerce, education, and so on. Particularly, NLP has been widely applied to the education domain and its applications have enormous potential to help teaching and learning. In this survey, we review recent advances in NLP with a focus on solving problems relevant to the education domain. In detail, we begin with introducing the related background and the real-world scenarios in education to which NLP techniques could contribute. Then, we present a taxonomy of NLP in the education domain and highlight typical NLP applications including question answering, question construction, automated assessment, and error correction. Next, we illustrate the task definition, challenges, and corresponding cutting-edge techniques based on the above taxonomy. In particular, LLM-involved methods are included for discussion due to the wide usage of LLMs in diverse NLP applications. After that, we showcase some off-the-shelf demonstrations in this domain, which are designed for educators or researchers. At last, we conclude with five promising directions for future research, including generalization over subjects and languages, deployed LLM-based systems for education, adaptive learning for teaching and learning, interpretability for education, and ethical consideration of NLP techniques. We organize all relevant datasets and papers in the open-available Github Link for better reviewhttps://github.com/LiXinyuan1015/NLP-for-Education.

Isolation Levels (IL) act as correct contracts between applications and database management systems (DBMSs). The complex code logic and concurrent interactions among transactions make it a hard problem to expose violations of various ILs stated by DBMSs. With the recent proliferation of new DBMSs, especially the cloud ones, there is an urgent demand for a general way to detect bugs violating various ILs. The core challenges come from the requirements of: (a) lightweight (verifying without modifying the application logic in workloads and the source code of DBMSs), (b) generality (verifying various ILs), and (c) efficiency (performing efficient verification on a long running workload). To this end, we propose a powerful and practical bug-finding toolLeopard. For lightweight, we propose to infer transaction dependencies based on the time intervals of operations collected from the client-side, without modifying the source code of DBMSs. For generality, based on a thorough analysis of existing concurrency control protocols, we summarize and abstract four mechanisms which can implement ILs in all commercial DBMSs we have investigated. For efficiency, we design atwo-level pipelineto organize and sort massive time intervals in a time and memory conservative way; we propose amechanism-mirrored verificationto simulate the concurrency control protocols implemented in DBMSs for high throughputs; From experimental results,Leopardoutperforms existing methodsCobraandElle. In practice,Leopardhas a superpower to verify various ILs on any workload running on all commercial DBMSs. Moreover, it has successfully discovered 49 bugs that cannot be found by other existing methods.

Inverted index is a basic tool in many data-intensive applications. Though numerous efforts have been made on efficient inverted index-based query processing, existing schemes do not achieve the expected performance for modern data centers, in which servers are equipped with powerful CPUs and relatively large memory. Through comprehensive measurement studies, we identify the root course is that the data formats for index representation make it unfeasible to design efficient query execution approaches on top of it, which results in poor parallel query support and waste CPU computation. Driven by the findings, we propose to reconcile the in-memory index as columnar structures. To enable this idea, we construct the compact columnar format (i.e., Cocoa) that achieves both desirable space efficiency and maintains the capability for efficient searching support. With Cocoa, we design an efficient query executing scheme that utilizes vectorized batch processing to avoid frequent branch prediction, as well as clause enumeration with pruning to save the overhead of intermediate batch materialization. We build an open-source system VeloSearch to embody our design; experimental results show that VeloSearch achieves ~30× better performance compared with state-of-the-art search libraries such as Lucene and Tantivy.

The advent of the "pre-train, prompt'' paradigm has recently extended its generalization ability and data efficiency to graph representation learning, following its achievements in Natural Language Processing (NLP). Initial graph prompt tuning approaches tailored specialized prompting functions for Graph Neural Network (GNN) models pre-trained with specific strategies, such as edge prediction, thus limiting their applicability. In contrast, another pioneering line of research has explored universal prompting via adding prompts to the input graph's feature space, thereby removing the reliance on specific pre-training strategies. However, the necessity to add feature prompts to all nodes remains an open question. Motivated by findings from prompt tuning research in the NLP domain, which suggest that highly capable pre-trained models need less conditioning signal to achieve desired behaviors, we advocate for strategically incorporating necessary and lightweight feature prompts to certain graph nodes to enhance downstream task performance. This introduces a combinatorial optimization problem, requiring a policy to decide 1) which nodes to prompt and 2) what specific feature prompts to attach. We then address the problem by framing the prompt incorporation process as a sequential decision-making problem and propose our method, RELIEF, which employs Reinforcement Learning (RL) to optimize it. At each step, the RL agent selects a node (discrete action) and determines the prompt content (continuous action), aiming to maximize cumulative performance gain. Extensive experiments on graph and node-level tasks with various pre-training strategies in few-shot scenarios demonstrate that our RELIEF outperforms fine-tuning and other prompt-based approaches in classification performance and data efficiency. The code is available at https://github.com/JasonZhujp/RELIEF.

Abstract Distributed in-memory databases are widely adopted to achieve low latency and high bandwidth for data-intensive applications. They support scale-out by sharding and distributing data across multiple nodes. To efficiently adapt to various workloads, distributed in-memory databases must be capable of migrating shards across nodes. In this paper, we demonstrate that state-of-the-art approaches experience significant performance degradation during migration due to service downtime and redundant data transfer. Furthermore, our findings indicate that the presence of service downtime constrains the scalability of migration strategies, while the transfer of redundant data during the snapshot transfer phase limits their adaptability to dynamic workloads. To this end, this paper proposes Aion, a live migration strategy designed for distributed in-memory databases. Aion eliminates any potential service downtime by immediately switching transaction routing to the destination node. To ensure data consistency between the source and destination nodes, as well as serializable execution during migration, Aion proposes the mutual validation phase. Moreover, Aion introduces an analysis phase before the snapshot transfer phase to identify dynamically changing hotspots in workloads. The analysis phase identifies and transfers tuples and versions accessed less frequently to the destination node, reducing the amount of data transferred. Aion is implemented on a distributed in-memory database and evaluated using various OLTP workloads. The results demonstrate that Aion can fundamentally eliminate service downtime, adapt effectively to various workloads and exhibit robust scalability. Compared to state-of-the-art approaches, Aion achieves up to 2.25x–6.57x higher throughput during migration and shortens the migration duration by 53.7–68.2%.

Modern analytical query engines (AQEs) are essential for large-scale data analysis and processing. These systems usually provide numerous query-level tunable knobs that significantly affect individual query performance. While several studies have explored automatic DBMS configuration tuning, they have several limitations to handle query-level tuning. Firstly, they fail to capture how knobs influence query plans, which directly affect query performance. Secondly, they overlook query failures during the tuning processing, resulting in low tuning efficiency. Thirdly, they struggle with cold-start problems for new queries, leading to prolonged tuning time. To address these challenges, we propose AQETuner, a novel Bayesian Optimization-based system tailored for reliable query-level knob tuning in AQEs. AQETuner first applies the attention mechanisms to jointly encode the knobs and plan query, effectively identifying the impact of knobs on plan nodes. Then, AQETuner employs a dual-task Neural Process to predict both query performance and failures, leveraging their interactions to guide the tuning process. Furthermore, AQETuner utilizes Particle Swarm Optimization to efficiently generate high-quality samples in parallel during the initial tuning stage for the new queries. Experimental results show that AQETuner significantly outperforms existing methods, reducing query latency by up to 23.7% and query failures by up to 51.2%.

Graph Databases (Graph DB) find extensive application across diverse domains such as finance, social networks, and medicine. Yet, the translation of Natural Language (NL) into the Graph Query Language (GQL), referred to as NL2GQL, poses significant challenges owing to its intricate and specialized nature. Some approaches have sought to utilize Large Language Models (LLMs) to address analogous tasks like text2SQL. Nonetheless, in the realm of NL2GQL tasks tailored to a particular domain, the absence of domain-specific NL-GQL data pairs adds complexity to aligning LLMs with the graph DB. To tackle this challenge, we present a well-defined pipeline. Initially, we use ChatGPT to generate NL-GQL data pairs, leveraging the provided graph DB and two mutual verification self-instruct methods which ensure consistency between NL and GQL. Subsequently, we employ the generated data to fine-tune LLMs, ensuring alignment between LLMs and the graph DB. Moreover, we find the importance of relevant schema in efficiently generating accurate GQLs. Thus, we introduce a method to extract relevant schema as the input context. We evaluate our method using two carefully constructed datasets derived from graph DBs in the finance and medicine domains, named FinGQL and MediGQL. Experimental results reveal that our approach significantly outperforms a set of baseline methods, with improvements of 5.90 and 6.36 absolute points on EM, and 6.00 and 7.09 absolute points on EX for FinGQL and MediGQL, respectively

Deep CNNs are increasingly prevalent in various application domains such as image processing. To explain a CNN prediction, it is popular to employ occlusion-based explanations (OBE). OBE helps users understand which parts of an image are important to a CNN prediction. Existing systems have explored incremental evaluation to accelerate CNN inference in OBE. However, they are oblivious that incremental evaluation does not always outperform full evaluation for certain layers. To address this issue, we propose a hybrid evaluation to efficiently interleave full and incremental evaluations during the CNN inference. Ad-ditionally, it employs a cost model to compare the overhead costs of two types of evaluations and a heuristic method to determine the efficient plan combination for common CNNs. More impor-tantly, hybrid evaluation adopts a dynamic programming-based method for attention-based CNNs. In particular, the dynamic programming-based method significantly reduces the overhead of searching for the efficient plan combination on the complex DAG structure. To demonstrate the efficiency of our techniques, we implement HyInJ, a hybrid CNN inf erence system based on PyTorch. Our experiments show that HyInf reduces execution time by up to 22% on GPU and 55% on CPU in comparison to the state-of-the-art incremental evaluation.

Cache replacement policies are essential for maximizing application performance. Policies such as LRFU, which incorporate both recency and frequency, have shown efficacy in improving hit rates in many studies. In this paper, we theoretically investigated how parameters impact hit rates in LRFU and discovered two distinct features named unimodality and correlation. Drawing on our understanding, we formulated Hill-Cache. Hill-Cache provides a holistic approach to cache. It incorporates recency and frequency and employs a hill-climbing algorithm for adaptability. Additionally, it improves churn resistance through quick demotion, the approach that the most recent research suggests. By overcoming the limitations of LRFU, including high maintenance overhead and dependency on parameters, Hill-Cache distinguishes itself as a new cache method. Hill-Cache is well-suited for situations where there is an efficiency gap between performance devices and capacity devices, including data caching applications and database systems. Our evaluations, employing 36 real-world traces and various sophisticated policies across diverse cache sizes, demonstrated the superior performance of Hill-Cache. It reduces the average miss rate by 11.97% compared to LRU and outperforms other advanced cache policies such as ARC, LIRS, DLIRS, CACHEUS, and S3FIFO. We incorporated Hill-Cache into Memcached and RocksDB, significantly improving performance metrics such as throughput and latency.

Self-attention-based vision transformers (ViTs) have emerged as a highly competitive architecture in computer vision. Unlike convo-lutional neural networks (CNNs), ViTs are capable of global information sharing. With the development of various structures of ViTs, ViTs are increasingly advantageous for many vision tasks. However, the quadratic complexity of self-attention renders ViTs computationally intensive, and their lack of inductive biases of locality and translation equivariance demands larger model sizes compared to CNNs to effectively learn visual features. In this paper, we propose a light-weight and efficient vision transformer model called DualToken-ViT that leverages the advantages of CNNs and ViTs. DualToken-ViT effectively fuses the token with local information obtained by convolution-based structure and the token with global information obtained by self-attention-based structure to achieve an efficient attention structure. In addition, we use position-aware global tokens throughout all stages to enrich the global information, which further strengthening the effect of DualToken-ViT. Position-aware global tokens also contain the position information of the image, which makes our model better for vision tasks. We conducted extensive experiments on image classification, object detection and semantic segmentation tasks to demonstrate the effectiveness of DualToken-ViT. On the ImageNet-1K dataset, our models of different scales achieve accuracies of 75.4% and 79.4% with only 0.5G and 1.0G FLOPs, respectively, and our model with 1.0G FLOPs outperforms LightViT-T using global tokens by 0.7%.

In a geo-distributed database, data shards and their respective replicas are deployed in distinct datacenters across multiple regions, enabling regional-level disaster recovery and the ability to serve global users locally. However, transaction processing in geo-distributed databases requires multiple cross-region communications, especially during the commit phase, which can significantly impact system performance. To optimize the performance of geo-distributed transactions, we propose Decentralized Two-phase Commit (D2PC), a new transaction commit protocol aiming to minimize the negative impact of cross-region communication. In D2PC, we employ multiple co-coordinators that perform commit coordination in parallel. Each co-coordinator is responsible for collecting 2PC votes and making a PreCommit decision in its local region. This approach allows for the concurrent invocation of multiple cross-region network round trips, and each region can end its concurrency control locally before replication is complete, thus significantly reducing the chances of blocking and enhancing system concurrency. Moreover, we propose the bypass leader replication reply method, leveraging decentralized co-coordinators to bypass the leader for message transmission, thereby reducing the commit latency. Experimental results have demonstrated that D2PC can reduce commit latency by 43% and improve throughput by up to 2.43 × compared to the geo-distributed transaction processing methods based on 2PC.

Generating synthetic workloads is essential and critical to the performance evaluation of database systems. When benchmarking database performance for a specific application, the similarity between synthetic workloads and real application workloads determines the credibility of the evaluation results. However, it meets a great challenge to catch workload characteristics for a target online transaction processing (OLTP) application considering the complexity of transaction executions. To address this problem, we propose a workload duplicator (Lauca) that can generate synthetic workloads with highly similar performance metrics compared to a specific application on both centralized and distributed databases. By carefully studying the application-driven workload generation problem, we presentTransaction Logic,Data Access DistributionandPartition Access Distributionto characterize runtime workloads and propose novel generation algorithms to guarantee the high fidelity of synthetic workloads. To the best of our knowledge, Lauca is the first application-driven transactional workload generator. We conduct extensive experiments based on TPC-C, SmallBank and YCSB on both centralized and distributed databases. The experimental results show that Lauca consistently generates high-quality synthetic workloads.

Sales forecasting during the launch of new products has always been a challenging task, due to the lack of historical sales data. The dynamic market environment and consumer preferences also increase the uncertainty of predictions. Large chains face even greater difficulties due to their extensive presence across various regions. Traditional time-series forecasting methods usually rely on statistical models and empirical judgments, which are difficult to handle large, variable data and often fail to achieve satisfactory performance for new products. In this paper, we propose a Multi-granularity AdversaRial Learning framework (MARL) to leverage knowledge from old products and improve the quality of invariant representations for more accurate sales predictions. To evaluate our proposed method, we conducted extensive experiments on both a real-world dataset from a prominent international Café chain and a public dataset. The results demonstrated that our method is more effective than the existing state-of-the-art baselines for new product sales forecasting.

In recent years, diffusion models have become the most popular and powerful methods in the field of image synthesis, even rivaling human artists in artistic creativity. However, the key issue currently limiting the application of diffusion models is its extremely slow generation process. Although several methods were proposed to speed up the generation process, there still exists a trade-off between efficiency and quality. In this paper, we first provide a detailed theoretical and empirical analysis of the generation process of the diffusion models based on schedulers. We transform the designing problem of schedulers into the determination of several parameters, and further transform the accelerated generation process into an expansion process of the linear subspace. Based on these analyses, we consequently propose a novel method called Optimal Linear Subspace Search (OLSS), which accelerates the generation process by searching for the optimal approximation process of the complete generation process in the linear subspaces spanned by latent variables. OLSS is able to generate high-quality images with a very small number of steps. To demonstrate the effectiveness of our method, we conduct extensive comparative experiments on open-source diffusion models. Experimental results show that with a given number of steps, OLSS can significantly improve the quality of generated images. Using an NVIDIA A100 GPU, we make it possible to generate a high-quality image by Stable Diffusion within only one second without other optimization techniques.

The log-structured merge tree (LSM-tree) has been widely adopted as a backbone of modern key-value stores. However, the multiple exponentially increased levels of LSM-tree makes it suffer from high write amplification. Existing studies often improve the write performance by sacrificing the read performance, which is inefficient to make trade-offs between the update and search efficiency. In this paper, we exploit nonvolatile memory (NVM) to address the write amplification issue for systems with NVM-SSD hybrid storage, and further propose a reinforcement learning method to navigate between update and search efficiency on the varying workloads. Specifically, we first propose a lightweight hot data identification method to efficiently capture access recency as well as frequency in NVM with relative large capacity. On this basis, we can eliminate different versions of frequently updated data in high-performance NVM without pushing them to SSD. To improve the data access locality and facilitate fine-grained index tuning in each level, we devise a virtual-split method to partition the key space gradually without extra write amplification. Finally, we propose a cost based Q-learning algorithm to adaptively tune the data organizations of each partition according to the changing access patterns. Experimental results show that our approach outperforms existing methods by up to 2.67×.

Isolation Levels (IL) act as correct contracts between applications and database management systems (DBMSs). The complex code logic and concurrent interactions among transactions make it a hard problem to expose violations of various ILs stated by DBMSs. With the recent proliferation of new DBMSs, especially the cloud ones, there is an urgent demand for a general way to verify various ILs. The core challenges come from the requirements of: (a) lightweight (verifying without modifying the application logic in workloads and the source code of DBMSs), (b) generality (verifying various ILs), and (c) efficiency (performing efficient verification on a long running workload). For lightweight, we propose to deduce transaction dependencies based on time intervals of operations collected from client-sides without touching the source code of DBMSs. For generality, based on a thorough analysis of existing concurrency control protocols, we summarize and abstract four mechanisms which can implement ILs in all commercial DBMSs we have investigated. For efficiency, we design a two-level pipeline to organize and sort massive time intervals in a time and memory conservative way; we propose a mechanism-mirrored verification to simulate the concurrency control protocols implemented in DBMSs for high throughputs. Leopard outperforms existing methods by up to 114× in verification time with a relative small memory usage. In practice, Leopard has a superpower to verify various ILs on any workload running on all commercial DBMSs. Moreover, it has successfully discovered 23 bugs that cannot be found by other existing methods.

With the explosive growth of video and text data on the web, text-video retrieval has become a vital task for online video platforms. Recently, text-video retrieval methods based on pre-trained models have attracted a lot of attention. However, existing methods cannot effectively capture the fine-grained information in videos, and typically suffer from the hubness problem where a collection of similar videos are retrieved by a large number of different queries. In this paper, we propose Match4Match, a new text-video retrieval method based on CLIP (Contrastive Language-Image Pretraining) and graph optimization theories. To balance calculation efficiency and model accuracy, Match4Match seamlessly supports three inference modes for different application scenarios. In fast vector retrieval mode, we embed texts and videos in the same space and employ a vector retrieval engine to obtain the top K videos. In fine-grained alignment mode, our method fully utilizes the pre-trained knowledge of the CLIP model to align words with corresponding video frames, and uses the fine-grained information to compute text-video similarity more accurately. In flow-style matching mode, to alleviate the detrimental impact of the hubness problem, we model the retrieval problem as a combinatorial optimization problem and solve it using maximum flow with minimum cost algorithm. To demonstrate the effectiveness of our method, we conduct experiments on five public text-video datasets. The overall performance of our proposed method outperforms state-of-the-art methods. Additionally, we evaluate the computational efficiency of Match4Match. Benefiting from the three flexible inference modes, Match4Match can respond to a large number of query requests with low latency or achieve high recall with acceptable time consumption.

Algorithmic trading is a crucial yet challenging task in the financial domain, where trading decisions are made sequentially from milliseconds to days based on the historical price movements and trading frequency. To model such a sequential decision making process in the dynamic financial markets, Deep Reinforcement Learning (DRL) based methods have been applied and demonstrated their success in finding trading strategies that achieve profitable returns. However, the financial markets are complex imperfect information games with high-level of noise and uncertainties which usually make the exploration policy of DRL less effective. In this paper, we propose an end-to-end DRL method that explores solutions on the whole graph via a probabilistic dynamic programming algorithm. Specifically, we separate the state into environment state and position state, and model the position state transition as a directed acyclic graph. To obtain reliable gradients for model training, we adopt a probabilistic dynamic programming algorithm to explore solutions over the whole graph instead of sampling a path. By avoiding the sampling procedure, we propose an efficient training algorithm and overcome the efficiency problem in most existing DRL methods. Furthermore, our method is compatible with most recurrent neural network architecture, which makes our method easy to implement and very effective in practice. Extensive experiments have been conducted on two real-world stock datasets. Experimental results demonstrate that our method can generate stable trading strategies for both high-frequency and low-frequency trading, significantly outperforming the baseline DRL methods on annualized return and Sharpe ratio.

Storage engines for analytic databases are being developed to be setup with different devices for both cost price and performance considerations. Persistent Memory(PMem), as a novel storage device, also provides a new promising option for the hybrid storage. In this demonstration, we introduce Hockey, an efficient columnar storage engine designed for hybrid PMem-SSD storage. We first go through the design of the system and introduce how the data and meta data are structured and accessed on the PMem. The system's data placement strategy on hybrid storage is then presented. To highlight Hockey's design concerns for the hybrid storage as well as its superior performance, we develop a visual interface to demonstrate the system through three scenarios.

Generating synthetic workloads is essential and critical to performance evaluation of database systems. When evaluating database performance for a specific application, the similarity between synthetic workloads and real application workloads determines the credibility of the evaluation results. However, it meets a great challenge to catch workload characteristics with respect to a target application considering the complexity of transaction executions. To address this problem, we propose a workload duplicator (Lauca) that can generate synthetic workloads with highly similar performance metrics compared to the real workloads of a specific application. By carefully studying the application-oriented workload generation problem, we present Transaction Logic and Data Access Distribution to characterize workloads of online transaction processing (OLTP) applications, and propose novel generation algorithms to guarantee the high fidelity of synthetic workloads. To the best of our knowledge, Lauca is the first application-oriented transactional workload generator. We conduct extensive experiments based on TPCC, SmallBank and YCSB on both centralized and distributed databases. The experimental results show that Lauca consistently generates high quality synthetic workloads.

As matrix computation becomes increasingly prevalent in large-scale data analysis, distributed matrix computation solutions have emerged. These solutions support query interfaces of linear algebra expressions, which often contain redundant subexpressions, i.e., common and loop-constant subexpressions. Hence, existing compilers rewrite queries to eliminate such redundancy. However, due to the large search space, they fail to find all redundant subexpressions, especially for matrix multiplication chains. Furthermore, redundancy elimination may change the original execution order of operators, and have negative impacts. To reduce the large search space and avoid the negative impacts, we propose automatic elimination and adaptive elimination, respectively. In particular, automatic elimination adopts a block-wise search that exploits the properties of matrix computation for speed-up. Adaptive elimination employs a cost model and a dynamic programming-based method to generate efficient plans for redundancy elimination. Finally, we implement ReMac atop SystemDS, eliminating redundancy in distributed matrix computation. In our experiments, ReMac is able to generate efficient execution plans at affordable overhead costs, and outperforms state-of-the-art solutions by an order of magnitude.

Distributed matrix computation solutions support query interfaces of linear algebra expressions, which often contain redundancy, i.e., common and loop-constant subexpressions. However, existing solutions fail to find all redundant subexpressions. Moreover, eliminating the found redundancy leads to new execution order of operators, which may have side effect. To exploit the benefits of redundancy elimination, we propose a new system called ReMac , which performs automatic and adaptive elimination. In particular, automatic elimination adopts a block-wise search that exploits the properties of matrix computation for speed-up. Adaptive elimination employs a cost model and a dynamic programming-based method to generate efficient plans with redundancy elimination. In this demonstration, attendees will have an opportunity to experience the effect that automatic and adaptive elimination have on distributed matrix computation.

Distributed shared memory abstraction can coordinate a cluster of machine nodes to empower performance-critical queries with the scalable memory space and abundant parallelism. But to deploy the query under such an abstraction, the general execution model just makes operators expressed as multiple subtasks and sequentially schedule them in parallel, while neglecting those vital dependencies between subtasks and data. In this paper, we conduct the in-depth researches about the issues (i.e., low CPU Utilization and poor data locality) raised by the ignorance of dependencies, and then propose a dependency-aware query execution model called Jasmine, which can (i) help users explicitly declare the dependencies and (ii) take these declared dependencies into the consideration of execution to address the issues. We invite our audience to use the rich graphical interfaces to interact with Jasmine to explore the dependency-aware query execution on distributed shared memory.

Due to the variability of IT applications, the back-end databases usually run the mixed OLTP workload, which comprises a variety of transactions. Some of these transactions are high-conflict and others are low-conflict. Furthermore, high-conflict transactions may contend on different groups of data stored in the database. Without precise admission control, too many transactions with conflict on the same group of records are simultaneously executed by the OLTP engine, and this will lead to the well-known problem of data-contention thrashing. Under mixed OLTP workloads, conflicting transactions would be blocked for a long time or rolled back finally, and other transactions have not enough opportunity to be processed.To achieve the optimal performance for each kind of transaction, we design a discriminative admission control mechanism for shared-everything database, referred to as DAC. DAC can quickly identify and classify high-conflict transactions according to the set of records they try to access, which is defined as a conflict zone. DAC makes admission control over OLTP transactions with the conflict zone as the granularity. By adaptively adjusting the transaction concurrency level for each zone, transaction blocking and waiting among the same kind of high-conflict transactions can be alleviated. Furthermore, thread resources are released to make the execution of low-conflict transactions less affected. We evaluate DAC using a main-memory database prototype and a classical disk-based database system. Experimental results demonstrate that DAC can help OLTP engine significantly improve the performance under mixed OLTP workloads.

Distributed matrix computation is common in large-scale data processing and machine learning applications. Existing systems that support distributed matrix computation already explore incremental evaluation for iterative-convergent algorithms. However, they are oblivious to the fact that non-zero increments are scattered in different blocks in a distributed environment. Additionally, we observe that incremental evaluation does not always outperform full evaluation. To address these issues, we propose matrix reorganization to optimize the physical layout upon the state-of-art optimized partition schemes, and thereby accelerate the incremental evaluation. More importantly, we propose a hybrid evaluation to efficiently interleave full and incremental evaluation during the iterative process. In particular, it employs a cost model to compare the overhead costs of two types of evaluations and a selective comparison mechanism to reduce the overhead incurred by comparison itself. To demonstrate the efficiency of our techniques, we implement HyMAC, a hybrid matrix computation system based on SystemML. Our experiments show that HyMAC reduces execution time on large datasets by 23% on average in comparison to the state-of-art optimization technique and consequently outperforms SystemML, ScaLAPACK, and SciDB by an order of magnitude.

Sorting plays a fundamental role in computer science. It has far reaching applications in database operations and data science tasks. An important class of sorting keys are strings and among all string sorting methods, radix sort is a simple but effective algorithm. Many works have been studied to accelerate radix string sort. One typical approach is to process multiple characters in each sorting pass. However, this approach incurs the crucial issue of the radix being too large. To address the problem, we introduce a novel multi-character encoding based method that can significantly reduce the radix. This new encoding scheme takes advantage of the sparse alphabet space usage as well as the sparsity of distinguishing prefixes of the inputs which are commonly seen in real-world datasets. Combining the effective encoding scheme with an adaptive sampling process to generate the encoding efficiently, our proposed sorting algorithm essentially blends radix sort with sample sort and achieves substantial improvement over other sorting approaches. The results on both real datasets and synthetic datasets show that our method yields an average 4.85× performance improvement over C++ STL sort[21], 1.47× improvement over the state-of-the-art Radix Sort on strings implementation[19] and 2.55× over the multikey quicksort[6]. Preliminary tests in a multi-core environment also show it is competitive or better than the most recent parallel string sorting algorithm pS5[8] which demonstrates the scalability of our method.

Distributed matrix computation is common in large-scale data processing and machine learning applications. Iterative-convergent algorithms involving matrix computation share a common property: parameters converge non-uniformly. This property can be exploited to avoid redundant computation via incremental evaluation . Unfortunately, existing systems that support distributed matrix computation, like SystemML, do not employ incremental evaluation. Moreover, incremental evaluation does not always outperform classical matrix computation, which we refer to as a full evaluation . To leverage the benefit of increments, we propose a new system called HyMAC , which performs hybrid plans to balance the trade-off between full and incremental evaluation at each iteration. In this demonstration, attendees will have an opportunity to experience the effect that full, incremental, and hybrid plans have on iterative algorithms.

Many institutions are devoted to providing investment advising services to stock investors to help them make sound investment decisions. Industry analysts at these institutions need to analyze huge amounts of financial news documents, and yield investment advising reports to the service subscribers. Automatic document classification is required to organize collected financial news documents into pre-defined fine-grained categories, before the document analysis tasks. It is challenging to implement accurate fine-grained classification over massive financial documents, because documents from close fine-grained categories are highly semantically similar, while existing classification methods may fail to differentiate the subtle differences for documents from close fine-grained categories. In this paper, we implement a document classification framework, named GraphSEAT, to classify financial documents for a leading financial information service provider in China. Specifically, we build a heterogeneous graph to model the global structure of our targeting financial documents, where documents and financial named entities are deemed as nodes, and a document is connected to a contained named entity with an edge, and we then train a graph convolutional network (GCN) with attention mechanisms, to learn an embedding representation containing domain information for a document. We also extract semantic information from a document's word sequence with a neural sequence encoder, and finally form an overall embedding representation for a document and make the prediction, via fusing the two learned representations of the document with attention mechanisms. We perform extensive experiments on our real-world financial news dataset and three public datasets, to evaluate the performance of the document classification framework, and the experimental results demonstrate that GraphSEAT outperforms all compared eight baseline models, especially on our dataset.

The inaccuracy of road intersection in digital road map easily brings serious effects on the mobile navigation and other applications. Massive traveling trajectories of thousands of vehicles enable frequent updating of road intersection topology. In this paper, we first expand the road intersection detection issue into a topology calibration problem for road intersection influence zone. Distinct from the existing road intersection update methods, we not only determine the location and coverage of road intersection, but figure out incorrect or missing turning paths within whole influence zone based on unmatched trajectories as compared to the existing map. The important challenges of calibration issue include that trajectories are mixing with exceptional data, and road intersections are of different sizes and shapes, etc. To address above challenges, we propose a three-phase calibration framework, called CITT. It is composed of trajectory quality improving, core zone detection, and topology calibration within road intersection influence zone. From such components it can automatically obtain high quality topology of road intersection influence zone. Extensive experiments compared with the state-of-the-art methods using trajectory data obtained from Didi Chuxing and Chicago campus shuttles demonstrate that CITT method has strong stability and robustness and significantly outperforms the existing methods.

Optimistic concurrency control (OCC) protocols validate whether a transaction has conflicts with other concurrent transactions after this transaction completes its execution. In this work, we demonstrate that the validation phase has a great influence on the performance of modern in-memory database systems, especially under heterogeneous workloads. The cost of validating operations in a transaction is determined by two main factors. The first factor is the operation type. An OCC protocol would take much less cost on validating a single-record read operation than validating a key-range scan operation. The second factor is the workload type. Existing schemes in OCC variants for validating key-range scan perform differently under various workloads. Although various validation schemes share the same goal of guaranteeing a transaction schedule to be serializable, there are remarkable differences between the costs they introduced. These observations motivate us to design an optimistic concurrency control which can choose a low-cost validation scheme at runtime, referred to as adaptive optimistic concurrency control (AOCC). First, at transaction-level granularity, AOCC can assign a validation method to a transaction according to the features of its operations. Furthermore, for each operation in a transaction, the validation method is selected according to not only the number of accessed records but also the instant characteristics of workloads. Experimental results show that AOCC has good performance and scalability under heterogeneous workloads mixed with point accesses and predicate queries.

This work addresses the need for efficient key-range validation for a composite OLTP and bulk processing workload characterized by modern enterprise applications. In-memory database system (IMDB), mostly adopting the optimistic concurrency control (OCC) mechanism, performs well if the contention of conventional OLTP workloads is low and each transaction only contains point read/write query with primary key. In this work we present the performance problem of IMDBs under mixed OLTP and bulk processing workloads. The reason is that existing OCC protocols take expensive cost to generate a serializable schedule if the OLTP workload contains bulk processing operations with key-range scan. To this end, we develop an efficient and scalable range optimistic concurrency control (ROCC) which uses logical ranges to track the potential conflicting transactions and to reduce the number of transactions to be validated. At the read phase, a transaction keeps a set of predicates to remember the version and precise scope of scanned ranges, which eliminates the cost of maintaining scanned records. Before entering the validation phase, if the transaction intends to update records in the logical range, it needs to register to the corresponding lock-free list implemented by a circular array. Finally, ROCC filters out unrelated transactions and validates the bulk operation at range level. Experimental results show that ROCC has good performance and scalability under heterogeneous workloads mixed with point access and bulk processing.

Membership testing is the problem of testing whether an element is in a set of elements. Performing the test exactly is expensive space-wise, requiring the storage of all elements in a set. In many applications, an approximate testing that can be done quickly using small space is often desired. Bloom filter (BF) was designed and has witnessed great success across numerous application domains. But there is no compact structure that supports set membership testing for temporal queries, e.g., has person A visited a web server between 9:30am and 9:40am? And has the same person visited the web server again between 9:45am and 9:50am? It is possible to support such "temporal membership testing" using a BF, but we will show that this is fairly expensive. To that end, this paper designs persistent bloom filter (PBF), a novel data structure for temporal membership testing with compact space.

A framework of synthetic data generator to generate social media timeline structures is proposed in this paper, which is useful for benchmarking query processing over social media data, and validating hypothesis over users' behavior. It is flexible to generate synthetic data with different distributions. With the help of its asynchronized parallel processing model and delayed update strategy, it is efficient to feed out timeline structure with high throughput. We show in experiments that our method can generate realistic social media timeline structures efficiently.

The demonstration of a benchmark, named as BSMA, for Benchmarking Social Media Analytics, is introduced in this paper. BSMA is designed to benchmark data management systems supporting analytical queries over social media. It is different to existing benchmarks in that: 1) Both real-life data and a synthetic data generator are provided. The real-life dataset contains a social network of 1.6 million users, and all their tweeting and retweeting activities. The data generator can generate both social networks and synthetic timelines that follow data distributions determined by predefined parameters. 2) A set of workloads are provided. The data generator is in responsible for producing updates. A workload generator produces queries based on predefined query templates by generating query arguments online. BSMA workloads cover a large amount of queries with graph operations, temporal queries, hotspot queries, and aggregate queries. Furthermore, the argument generator is capable of sampling data items in the timeline following power-law distribution online. 3) A toolkit is provided to measure and report the performance of systems that implement the benchmark. Furthermore, a prototype system based on dataset and workloads of BSMA is also implemented. The demonstration will include two parts, i.e. the internals of data and workload generator, as well as the performance testing of reference implementations.

Topic detection is an hot research in the area of information retrieval. However, the new environment of Internet, the content of which are usually user-generated, asks for new requirements and brings new challenges. Topic detection has to resolve the problem of its lower quality and large amount of noisy. This paper not only provides a solution for detecting hot topics, but also giving its semantic descriptions as result. Our method integrates two kinds of term features (local features and global features), and use single pass clustering to perform topic detection in a web forum. It's efficient to filter non-topic documents and get readable descriptions of topic in our system. By comparison with baseline and topic model LDA, our method gets better performance and readable result.

Microblogs, a mixture of new media and social networks, is a hotbed of lurking users. It is meaningful to capture profiles for a lurking user in customized applications because a lurking user can receive all messages except for sending few messages in microblogs. However, it is difficult to capture profiles for a lurking user because of lacking its user-generated contents. In this paper, we propose an approach to generate the lurking user's profiles by its followees' activities. In addition, we present a unified social context graph model to represent the lurking user's followees' activities. And the RWR algorithm is used to generate profiles of the lurking user in this graph model. Extensive experiments show that our approach can effectively determine profiles for lurking users.

Estimating the global data distribution in Peer-to-Peer (P2P) networks is an important issue and has yet to be well addressed. It can benefit many P2P applications, such as load balancing analysis, query processing, and data mining. Inspired by the inversion method for random variate generation, in this paper we present a novel model named distribution-free data density estimation for dynamic ring-based P2P networks to achieve high estimation accuracy with low estimation cost regardless of distribution models of the underlying data. It generates random samples for any arbitrary distribution by sampling the global cumulative distribution function and is free from sampling bias. In P2P networks, the key idea for distribution-free estimation is to sample a small subset of peers for estimating the global data distribution over the data domain. Algorithms on computing and sampling the global cumulative distribution function based on which global data distribution is estimated are introduced with detailed theoretical analysis. Our extensive performance study confirms the effectiveness and efficiency of our methods in ring-based P2P networks.

Along with the development of Web 2.0 applications, social media services has attracted many users and become their hands-on toolkits for recording life, sharing ideas, and social networking. Though social media services are essentially web or mobile applications and services, they combine user-generated content and social networks together, so that information can be created, transmitted, transformed, and consumed in the cyberspace. Thus, social media somehow could be regarded as a kind of sensor to the real life of its users. In general, the data from social media is of low quality. Pieces of information in social media are usually short, with informal presentation, and in some specific context that is highly related to the physical world. Therefore, it is challenging to extract semantics from social media data. However, we argue that given sufficient social media data, users' collective behaviors could be sensed, studied, and even predicted in a certain circumstance. Our study is conducted on data from two services, i.e. Twitter, and Sina Weibo, the most popular microblogging services all over the world and in China, respectively. Collective behaviors are actions of a large amount of various people, which are neither conforming nor deviant. Various collective behaviors are studied in the context of social media. Our studies show that there are various information flow patterns in social media, some of which are similar to traditional media such as newspapers, while others are embedded deep in the social network structure. The evolution of hotspots is highly affected by external stimulation, the social network structure, and individual user's activities. Furthermore, social media tends to be immune to some repeated similar external stimulations. Last but not the least, there is considerable difference in users' behavior between Twitter and Sina Weibo.

With the advance of the semantic Web, varying RDF data were increasingly generated, published, queried, and reused via the Web. For example, the DBpedia, a community effort to extract structured data from Wikipedia articles, broke 100 million RDF triples in its latest release. Initiated by Tim Berners-Lee,likewise, the Linking Open Data (LOD) project has published and interlinked many open licence datasets which consisted of over 2 billion RDF triples so far. In this context, fast query response over such large scaled data would be one of the challenges to existing RDF data stores. In this paper, we propose a novel triple indexing scheme to help RDF query engine fast locate the instances within a small scope. By considering the RDF data as a graph, we would partition the graph into multiple subgraph pieces and store them individually, over which a signature tree would be built up to index the URIs. When a query arrives, the signature tree index is used to fast locate the partitions that might include the matches of the query by its constant URIs. Our experiments indicate that the indexing scheme dramatically reduces the query processing time in most cases because many partitions would be early filtered out and the expensive exact matching is only performed over a quite small scope against the original dataset.

We introduce COSTA, for content-based search using term aggregation. Besides advantages shared with other P2P-based information retrieval systems, the system has several characteristics that distinguish itself from other systems: First, an adaptive indexing scheme which can dynamically identify important terms is used. Important terms are indexed in a chord-like ring, while other terms are aggregated in a balanced tree. We argue that this architecture is more flexible and suitable for term indexing than DHT-based methods. Furthermore, this structure allows to eliminate the requirement of maintaining global knowledge, and hence we can avoid the difficulty in maintaining such knowledge. Term aggregation is useful not only for performance enhancement, but also for improving the quality of search, by using of the term statistics information obtained via the aggregation. Traditional IR techniques such as query expansion can be utilized based on the information. Therefore, COSTA finely integrates distributed indexing with information retrieval. Advanced techniques, such as node clustering, caching and workload balance, are employed. We show that more existing optimization techniques can be adopted for further improvement of the system's performance.

Efficiently querying RDF [1] data is being an important factor in applying Semantic Web technologies to real-world applications. In this context, many efforts have been made to store and query RDF data in relational database using particular schemas. In this paper, we propose a new scheme to store, index, and query RDF data in triple stores. Graph feature of RDF data is taken into considerations which might help reduce the join costs on the vertical database structure. We would partition RDF triples into overlapped groups, store them in a triple table with one more column of group identity, and build up a signature tree to index them. Based on this infrastructure, a complex RDF query is decomposed into multiple pieces of sub-queries which could be easily filtered into some RDF groups using signature tree index, and finally is evaluated with a composed and optimized SQL with specific constraints. We compare the performance of our method with prior art on typical queries over a large scaled LUBM and UOBM benchmark data (more than 10 million triples)in [3]. For some extreme cases, they can promote3to4ordersofmagnitude.

In this demonstration, we present a prototype content-based dissemination broker, called Sonnet, which is built upon structured overlay network. It combines approximate filtering of XML packets with routing in the overlay network. Deliberate optimization technologies are implemented. The running and tracing of the system in a real-life application are to be demonstrated.

Aggregate monitoring over data streams is attracting more and more attention in research community due to its broad potential applications. Existing methods suffer two problems, 1) The aggregate functions which could be monitored are restricted to be first-order statistic or monotonic with respect to the window size. 2) Only a limited number of granularity and time scales could be monitored over a stream, thus some interesting patterns might be neglected, and users might be misled by the incomplete changing profile about current data streams. These two impede the development of online mining techniques over data streams, and some kind of breakthrough is urged. In this paper, we employed the powerful tool of fractal analysis to enable the monitoring of both monotonic and non-monotonic aggregates on time-changing data streams. The monotony property of aggregate monitoring is revealed and monotonic search space is built to decrease the time overhead for accessing the synopsis from O(m) to O(logm), where m is the number of windows to be monitored. With the help of a novel inverted histogram, the statistical summary is compressed to be fit in limited main memory, so that high aggregates on windows of any length can be detected accurately and efficiently on-line. Theoretical analysis show the space and time complexity bound of this method are relatively low, while experimental results prove the applicability and efficiency of the proposed algorithm in different application settings.

In this demonstration, we present a prototype system called SIPPER, which is the abbreviation for Selecting Informative Peers in Structured P2P Environment for Content-based Retrieval. SIPPER distinguishes itself from the existing P2P-IR systems by the following two features: First, to improve retrieval efficiency, SIPPER employs a novel peer selection method to direct the query to a small fraction of relevant peers in the network for searching globally relevant documents. Second, to reduce the bandwidth cost of meta data publishing, SIPPER uses a new publishing mechanism, the term-node publishing mechanism, which is different from the traditional term-document model [2].

Clustering is an important task in mining evolving data streams. Beside the limited memory and one-pass constraints, the nature of evolving data streams implies the following requirements for stream clustering: no assumption on the number of clusters, discovery of clusters with arbitrary shape and ability to handle outliers. While a lot of clustering algorithms for data streams have been proposed, they offer no solution to the combination of these requirements. In this paper, we present DenStream, a new approach for discovering clusters in an evolving data stream. The “dense” micro-cluster (named core-micro-cluster) is introduced to summarize the clusters with arbitrary shape, while the potential core-micro-cluster and outlier micro-cluster structures are proposed to maintain and distinguish the potential clusters and outliers. A novel pruning strategy is designed based on these concepts, which guarantees the precision of the weights of the micro-clusters with limited memory. Our performance study over a number of real and synthetic data sets demonstrates the effectiveness and efficiency of our method.

The filtering of XML data is the basis of many complex applications. Lots of algorithms have been proposed to solve this problem. One important challenge is that the number of path queries is huge. It is necessary to take an efficient data structure representing path queries. Another challenge is that these path queries usually vary with time. The maintenance of path queries determines the flexibility and capacity of a filtering system. In this paper, we introduce a novel approximate method for XML data filtering, which uses Bloom filters representing path queries. In this method, millions of path queries can be stored efficiently At the same time, it is easy to deal with the change of these path queries. To improve the filtering performance, we introduce a new data structure, Prefix Filters, to decrease the number of candidate paths. Experiments show that our Bloom filter-based method takes less time to build routing table than automaton-based method. And our method has a good performance with acceptable false positive when filtering XML packets of relatively small depth with millions of path queries.

It is challenge to maintain frequent items over a data stream, with a small bounded memory, in a dynamic environment where both insertion/deletion of items are allowed. In this paper, we propose a new novel algorithm, called hCount, which can handle both insertion and deletion of items with a much less memory space than the best reported algorithm. Our algorithm is also superior in terms of precision, recall and processing time. In addition, our approach does not request the preknowledge on the size of range for a data stream, and can handle range extension dynamically. Given a little modification, algorithm hCount can be improved to hCount*, which even owns significantly better performance than before.

Density estimation is a costly operation for computing distribution information of data sets underlying many important data mining applications, such as clustering and biased sampling. However, traditional density estimation methods are inapplicable for streaming data, which are continuously arriving large volume of data, because of their request for linear storage and square size calculation. The shortcoming limits the application of many existing effective algorithms on data streams, for which the mining problem is an emergency for applications and a challenge for research. In this paper, the problem of computing density functions over data streams is examined. A novel method attacking this shortcoming of existing methods is developed to enable density estimation for large volume of data in linear time, fixed size memory, and without lose of accuracy. The method is based on M-Kernel merging, so that limited kernel functions to be maintained are determined intelligently, The application of the new method on different streaming data models is discussed, and the result of intensive experiments is presented. The analytical and empirical result show that this new density estimation algorithm for data streams can calculate density functions on demand at any time with high accuracy for different streaming data models.