Index recommendation is crucial for optimizing database performance. However, existing heuristic- and learning-based methods often rely on inefficient exhaustive search and estimated costs, leading to low efficiency (due to the vast search space) and unsatisfactory actual latency (due to inaccurate estimations). Inspired by the refinement strategies of experienced DBAs-who efficiently identify and iteratively refine indexes with database feedback-we present LLMIA, an out-of-the-box, tuning-free index advisor leveraging large language models (LLMs) through in-context learning for index recommendation. LLMIA injects database expertise into the LLM using a high-quality demonstration pool and comprehensive workload feature extraction, while iteratively incorporating database feedback to guide the index refinement. This design enables LLMIA to emulate the decision-making process of expert DBAs: efficiently recommending and refining indexes for various workloads within just a few interactions with the DBMS. We validate LLMIA with extensive experiments on five standard OLAP benchmarks (TPC-H with different scales, JOB, TPC-DS, SSB), where it consistently outperforms or matches 12 baselines by producing superior index recommendations with minimal database interactions. Additionally, LLMIA demonstrates robust generalization on two real-world commercial workloads, delivering high-quality recommendations without the need for additional adaptation or retraining, highlighting its out-of-the-box capability.

Efficiently execution of join operations over large-scale distributed data is critical in modern analytical engines, yet costly shuffle operations involving extensive network transfer and remote I/O often hinder performance. Existing data layout techniques struggle with complex multi-table joins due to inflexible distribution key assignments, suboptimal cluster key choices that require significant manual tuning, and weak co-optimization with downstream join strategy selection. This paper introduces PAC-Tree ( P artition- A ligned C o-Join Tree ), a novel query-aware data layout designed to comprehensively address these limitations in an end-to-end manner. PAC-Tree features a two-level hierarchical structure: the upper level replicates fact tables with diverse distribution keys to improve co-location across join patterns, while the lower level applies advanced multidimensional partitioning with predicate-aware splits for fine-grained intra-shard data skipping. Leveraging PAC-Tree’s statistics, we further propose a block-grouping algorithm to construct co-partitions under memory constraints and a PRIM-based reordering policy for multi-table joins, together significantly reducing shuffle overhead. Experiments on a real Spark cluster demonstrate that PAC-Tree reduces query latency by up to 45.7% and improves throughput by up to 2 \(\times\) compared with state-of-the-art layouts, especially for join-heavy workloads.

Database knob tuning is a long-standing challenge in the database community, aimed at enhancing the performance of database management systems (DBMSs) by minimizing latency and maximizing throughput. Manual tuning, which relies heavily on human expertise, is often inefficient and impractical for large-scale or dynamic deployments. Recent work has explored automating this process using machine learning (ML) and large language models (LLMs). However, existing methods typically require hundreds of workload replays or rely on extensive training data, leading to low tuning efficiency or high preparation costs. Moreover, they also risk generating invalid configurations that can degrade performance or even crash the database. To address these limitations, we introduce AgentTune, the first agent-based knob tuning framework powered by LLMs, designed for efficiency, adaptability, and reliability. AgentTune decomposes the tuning process into four specialized agents: Workload Analyzer, Knob Selector, Range Pruner, and Configuration Recommender, each responsible for a distinct subtask. These agents collaborate through structured prompt chaining. AgentTune first analyzes the input workload to identify impactful knobs and reconstructs their valid ranges to reduce the search space. It then employs a tree-based search strategy to efficiently explore the configuration space and identify suitable knob values. We conduct extensive evaluations across diverse workloads (public benchmarks and real-world workloads), metrics (latency and throughput), DBMSs (PostgreSQL, MySQL, and TiDB), hardware environments, and database scales. Experimental results demonstrate that, compared to existing baselines, AgentTune is able to identify superior configurations using significantly fewer workload replays. Furthermore, AgentTune rarely generates invalid configurations during the tuning process, ensuring reliability and suitability for real-world deployments.

Text-to-SQL, the task of translating natural language questions into SQL queries, plays a crucial role in enabling non-experts to interact with databases. While recent advancements in large language models (LLMs) have significantly enhanced text-to-SQL performance, existing approaches face notable limitations in real-world text-to-SQL applications. Prompting-based methods often depend on closed-source LLMs, which are expensive, raise privacy concerns, and lack customization. Fine-tuning-based methods, on the other hand, suffer from poor generalizability due to the limited coverage of publicly available training data. To overcome these challenges, we propose a novel and scalable text-to-SQL data synthesis framework for automatically synthesizing large-scale, high-quality, and diverse datasets without extensive human intervention. Using this framework, we introduce SynSQL-2.5M, the first million-scale text-to-SQL dataset, containing 2.5 million samples spanning over 16,000 synthetic databases. Each sample includes a database, SQL query, natural language question, and chain-of-thought (CoT) solution. Leveraging SynSQL-2.5M, we develop OmniSQL, a powerful open-source text-to-SQL model available in three sizes: 7B, 14B, and 32B. Extensive evaluations across nine datasets demonstrate that OmniSQL achieves state-of-the-art performance, matching or surpassing leading closed-source and open-source LLMs, including GPT-4o and DeepSeek-V3, despite its smaller size. We release all code, datasets, and models to support further research.

Learned indexes, emerging as a promising alternative to traditional indexes like B+Tree, utilize machine learning models to enhance query performance and reduce memory usage. However, the widespread adoption of learned indexes is limited by their expensive training cost and the need for high accuracy of internal models. Although some studies attempt to optimize the building process of these learned indexes, existing methods are restrictive in scope and applicability. They are usually tailored to specific index types and heavily rely on pre-trained model knowledge, making deployment a challenging task. In this work, we introduce the Learned Index Optimization Framework (LIOF), a general and easily integrated solution aimed at expediting the training process and improving the accuracy of index model for one-dimensional and multi-dimensional learned indexes. The optimization of LIOF for the learned indexes is intuitive, directly providing optimized parameters for index models based on the distribution of node data. By leveraging the correlation between key distribution and node model parameters, LIOF significantly reduces the training epochs required for each node model. Initially, we introduce an optimization strategy inspired by optimization-based meta-learning to train the LIOF to generate optimized initial parameters for index node models. Subsequently, we present a data-driven encoder and a parameter-centric decoder network, which adaptively translate key distribution into a latent variable representation and decode it into optimized node model initialization. Additionally, to further utilize characteristics of key distribution, we propose a monotonic regularizer and focal loss, guiding LIOF training towards efficiency and precision. Through extensive experimentation on real-world and synthetic datasets, we demonstrate that LIOF provides substantial enhancements in both training efficiency and the predictive accuracy for learned indexes.

Vertical partitioning is a crucial physical design strategy in databases that enhances data management and retrieval through optimal data placement. However, current research often overlooks the use of query predicates for effective data block allocation, resulting in potential performance bottlenecks. Moreover, selecting an appropriate partitioning technique based solely on historical experimental results from research articles is challenging due to variability in storage devices, evaluation metrics, and database schemas. We propose PARS to address these issues by offering end-to-end input/output, customizable database configurations, and prioritized optimization objectives to aid database administrators (DBAs) in making informed partitioning decisions. Additionally, PARS introduces a novel algorithm that leverages both numeric and non-numeric query predicates to partition the tablespace into finer data blocks, reducing query latency by 36.1% when benchmarked against the state-of-the-art (SOTA) method.

Open-world semi-supervised learning (Open-world SSL) for node classification, that classifies unlabeled nodes into seen classes or multiple novel classes, is a practical but under-explored problem in the graph community. As only seen classes have human labels, they are usually better learned than novel classes, and thus exhibit smaller intra-class variances within the embedding space (named as imbalance of intra-class variances between seen and novel classes). Based on empirical and theoretical analysis, we find the variance imbalance can negatively impact the model performance. Pre-trained feature encoders can alleviate this issue via producing compact representations for novel classes. However, creating general pre-trained encoders for various types of graph data has been proven to be challenging. As such, there is a demand for an effective method that does not rely on pre-trained graph encoders. In this paper, we propose an IMbalance-A ware method named OpenIMA for Open-world semi-supervised node classification, which trains the node classification model from scratch via contrastive learning with bias-reduced pseudo labels. Extensive experiments on seven popular graph benchmarks demonstrate the effectiveness of OpenIMA, and the source code has been available on GitHub11https://github.com/RUCKBReasoning/OpenIMA.

Various works have utilized deep learning to address the query optimization problem in database system. They either learn to construct plans from scratch in a bottom-up manner or steer the plan generation behavior of traditional optimizer using hints. While these methods have achieved some success, they face challenges in either low training efficiency or limited plan search space. To address these challenges, we introduce FOSS, a novel framework for query optimization based on deep reinforcement learning. FOSS initiates optimization from the original plan generated by a traditional optimizer and incrementally refines suboptimal nodes of the plan through a sequence of actions. Additionally, we devise an asymmetric advantage model to evaluate the advantage between two plans. We integrate it with a traditional optimizer to form a simulated environment. Leveraging this simulated environment, FOSS can bootstrap itself to rapidly generate a large amount of high-quality simulated experiences. FOSS then learns from these experiences to improve its optimization capability. We evaluate the performance of FOSS on Join Order Benchmark, TPC-DS, and Stack Overflow. The experimental results demonstrate that FOSS outperforms the state-of-the-art methods in terms of latency performance. Compared to PostgreSQL, FOSS achieves speedup ranging from 1.15x to 8.33x in total latency across different benchmarks.

Language models have shown promising performance on the task of translating natural language questions into SQL queries (Text-to-SQL). However, most of the state-of-the-art (SOTA) approaches rely on powerful yet closed-source large language models (LLMs), such as ChatGPT and GPT-4, which may have the limitations of unclear model architectures, data privacy risks, and expensive inference overheads. To address the limitations, we introduce CodeS, a series of pre-trained language models with parameters ranging from 1B to 15B, specifically designed for the text-to-SQL task. CodeS is a fully open-source language model, which achieves superior accuracy with much smaller parameter sizes. This paper studies the research challenges in building CodeS. To enhance the SQL generation abilities of CodeS, we adopt an incremental pre-training approach using a specifically curated SQL-centric corpus. Based on this, we address the challenges of schema linking and rapid domain adaptation through strategic prompt construction and a bi-directional data augmentation technique. We conduct comprehensive evaluations on multiple datasets, including the widely used Spider benchmark, the newly released BIRD benchmark, robustness-diagnostic benchmarks such as Spider-DK, Spider-Syn, Spider-Realistic, and Dr.Spider, as well as two real-world datasets created for financial and academic applications. The experimental results show that our CodeS achieves new SOTA accuracy and robustness on nearly all challenging text-to-SQL benchmarks.

Triangle count estimation is a fundamental task in federated graph analysis. Yet, directly collecting local counts from users exposes individuals to severe privacy risks, as the local reports may reveal sensitive social connections. Protecting edge privacy in triangle count estimation is extremely challenging due to the strong data correlation among distinct users and large data sensitivity. Though many efforts have been put into addressing this issue, the existing works fail to provide a stringent privacy guarantee as well as a promising data utility. Motivated by this, we first propose an enhanced privacy notion namely Edge Relationship Local Differential Privacy (Edge-RLDP) that formally considers data correlations and provides a stringent privacy guarantee by hiding multiple edges in the global graph. Based on Edge-RLDP, we further propose a PRIvacy-preserved federated Estimator for Triangle count (PRIVET) with three perturbation algorithms, which enhances the estimation accuracy by designing specialized noise calibration schemes and leveraging a triangle-subsample trick. Theoretically, we prove that PRIVET achieves (ε δ)-Edge-RLDP. Empirically, we verify that PRIVET provides promising estimation accuracy in terms of mean relative error.

As the location-based applications ourishing, we will witness soon the transferring of a prodigious amount of data from the local to a public cloud. The rising demand for outsourced data is moving toward a wider geographical area with arbitrary distribution (i.e., dense or sparse) and query scope (i.e., limited or vast). In terms of cloud risks, the outsourced individual data should be preserved when being queried, especially for location information. Geometric range queries are one of the most fundamental search functions. However, the existed works of secure geometric queries are far from practical usage on efciency and security simultaneously. In this paper, we propose a novel scheme, LuxGeo. Our scheme reaches a constant navigation and a linear sweep, which is tailored for secure and efcient location-lookup. Our experiments over three real-world spatial datasets have shown its practical efciency. For example, it only takes 10.01s with 728 tuples retrieved over 63, 369 ciphertext dataset for a single query. LuxGeo has better performance than the existed solutions for a GSE problem on efciency and security.

The accuracy of selectivity estimation is of vital importance to create good query plans. Traditional estimators such as histograms make several assumptions during estimation that can lead to huge errors. Recently the database community started exploring the usage of machine learning in selectivity estimation and won great achievements. However, due to the black box models they used, existing learning-based methods still face several new challenges, including high estimation latency, large training data demanding, and occurrence of illogical results. In this work, we propose a learning-based MOnotonic Selectivity Estimator (MOSE) to address these challenges. We first learn a multi-dimensional cumulative distribution function of the data in a supervised method and then compute selectivity for ad hoc query predicates at rum-time. We propose a novel regularizer and an effective attribute-aware calibration method to improve the estimation accuracy. To further improve the model efficiency, we design a mutual information based model ensemble method. With regard to the heavy cost of training data collection, we design a model-based active learning strategy to generate high-quality training data cost-effectively. We conduct extensive experiments on both real-world and synthetic datasets and the results show that MOSE outperforms the state-of-the-art methods in terms of accuracy and efficiency.

Phrase mining is an essential step when transforming unstructured text into structured information, in which the aim is to extract high-quality phrases from given corpora automatically. Existing statistics-based methods have achieved state-of-the-art performance on this task. However, such methods often rely heavily on statistical signals to extract quality phrases, ignoring the effect of contextual information. In this paper, we propose a novel context-aware method, called ConPhrase, for quality phrase mining under distantly supervised settings. Specifically, ConPhrase formulates phrase mining as a sequence labeling problem by considering local contextual information, and also incorporates distant supervision methods to automatically generate labeled data. It comprises two modules designed to tackle global information scarcity and noisy data filtration: 1) a topic-aware phrase recognition network that incorporates domain-related topic information into word representation learning to identify quality phrases effectively; 2) an instance selection network that focuses on choosing correct sentences with reinforcement learning for improving the prediction performance of the phrase recognition network. Moreover, we also propose an extended variant of ConPhrase, called ConPhrase+, that further enhances phrase recognition by utilizing document-level contextual information across sentences within the entire document. Experimental results show that contextual information is indispensable for phrase mining and our context-aware methods perform significantly better than state-of-the-art approaches on three publicly available datasets.

The cold-start issue is a fundamental challenge in Recommender Systems. The recent self-supervised learning (SSL) on Graph Neural Networks (GNNs) model, PT-GNN, pre-trains the GNN model to reconstruct the cold-start embeddings and has shown great potential for cold-start recommendation. However, due to the over-smoothing problem, PT-GNN can only capture up to 3-order relation, which cannot provide much useful auxiliary information to depict the target cold-start user or item. Besides, the embedding reconstruction task only considers the intra-correlations within the subgraph of users and items, while ignoring the inter-correlations across different subgraphs. To solve the above challenges, we propose a multi-strategy-based pre-training method for cold-start recommendation (MPT), which extends PT-GNN from the perspective of model architecture and pretext tasks to improve the cold-start recommendation performance. 1 Specifically, in terms of the model architecture, in addition to the short-range dependencies of users and items captured by the GNN encoder, we introduce a Transformer encoder to capture long-range dependencies. In terms of the pretext task, in addition to considering the intra-correlations of users and items by the embedding reconstruction task, we add an embedding contrastive learning task to capture inter-correlations of users and items. We train the GNN and Transformer encoders on these pretext tasks under the meta-learning setting to simulate the real cold-start scenario, making the model able to be easily and rapidly adapted to new cold-start users and items. Experiments on three public recommendation datasets show the superiority of the proposed MPT model against the vanilla GNN models, the pre-training GNN model on user/item embedding inference, and the recommendation task.

Counting subgraphs in decentralized settings has drawn increasing attention for graph analysis, wherein triangle count is one of the fundamental statistics. However, triangle counts may breach edge privacy, such as sensitive relations of individuals. Protecting edge privacy in triangle counts collection is a challenging problem due to the strong correlations among data from different clients. Decentralized Differential Privacy (DDP), as a possible option, protects edge privacy on correlated data to some extent. However, DDP provides a weak privacy guarantee by only hiding one edge in global. Unlike DDP, Local Differential Privacy (LDP) is a widely adopted standard for data collection which hides multiple data points in global at a time. But the LDP notion does not consider data correlations. With the understanding of these limitations, we introduce Edge Relationship Local Differential Privacy (Edge-RLDP), which provides a strong privacy guarantee as LDP and considers data correlations simultaneously. Based on Edge-RLDP, a baseline framework for triangle counts collection is proposed, as well as an improved two-phase framework, which strikes a better balance between privacy and data utility. Our improved framework fully utilizes the privacy budget by asking each client to only report the count of randomly sampled triangles after measuring the global data correlation. Theoretically, we rigorously prove that our framework satisfies ($\varepsilon, \delta$) -Edge-RLDP. Experimentally, we demonstrate our framework outperforms the state-of-art methods in terms of triangle count accuracy under a stricter privacy definition.

The accuracy of selectivity estimation is of vital importance to create good query plans in database management systems. We propose MOSE, a learning-based MOnotonic Selectivity Estimator, to provide accurate, reliable, and efficient selectivity estimation for query optimization.

Query optimization is crucial for the query performance of database systems. Despite decades of efforts from both research and industrial communities, query optimization remains one of the most challenging problems. Thanks to the advances in artificial intelligence, data-driven and learning-based techniques are seeing traction in database research recently. However, most former learning-based works perform less practical because they are evasive about the interaction between learning components and database systems.

We study the problem of supervised contrastive (SupCon) learning on graphs. The SupCon loss has been recently proposed for classification tasks by pulling data points in the same class closer than those of different classes. However, it could be difficult for SupCon to handle datasets with large intra-class variances and high inter-class similarities. This issue is also challenging when it couples with graph structures. To address this, we present the cluster-aware supervised contrastive learning loss (ClusterSCL1) for graph learning tasks. The main idea of ClusterSCL is to retain the structural and attribute properties of a graph in the form of nodes’ cluster distributions during supervised contrastive learning. Specifically, ClusterSCL introduces the strategy of cluster-aware data augmentation and integrates it with the SupCon loss. Extensive experiments on several widely adopted graph benchmarks demonstrate the superiority of ClusterSCL over the cross-entropy, SupCon, and other graph contrastive objectives.

As an important branch in Recommender System, occasional group recommendation has received more and more attention. In this scenario, each occasional group (cold-start group) has no or few historical interacted items. As each occasional group has extremely sparse interactions with items, traditional group recommendation methods can not learn high-quality group representations. The recent proposed Graph Neural Networks (GNNs), which incorporate the high-order neighbors of the target occasional group, can alleviate the above problem in some extent. However, these GNNs still can not explicitly strengthen the embedding quality of the high-order neighbors with few interactions. Motivated by the self-supervised learning technique, which is able to find the correlations within the data itself, we propose a self-supervised graph learning framework, which takes the user/item/group embedding reconstruction as the pretext task to enhance the embeddings of the cold-start users/items/groups. To explicitly enhance the high-order cold-start neighbors' embedding quality, we further introduce an embedding enhancer, which leverages the self-attention mechanism to improve the embedding quality for them. Comprehensive experiments show the advantages of our proposed framework than the state-of-the-art methods.

Name disambiguation is a key and also a very tough problem in many online systems such as social search and academic search. Despite considerable research, a critical issue that has not been systematically studied isdisambiguation on the fly— to complete the disambiguation in the real-time. This is very challenging, as the disambiguation algorithm must be accurate, efficient, and error tolerance. In this paper, we propose a novel framework — CONNA — to train a matching component and a decision component jointly via reinforcement learning. The matching component is responsible for finding the top matched candidate for the given paper, and the decision component is responsible for deciding on assigning the top matched person or creating a new person. The two components are intertwined and can be bootstrapped via jointly training. Empirically, we evaluate CONNA on two name disambiguation datasets. Experimental results show that the proposed framework can achieve a 1.21-19.84 percent improvement on F1-score using joint training of the matching and the decision components. The proposed CONNA has been successfully deployed on AMiner — a large online academic search system.

Deep Convolutional Neural Networks (CNNs) are increasingly used in multimedia retrieval, and accelerating Deep CNNs has recently received an ever-increasing research focus. Among various approaches proposed in the literature, filter pruning has been regarded as a promising solution, which is due to its advantage in significant speedup and memory reduction of both network model and intermediate feature maps. Many works have been proposed to find unimportant filters, and then prune it for accelerating Deep CNNs. However, they mainly focus on using heuristic methods to evaluate the importance of filters, such as the statistical information of filters (e.g., prune filter with small $\ell_2$-norm), which may be not perfect. In this paper, we propose a novel filter pruning method, namely A Unified-Model via Block Coordinate Descent for Learning the Importance of Filter (U-BCD). The importance of the filters in our U-BCD is learned by optimizing method. We can simultaneously learn the filter parameters and the importance of filters by block coordinate descent method. When applied to two image classification benchmarks, the effectiveness of our U-BCD is validated. Notably, on CIFAR-10, our U-BCD reduces more than 57% FLOPs on ResNet-110 with even 0.08% relative accuracy improvement, and also achieve state-of-the-art results on ILSVRC-2012.

GNN-based anomaly detection has recently attracted considerable attention. Existing attempts have thus far focused on jointly learning the node representations and the classifier for detecting the anomalies. Inspired by the recent advances of self-supervised learning (SSL) on graphs, we explore another possibility of decoupling the node representation learning and the classification for anomaly detection. We conduct a preliminary study to show that decoupled training using existing graph SSL schemes to represent nodes can obtain performance gains over joint training, but it may deteriorate when the behavior patterns and the label semantics become highly inconsistent. To be less biased by the inconsistency, we propose a simple yet effective graph SSL scheme, called Deep Cluster Infomax (DCI) for node representation learning, which captures the intrinsic graph properties in more concentrated feature spaces by clustering the entire graph into multiple parts. We conduct extensive experiments on four real-world datasets for anomaly detection. The results demonstrate that decoupled training equipped with a proper SSL scheme can outperform joint training in AUC. Compared with existing graph SSL schemes, DCI can help decoupled training gain more improvements.

Cold-start problem is a fundamental challenge for recommendation tasks. Despite the recent advances on Graph Neural Networks (GNNs) incorporate the high-order collaborative signal to alleviate the problem, the embeddings of the cold-start users and items aren't explicitly optimized, and the cold-start neighbors are not dealt with during the graph convolution in GNNs. This paper proposes to pre-train a GNN model before applying it for recommendation. Unlike the goal of recommendation, the pre-training GNN simulates the cold-start scenarios from the users/items with sufficient interactions and takes the embedding reconstruction as the pretext task, such that it can directly improve the embedding quality and can be easily adapted to the new cold-start users/items. To further reduce the impact from the cold-start neighbors, we incorporate a self-attention-based meta aggregator to enhance the aggregation ability of each graph convolution step, and an adaptive neighbor sampler to select the effective neighbors according to the feedbacks from the pre-training GNN model. Experiments on three public recommendation datasets show the superiority of our pre-training GNN model against the original GNN models on user/item embedding inference and the recommendation task.

Accelerating Deep Convolutional Neural Networks(CNNs) has recently received ever-increasing research focus. Among various approaches proposed in the literature, filter pruning has been regarded as a promising solution, which is due to its advantage in significant speedup and memory reduction of both network model and intermediate feature maps. Previous works utilized "smaller-norm-less-important" criterion to prune filters with smaller lp-norm values by pruning and retraining alternately. However, they ignore the effects of $feedback: most current approaches that prune filters only consider the statistics of the filters (e.g., prune filter with small lp-norm values), without considering the performance of the pruned model as an important feedback signal in the next iteration of filter pruning. To solve the problem of non-feedback, we propose a novel filter pruning method, namely Filter Pruning via Probabilistic Model-based Optimization (FPPMO). FPPMO solves the problem of non-feedback by pruning filters in a probabilistic manner. We introduce a pruning probability for each filter, and pruning is guided by sampling from the pruning probability distribution. An optimization method is proposed to update the pruning probability based on the performance of the pruned model in the pruning process. When applied to two image classification benchmarks, the effectiveness of our FPPMO is validated. Notably, on CIFAR-10, our FPPMO reduces more than 57% FLOPs on ResNet-110 with even 0.08% relative accuracy improvement. Moreover, on ILSVRC-2012, our FPPMO reduces more than 50% FLOPs on ResNet-101 without top-5 accuracy drop. Which proving that our FPPMO outperforms the state-of-the-art filter pruning method.

Group k-nearest neighbor (kGNN) search allows a group of n mobile users to jointly retrieve k points from a location-based service provider (LSP) that minimizes the aggregate distance to them. We identify four protection objectives in the privacy preserving kGNN search: (i) every user's location should be protected from LSP; (ii) the group's query and the query answer should be protected from LSP; (iii) LSP's private database information should be protected from users; (iv) every user's location should be protected from other users in the group. We design two privacy preserving solutions under two types of threat model to the privacy preserving kGNN search in the full user collusion environment, where any n - 1 users in the group may collude to infer the location of the remaining user. Our solutions do not rely on heavy pre-computation on LSP like previous works. Though we consider kGNN, the proposed privacy preserving solutions can be easily adopted to any group query as it treats the query answering (i.e., kGNN) as a black box. Theoretical and experimental analysis suggest that our solutions are highly efficient in both communication cost and user computational cost while incurring some reasonable overhead on LSP.

Accelerating Deep Convolutional Neural Networks (CNNs) has recently received ever-increasing research focus. Among various approaches proposed in the literature, filter pruning has been regarded as a promising solution, which is due to its advantage in significant speedup and memory reduction of both network model and intermediate feature maps. Previous works utilized "smaller-norm-less-important" criterion to prune filters with smaller ࡁp-norm values by pruning and retraining alternately. This trends to narrow the model capacity for the following reasons: (1) Violent pruning. Previous works adopt a violent strategy in which all filters are simultaneously pruned, which leaving the room to retain model accuracy limited. (2) Filter degradation. Previous works simply set the pruned filter to 0 and retrained it alterately, which easily led to the loss of learning ability of filters. To solve this problem, we propose a novel filter pruning method, namely Incremental Filter Pruning via Random Walk (IFPRW). IFPRW solves the problem of violent pruning by incremental method and Filter degradation by means of random walk. When applied to two image classification benchmarks, the usefulness and strength of IFPRW is validated. Notably, on CIFAR-10, IFPRW reduces more than 46% FLOPs on ResNet-110 with even 0.28% relative accuracy improvement. Moreover, on ILSVRC-2012, IFPRW reduces more than 54% FLOPs on ResNet-101 with only 0.7% top-5 accurcacy drop. which proving that IFPRW outperforms the state-of-the-art filter pruning methods.

We propose a ranking framework, called PatternRank+NN, for expanding a set of seed entities of a particular class (i.e., entity set expansion) from Web search queries. PatternRank+NN consists of two parts: PatternRank and NN. Unlike the traditional methods, PatternRank brings user behaviors into entity set expansion from Web search queries. PatternRank is a Markov chain which simulates the Web search query process of users on the graph model for Web search query log, and ranks the features of the class. The features in the front rank are used to generate candidate entities of the class. NN, a ranking strategy called Nearest Neighbor, ranks these candidate entities such that the set of seed entities can be expanded from the candidate entities in the front rank. Our experiments demonstrate the superior performance of PatternRank+NN in comparison with the state-of-the-art methods.

Data release, such as statistics of data distribution, in many data analysis and machine learning tasks is needed, which poses significant risks of user's privacy. Usually, to preserve privacy of every individual, frequency estimation based on LDP (Local Differential Privacy) is used to replace the real distribution of data. Unfortunately, when an individual sends values multiple times, privacy leakage, i.e., same value problems may occur, along with other performance problems such as memory usage problem. To narrow these gaps, SAnonLDP (Sample Anonymous Local Differential Privacy) is proposed in this paper. We build the SAnonLDP framework by integrating k-anonymous into LDP, which includes four blocks: random grouping; anonymous and Walsh-Fourier transforms; random response; singular value decomposition (SVD). Among them, the second block 'Anonymous and Walsh-Fourier transforms' significantly decreases the communication cost and the memory requirements. The left blocks make up for the loss of information to achieve an acceptable frequency estimation. More important, we verify that this estimation is unbiased by the strict mathematical reasoning. Finally, the numerical experiments demonstrate that SAnonLAP achieves better KL-divergence and estimation error compared to another known privacy model: RAPPOR.

Aligning users across multiple heterogeneous social networks is a fundamental issue in many data mining applications. Methods that incorporate user attributes and network structure have received much attention. However, most of them suffer from error propagation or the noise from diverse neighbors in the network. To effectively model the influence from neighbors, we propose a graph neural network to directly represent the ego networks of two users to be aligned into an embedding, based on which we predict the alignment label. Three major mechanisms in the model are designed to unitedly represent different attributes, distinguish different neighbors and capture the structure information of the ego networks respectively.

Context plays an important role in helping users to make decisions. There are hierarchical structure between contexts and aggregation characteristics within the context in real scenarios. Exist works mainly focus on exploring the explicit hierarchy between contexts, while ignoring the aggregation characteristics within the context. In this work, we explore both of them so as to improve accuracy of prediction in recommender systems. We propose a Random Partition Factorization Machines (RPFM) by adopting random decision trees to split the contexts hierarchically to better capture the local complex interplay. The intuition here is that local homogeneous contexts tend to generate similar ratings. During prediction, our method goes through from the root to the leaves and borrows from predictions at higher level when there is sparseness at lower level. Other than estimation accuracy of ratings, RPFM also reduces the over-fitting by building an ensemble model on multiple decision trees. We test RPFM over three different benchmark contextual datasets. Experimental results demonstrate that RPFM outperforms state-of-the-art context-aware recommendation methods.

It is popular for most people to read news online since the web sites can provide access to news articles from millions of sources around the world. For these news web sites, the key challenge is to help users find related news articles to read. In this paper, we present a system called CROWN (Context-aware RecOmmender for Web News) to do Chinese news recommendation. By recommendation, the system can retrieve personalized fresh and relevant news articles to mobile users according to their particular context. Differing from existing mobile news applications which employ rather simple strategies for news recommendation, CROWN integrates the contextual information in prediction by modeling the data as a tensor. Such context information usually includes the time, the location, etc. This demo paper presents the implementation of the whole procedure of news recommendation in the system of CROWN. Experimental results on a large corpus of newly-published Chinese web news show its performance is satisfactory.

Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes and to do similarity search in a graph. For example, in social networks such as Facebook, system may want to recommend potential friends to a particular user based on connections between users. In custom-product networks such as eBay, one may wish to recommend products to others based on purchases history. In this talk, I will introduce some methods on vertex similarities computations and their applications on similarity search in real world networks.

We study the problem of question topic classification using a very large real‐worldCommunityQuestionAnswering (CQA) dataset fromYahoo!Answers. The dataset comprises 3.9 million questions and these questions are organized into more than 1,000 categories in a hierarchy. To the best knowledge, this is the first systematic evaluation of the performance of different classification methods on question topic classification as well as short texts. Specifically, we empirically evaluate the following in classifying questions intoCQAcategories: (a) the usefulness of n‐gram features and bag‐of‐word features; (b) the performance of three standard classification algorithms (naive Bayes, maximum entropy, and support vector machines); (c) the performance of the state‐of‐the‐art hierarchical classification algorithms; (d) the effect of training data size on performance; and (e) the effectiveness of the different components ofCQAdata, including subject, content, asker, and the best answer. The experimental results show what aspects are important for question topic classification in terms of both effectiveness and efficiency. We believe that the experimental findings from this study will be useful in real‐world classification problems.

Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes in a graph. SimRank is a simple and influential measure of this kind, based on a solid graph theoretical model. However, existing methods on SimRank computation suffer from two limitations: 1) the computing cost can be very high in practice; and 2) they can only be applied on static graphs. In this paper, we exploit the inherent parallelism and high memory bandwidth of graphics processing units (GPU) to accelerate the computation of SimRank on large graphs. Furthermore, based on the observation that SimRank is essentially a first-order Markov Chain, we propose to utilize the iterative aggregation techniques for uncoupling Markov chains to compute SimRank scores in parallel for large graphs. The iterative aggregation method can be applied on dynamic graphs. Moreover, it can handle not only the link-updating problem but also the node-updating problem. We give the corresponding theoretical justification and analysis, propose three optimization strategies to further improve the computation efficiency, and extend the proposed algorithm to dynamic graphs. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.

Information networks are ubiquitous in many applications and analysis on such networks has attracted significant attention in the academic communities. One of the most important aspects of information network analysis is to measure similarity between nodes in a network. SimRank is a simple and influential measure of this kind, based on a solid theoretical "random surfer" model. Existing work computes SimRank similarity scores in an iterative mode. We argue that the iterative method can be infeasible and inefficient when, as in many real-world scenarios, the networks change dynamically and frequently. We envision non-iterative method to bridge the gap. It allows users not only to update the similarity scores incrementally, but also to derive similarity scores for an arbitrary subset of nodes. To enable the non-iterative computation, we propose to rewrite the SimRank equation into a non-iterative form by using the Kronecker product and vectorization operators. Based on this, we develop a family of novel approximate SimRank computation algorithms for static and dynamic information networks, and give their corresponding theoretical justification and analysis. The non-iterative method supports efficient processing of various node analysis including similarity tracking and centrality tracking on evolving information networks. The effectiveness and efficiency of our proposed methods are evaluated on synthetic and real data sets.

This paper addresses a fundamental and challenging problem with broad applications: efficient processing of region-based promotion queries, i.e., to discover the top-k most interesting regions for effective promotion of an object (e.g., a product or a person) given by user, where a region is defined over continuous ranged dimensions. In our problem context, the object can be promoted in a region when it is top-ranked in it. Such type of promotion queries involves an exponentially large search space and expensive aggregation operations. For efficient query processing, we study a fresh, principled framework called region-based promotion cube (RepCube). Grounded on a solid cost analysis, we first develop a partial materialization strategy to yield the provably maximum online pruning power given a storage budget. Then, cell relaxation is performed to further reduce the storage space while ensuring the effectiveness of pruning using a given bound. Extensive experiments conducted on large data sets show that our proposed method is highly practical, and its efficiency is one to two orders of magnitude higher than baseline solutions.

Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes in a graph. SimRank is a simple and influential measure of this kind, based on a solid graph theoretical model. However, existing methods on SimRank computation suffer from two limitations: 1) the computing cost can be very high in practice; and 2) they can only be applied on static graphs. In this paper, we exploit the inherent parallelism and high memory bandwidth of graphics processing units (GPU) to accelerate the computation of SimRank on large graphs. Furthermore, based on the observation that SimRank is essentially a first-order Markov Chain, we propose to utilize the iterative aggregation techniques for uncoupling Markov chains to compute SimRank scores in parallel for large graphs. The iterative aggregation method can be applied on dynamic graphs. Moreover, it can handle not only the link-updating problem but also the node-updating problem. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.

The concept of dominance has recently attracted much interest in the context of skyline computation. Given an N-dimensional data set S, a point p is said to dominate q if p is better than q in at least one dimension and equal to or better than it in the remaining dimensions. In this paper, we propose extending the concept of dominance for business analysis from a microeconomic perspective. More specifically, we propose a new form of analysis, called Dominant Relationship Analysis (DRA), which aims to provide insight into the dominant relationships between products and potential buyers. By analyzing such relationships, companies can position their products more effectively while remaining profitable.To support DRA, we propose a novel data cube called DADA (Data Cube for Dominant Relationship Analysis), which captures the dominant relationships between products and customers. Three types of queries called Dominant Relationship Queries (DRQs) are consequently proposed for analysis purposes: 1)Linear Optimization Queries (LOQ), 2)Subspace Analysis Queries (SAQ), and 3)Comparative Dominant Queries (CDQ). Algorithms are designed for efficient computation of DADA and answering the DRQs using DADA. Results of our comprehensive experiments show the effectiveness and efficiency of DADA and its associated query processing strategies.

Data cube pre-computation is an important concept for supporting OLAP(Online Analytical Processing) and has been studied extensively. It is often not feasible to compute a complete data cube due to the huge storage requirement. Recently proposed quotient cube addressed this issue through a partitioning method that groups cube cells into equivalence partitions. Such an approach is not only useful for distributive aggregate functions such as SUM but can also be applied to the holistic aggregate functions like MEDIAN.Maintaining a data cube for holistic aggregation is a hard problem since its difficulty lies in the fact that history tuple values must be kept in order to compute the new aggregate when tuples are inserted or deleted. The quotient cube makes the problem harder since we also need to maintain the equivalence classes. In this paper, we introduce two techniques called addset data structure and sliding window to deal with this problem. We develop efficient algorithms for maintaining a quotient cube with holistic aggregation functions that takes up reasonably small storage space. Performance study shows that our algorithms are effective, efficient and scalable over large databases.