Learnable sparse retrieval (LSR) models encode texts into high-dimensional sparse representations, supporting token-level expansion beyond the original text and addressing the vocabulary mismatch problem in traditional bag-of-words retrieval. However, in the absence of representation-level supervision, these representations usually overemphasize irrelevant tokens while neglecting truly relevant ones. We term this phenomenon the Representation Hallucination problem in LSR models, a critical bottleneck impeding accurate retrieval. To address this challenge, we introduce SiRe, a self-improving training framework for sparse retrieval that integrates two core strategies: Heuristic Representation Refinement and Representation-Focused Learning. Specifically, SiRe first identifies and corrects representation hallucinations in the outputs of the current LSR model using heuristic methods. The resulting representations serve as the primary supervision signals, guiding a pretrained language model (e.g., BERT) to mitigate the problem directly at the representation level. This process can be iterated, enabling progressive model improvement. Extensive experiments on both in-domain and out-domain benchmarks show that SiRe produces higher-quality sparse representations, significantly enhancing retrieval performance over strong baselines.

Event linking aims to associate event mentions in text with their corresponding entries in a knowledge base (KB). This task can help text understanding to benefit downstream tasks (e.g., question answering) and expand the KB through new event knowledge mentioned in the text. Existing event linking approaches usually adopt a retrieve-and-rank framework, which suffers from high computational costs and relies on hand-crafted rules, thereby limiting generalization. Additionally, it is found that some entity linking methods can be used to solve this task directly. However, they also perform not well. In this paper, we propose SEFEL, an end-to-end, argument-aware event representation-based event linking framework to unify the modeling of both in-KB and out-of-KB scenarios. To further enhance the linking performance, we propose a contrastive learning module to refine the learned embeddings of events and event mentions. Experimental results demonstrate that SEFEL improves accuracy by at least 3.59 (in-KB) and 21.5 (out-of-KB) compared with baselines, while its inference speed is more than 38 times faster than baselines, showcasing its accuracy and efficiency.

Knowledge Bases (KBs) play a key role in various applications.As two representative KB-related tasks, knowledge base completion (KBC) and knowledge base question answering (KBQA) are closely related and inherently complementary with each other.Thus, it will be beneficial to solve the task of joint KBC and KBQA to make them reinforce each other.However, existing studies usually rely on the small language model (SLM) to enhance them jointly, and the large language model (LLM)'s strong reasoning ability is ignored.In this paper, by combining the strengths of the LLM with the SLM, we propose a novel framework JCQL, which can make these two tasks enhance each other in an iterative manner.To make KBC enhance KBQA, we augment the LLM agent-based KBQA model's reasoning paths by incorporating an SLM-trained KBC model as an action of the agent, alleviating the LLM's hallucination and high computational costs issue in KBQA.To make KBQA enhance KBC, we incrementally fine-tune the KBC model by leveraging KBQA's reasoning paths as its supplementary training data, improving the ability of the SLM in KBC.Extensive experiments over two public benchmark data sets demonstrate that JCQL surpasses all baselines for both KBC and KBQA tasks.

The global shortage and uneven distribution of medical expertise continue to hinder equitable access to accurate diagnostic care. While existing intelligent diagnostic system have shown promise, most struggle with dual-user interaction, and dynamic knowledge integration—limiting their real-world applicability. In this study, we present DiagLink, a dual-user diagnostic assistance system that synergizes large language models (LLMs), knowledge graphs (KGs), and medical experts to support both patients and physicians. DiagLink uses guided dialogues to elicit patient histories, leverages LLMs and KGs for collaborative reasoning, and incorporates physician oversight for continuous knowledge validation and evolution. The system provides a role-adaptive interface, dynamically visualized history, and unified multi-source evidence to improve both trust and usability. We evaluate DiagLink through user study, use cases and expert interviews, demonstrating its effectiveness in improving user satisfaction and diagnostic efficiency, while offering insights for the design of future AI-assisted diagnostic systems.

The Viterbi algorithm is a key operator for structured sequence inference in modern data systems, with applications in trajectory analysis, online recommendation, and speech recognition. As these workloads increasingly migrate to resource-constrained edge platforms, standard Viterbi decoding remains memory-intensive and computationally inflexible. Existing methods typically trade decoding time for space efficiency, but often incur significant runtime overhead and lack adaptability to various system constraints. This paper presents FLASH Viterbi, a Fast, Lightweight, Adaptive, and Hardware-Friendly Viterbi decoding operator that enhances adaptability and resource efficiency. FLASH Viterbi combines a non-recursive divide-and-conquer strategy with pruning and parallelization techniques to enhance both time and memory efficiency, making it well-suited for resource-constrained data systems. To further decouple space complexity from the hidden state space size, we present FLASH-BS Viterbi, a dynamic beam search variant built on a memory-efficient data structure. Both proposed algorithms exhibit strong adaptivity to diverse deployment scenarios by dynamically tuning internal parameters. To ensure practical deployment on edge devices, we also develop FPGA-based hardware accelerators for both algorithms, demonstrating high throughput and low resource usage. Extensive experiments show that our algorithms consistently outperform existing baselines in both decoding time and memory efficiency, while preserving adaptability and hardware-friendly characteristics essential for modern data systems. All codes are publicly available at https://github.com/Dzh-16/FLASH-Viterbi.

Abstract Opinion maximization has attracted much attention in viral marketing. It selects an initial seed user set to disseminate user opinions on the target product and finally produces more positive opinions in social networks. In earlier studies, a critical but not studied problem is the fairness of information dissemination in groups with sensitive characteristic (such as age or race). People prefer to promote products for target users (majority groups) rather than in sensitive characteristic groups (minority groups). That leads to the differences in information dissemination between minority groups. In addition, social networks have the in-depth structural information. Therefore, in this paper, we design opinion maximization based on fairness framework (OMBF) using graph attention networks (GAT) to exploit more network information, and only consider the fairness in minority groups. OMBF composes of three parts: (1) the determination of candidate nodes according to node representations, (2) the dynamic changes in opinions, (3) the selection of final seed nodes. Firstly, we utilize GAT to obtain node representations and to determinate candidate nodes and design a node opinion formation model to model the dynamic changes in opinions. Then, we use the fair constraint value to ensure the fairness in the information dissemination process of minority groups. Based on above, final seed nodes are selected. We conduct experiments on synthetic and real-world datasets to show the effectiveness of our approach. The results indicate that the total opinions of active nodes in all nodes and fair values in minority groups are better than the chosen state-of-the-art benchmarks.

Untargeted poisoning membership inference (PMI) attacks are a newly emerging privacy threat that evaluates the impact of poisoned samples on the privacy leakage risk in the model's training dataset. Existing approaches typically select target samples randomly from a candidate dataset to generate poisoned samples, which are then injected into the training dataset. While effective in amplifying privacy leakage risks, this random selection strategy overlooks the fact that each poisoned sample contributes unequally to the attack. In this paper, we first observe that randomly selected target samples may be distant from and dispersed relative to high-confidence benign samples, which restricts the effectiveness of membership inference attacks. We then show that selecting target samples with high confidence in their ground-truth class to generate poisoned samples contributes more significantly to the attack. Therefore, we propose a novel untargeted PMI attack incorporating the target sample selection and enhancement. Specifically, we train shadow models to select the highest-confidence target samples for poison generation. To further enhance the effectiveness of the attack, we introduce a noise generator that adds adversarial perturbations to the selected target samples. Experimental results demonstrate that our approach significantly improves the attack success rate (e.g.,$85.6\%$compared to the baseline of$71.9\%$). Notably, the ablation study shows that our noise generator enhances privacy leakage risks even when target samples are selected randomly, highlighting its effectiveness and broad applicability.

The corpus of knowledge that we have amassed is often fragmented in nature. That is, we only possess a mere fraction of understanding regarding various objects and lack a holistic view of the interconnections between them. Graph, a widely used model to represent data and relationships between data, encompasses significant amounts of fragmented knowledge. In this paper, we study fragmented graph pattern matching ($\mathsf {FPM}$for short) on large graphs, a typical problem of fragmented knowledge management. Given several query graphs,$\mathsf {FPM}$searches for matches whose subgraphs are isomorphic to the given query graphs and these subgraphs are connected in a specified way.$\mathsf {FPM}$plays a crucial role in detecting financial crime, identifying abnormal behavior and mining latent knowledge. We propose an algorithm$\mathsf {FraMatch}$, which adopts a traversal-based manner to adaptively identify matches for the given query graphs and enumerates the interconnections among these matches. To improve the efficiency of$\mathsf {FraMatch}$, an index, represented as a$k$-partite graph, is constructed to help organize the candidate matches. Additionally, several methods, including four filtering strategies, parallel optimization and a dynamic loading strategy, are proposed to further accelerate the algorithm and reduce memory usage. We conducted extensive experiments on 4 real graphs to validate$\mathsf {FraMatch}$. The results demonstrate that$\mathsf {FraMatch}$outperforms its comparisons 2000× in running time and reduces memory usage by 8% on average. A real application on anti-money laundering further verifies the effectiveness of$\mathsf {FPM}$. To the best of our knowledge, this is the first study on$\mathsf {FPM}$on large graphs.

The advent of Single Instruction Multiple Data (SIMD) instructions in modern processors has revolutionized data processing by enabling simultaneous computation across multiple data elements. While database systems have extensively adopted SIMD for traditional operations, its potential for complex event pattern matching remains largely unexplored. This paper presents a novel approach that bridges this gap through bit-parallel processing enhanced with AVX-512 vectorization. Our approach encodes event streams into compact bit sequences, where each bit corresponds to a time slice, and an event's presence is marked by a 1-bit when its timestamp falls within the respective slice. This representation enables the formulation of bit-parallel operations that natively enforce complex event constraints, including temporal window requirements and event ordering relationships. We develop a family of bit-parallel algorithms that leverage this representation for continuous event matching, and further optimize their performance through SIMD vectorization (AVX-512 instructions) to exploit modern hardware parallelism. Experimental evaluations on both real-world and synthetic datasets demonstrate the superiority of our method, achieving at least 35.7x improvement in query efficiency compared to state-of-the-art alternatives.

With the rapid advancement of large language models (LLMs) in both academia and industry, their growing size and complexity have introduced significant challenges in terms of computational cost and deployment efficiency. To address these issues, a wide range of inference optimization techniques-including but not limited to model compression-have been proposed to accelerate LLM inference while preserving model performance. This survey provides a comprehensive overview of LLM inference acceleration strategies, analyzing them from multiple perspectives, including foundational principles, algorithmic techniques, real-world applications, and open research challenges. We begin by introducing core concepts underlying inference optimization and propose a new taxonomy that categorizes existing approaches, including quantization, pruning, distillation, efficient architectures, compilation, and hardware-aware methods. Following the lifecycle of LLM development and deployment, we examine how these techniques interact with model training, fine-tuning, and serving. Furthermore, we highlight key applications of efficient LLMs and discuss emerging trends and unresolved issues in the field. By synthesizing recent advances, this survey aims to provide actionable insights and practical guidance for researchers and practitioners working with scalable and efficient LLM systems.

Recommendations usually focus on immediate accuracy metrics like Click-Through Rate (CTR), ignoring user long-term metrics. User retention, which reflects the percentage of today’s users who will return to the system in the next few days, should be paid more attention to. However, most existing methods did not focus on user retention, since their complexity and uncertainty make it extremely hard to discover why a user will or will not return to a system. Recently, a few pioneers have optimized user retention, focusing solely on accuracy without delving into its underlying rationale. This is primarily due to the absence of explicit supervised signals. In this work, we design a Behavior-wise Contrastive Multi-Instance Learning (BCMIL) module, which jointly models clicked and impressed items to capture interpretable user retention. Specifically, we conduct in-depth analyses in real-world scenarios to discover implicit retention-related supervised signals. To model these signals, we design a Forward Supervised Signals Extractor (FSSE) that utilizes a heterogeneous graph, enhancing the reliability of user retention. To mitigate randomness and uncertainty, we propose a Backward Supervised Signals Stabilizer (BSSS) that utilizes overlooked label-part behaviors within each training window to retrospectively guide the training process. Offline and online evaluations of an industrial system verify the effectiveness of our methods.

Heterogeneous behavioral data provides comprehensive insights into user intentions and decision-making patterns. Contemporary multi-behavior recommendation models, which leverage such data to infer user preferences, typically capture high-order collaborative signals through graph neural networks on a multi-behavior heterogeneous graph or multiple behavior-specific subgraphs. However, auxiliary behaviors (e.g., view, cart) inherently contain noise that can mislead target behavior (e.g., purchase) prediction, and the incorporation of high-order collaborative signals further amplify such noise. Moreover, these approaches fail to adequately explore cross-behavior item dependencies, leading to inadequate modeling of dependencies across heterogeneous behaviors. To address these limitations, we propose Cross-behavior Item DEpendency modeling for multi-behavior Recommendation (CIDER) , a novel framework that explicitly models item dependencies across multiple types of behaviors for target behavior prediction (e.g., purchase). Specifically, our framework introduces the Hierarchical Behavior Sequence (HBS) , a data structure to systematically organize multi-behavior user–item interactions. Based on the HBS, we design a Cross-behavior Item Dependency Modeling (CIDM) module coupled with a multi-behavior cascading learning scheme to capture item-level dependencies. To enhance the robustness of the representations learned from the CIDM module, we develop an HBS-based denoising module that filters out noise inherent in auxiliary behaviors. Empirical evaluation on three benchmark datasets demonstrates the effectiveness of our model in harnessing multi-behavior data. The implementation is publicly available at https://github.com/SunJianier/CIDER .

Nowadays, research on session-based recommender systems (SRSs) is one of the hot spots in the recommendation domain. Existing methods make recommendations based on the user’s current intention (also called short-term preference) during a session, often overlooking the specific preferences associated with these intentions. In reality, users usually exhibit diverse preferences for different intentions, and even for the same intention, individual preferences can vary significantly between users. As users interact with items throughout a session, their intentions can shift accordingly. To enhance recommendation quality, it is crucial not only to consider the user’s intentions but also to dynamically learn their varying preferences as these intentions change. In this article, we propose a novel I ntention-sensitive P reference L earning N etwork (IPLN) including three main modules: intention recognizer , preference detector , and prediction layer . Specifically, the intention recognizer infers the user’s underlying intention within his/her current session by analyzing complex relationships among items. Based on the acquired intention, the preference detector learns the intention-specific preference by selectively integrating latent features from items in the user’s historical sessions. Besides, the user’s general preference is utilized to refine the obtained preference to reduce the potential noise carried from historical records. Ultimately, the fine-tuned preference and intention collaborate to instruct the next-item recommendation in the prediction layer . To prove the effectiveness of the proposed IPLN, we perform extensive experiments on two real-world datasets. The experiment results demonstrate the superiority of IPLN compared with other state-of-the-art models.

Video Moment Retrieval (VMR) aims to identify a temporal segment in an untrimmed video that best matches a given textual query. Bias in VMR is a critical issue, where the model achieves favorable results even if disregarding the video input. Existing evaluation methods, such as Resplitting, have attempted to address bias by creating out-of-distribution (OOD) datasets. However, these methods provide an incomplete definition of bias and do not quantify bias. To this end, we provide a comprehensive definition of bias in VMR, encompassing both data bias and model bias. Besides, our evaluation metrics can analyze the magnitude of these biases better. To address both data and model biases comprehensively, we introduce Reverse Distribution based VMR (ReDis-VMR). This novel approach dynamically generates datasets with inverse distributions tailored to different models based on Gaussian kernel estimation. As a result, it enables a more accurate evaluation of model performance. Building on ReDis-VMR, we further propose the Dynamic Expandable Adjustment (DEA) pipeline. DEA incrementally expands the model structure to enhance its focus on video and text features, and it incorporates a fair loss to minimize the influence of concentrated data distributions. The experimental results on bias ratio demonstrate that our ReDis method achieves state-of-the-art performance in bias elimination, while the results on moment retrieval confirm the effectiveness of our DEA framework across three evaluation methods, two datasets, and three baselines.

Sequential Recommenders (SRs) are trained to predict the next item as the target given its preceding items as the input, assuming every input-target pair is matched and is reliable for training. However, users can be induced by external distractions to click on items inconsistent with their true preferences, resulting in unreliable training instances with mismatched input-target pairs. To resist unreliable data, researchers attempt to develop Robust SRs (RSRs). However, our data analysis unveils that existing RSRs are data-driven. That is, for most instances formed by infrequently co-occurred items, existing RSRs are uncertain about their reliability. To fill this gap, we propose a generic framework -- LLM4RSR (Large Language Models for Robust Sequential Recommendation) to semantically complement data-driven RSRs by correcting uncertain instances into reliable ones based on LLMs' semantic comprehension of items beyond co-occurrence. In this way, RSRs can be re-trained with the corrected data for better accuracy. This is a selective knowledge distillation procedure, where the LLM acts as a teacher guiding student RSRs via uncertain instances. To align LLMs with the data correction task and mitigate inherent hallucinations, we equip the LLM with profile, plan, and memory modules, which are automatically optimized via textual gradient descent, eliminating the need for human effort and expertise. Experiments on four real-world datasets spanning eight backbones verify the generality, effectiveness, and efficiency of LLM4RSR.

Hybrid-storage blockchains have become a promising paradigm for scaling up query processing services. This paradigm provides a hybrid on/off-chain approach, where only small metadata is stored on-chain while the raw data is outsourced to off-chain storage. The key concerns for query processing in such a system are security and query integrity. However, existing schemes mostly address an impractical honest-but-curious model, rather than a more realistic malicious model, due to the intricate interplay between security and query integrity. Additionally, supporting efficient dynamic update with forward security is a significant challenge for blockchain systems. To address these issues, in this paper, we first formally define the problem of secure, reliably verifiable, and dynamic Boolean range queries in hybrid-storage blockchains (SRVF). Then, we propose a novel index called Virtual Keyword Forest (VKF), which achieves secure and reliably verifiable query processing in hybrid-storage blockchains. To support dynamic queries with forward security, we propose an adaptive version-control update scheme to integrate into VKF. Furthermore, to reduce communication overhead and gas consumption, we design an aggregation signature algorithm that ensures the verification information is of a fixed size. We provide theoretical security analysis and empirical evaluations, comparing our proposed approaches with the state-of-the-art approaches, to demonstrate their feasibility.

A corpus of recent work has revealed that authenticated query services have been under the spotlight due to the untrustworthiness of outsourced service provider. To enrich scalable functionality, there is an increasing demand for dynamically authenticated query. However, when implementing query and update simultaneously, traditional approaches heavily suffer from the inconsistency between verification digest and requested index and therefore are infeasible in reality. Moreover, the efficiency of storage, query, verification, and update is still a huge hinder when processing large scale data. To address these challenging issues, in this paper, we propose a novel idea of authenticated learned index that is carefully designed and actively optimized for authenticated query processing. Specifically, we first propose a version control update mechanism for consistency guarantee by maintaining historical index versions. Following this, we propose two basic authenticated learned indexes, i.e., query-friendly PVL-tree and update-friendly PVLB-tree, to support efficient scalable authenticated range query. Furthermore, to improve the efficiency, we introduce a hybrid index framework HPVL-tree based on two basic indexes. Extensive theoretical and experimental analysis demonstrate that our proposed HPVL-tree outperforms the state-of-the-art approaches by up to$2.28\times, 3.96\times$, and$2.51\times$in search time, update time, and verification time, respectively. Moreover, the storage overhead and communication overhead occupy only 38 % and 2.25 % of existing approach, respectively.

Graph-based methods for high-dimensional Approximate Nearest Neighbor (ANN) search have achieved remarkable success. Recent studies have revealed that DCO (distance comparison operation) is a bottleneck in graph-based methods due to distance computations. Optimizations such as ADSampling, DDC and DADE are employed to alleviate this issue by terminating the distance computation early. Although these optimizations achieve significant speedup, they rely on an estimation-and-testing process for early termination. Their effectiveness diminishes when SIMD (Single Instruction Multiple Data) acceleration is enabled in distance computation, the cost introduced in estimation-and-testing process may outweigh the benefit of early termination, leading to performance degradation. Furthermore, the best-first-search strategy employed in graph-based methods requires DCO for all neighboring points, incurring redundant distance computation. To address these issues, in this paper, we first perform a cost analysis to reveal the inefficiency of existing DCO optimizations under SIMD-enabled setting. We then analyze the current search strategy to demonstrate that not all neighboring nodes require DCO. Based on these analyses, we present SkipComputing to accelerate the ANN search. Specifically, we first propose a subspace-based candidate search strategy to identify promising points for DCO, thereby eliminating the reliance on estimation-and-testing based DCO optimization for low potential points. We then develop a lower-bound pruning method based on distance decomposition to enable early termination of distance computations in DCO. Finally, we optimize the data layout to reduce the overhead of random memory access during candidate search. When SIMD is enabled, experimental results show that SkipComputing substantially outperforms HNSW, achieving up to 6x performance improvement. Furthermore, it achieves up to 2.7x speedup over state-of-the-art optimization methods while maintaining competitive space efficiency.

Deterministic databases are revolutionizing batch transaction processing in shared-nothing architectures, with efficiency largely hinging on minimizing cross-partition operations. However, achieving a universal data partition that eliminates cross-partition operations is often impractical. Thus, developing effective transaction partitioning strategies becomes crucial. Existing methods tend to partition and optimize transactions individually, neglecting the overarching commonalities between transactions within a batch. This oversight results in suboptimal partitioning of transactions that share similar read-write sets, ultimately missing opportunities for global batch execution optimization. In this paper, we present DelayPart, a deterministic database transaction engine that employs a ''wait and see'' strategy to address contextual conflicts between transactions within each batch. DelayPart models transaction batch partitioning as a k -cut problem based on transaction similarity and employs a LSH forest-based approach to approximate solutions efficiently in linear time, factoring in the global overhead of remote operations for each batch. By postponing the allocation and execution of individual transactions, DelayPart systematically analyzes inter-transaction relationships, enhancing overall performance without compromising execution efficiency. We evaluated DelayPart's performance against various benchmarks on a large-scale cluster, demonstrating that it significantly outperforms state-of-the-art transaction partitioning methods.

Path finding in multi-agent systems aims to identify collision-free and cost-optimized paths for all agents with distinct start and goal positions. It poses challenging optimization problems. Existing research typically treats all agents equally, overlooking their differences in practical scenarios where they undertake the tasks of varying importance. In many application scenarios, agents must be differentiated into critical (c-agents) and acritical ones (a-agents) due to premium/general service, no-loaded/full-loaded states, and urgent/non-urgent tasks. Facing this practical need, this work focuses on multi-agent systems in which the different importance of agents must be considered; and tackles a lexicographic dual-objective variant of path-finding problem. The consideration of c-agents makes the concerned problem more useful yet more challenging than basic multi-agent path-finding problems. Different from existing multi-agent path planning methods that minimize the sum-of-costs of all agents, we optimize two objectives with preferences to emphasize the influence of c-agents on the system. The primary one is to minimize the sum-of-costs of c-agents and the secondary one is to minimize that of a-agents. As existing methods are inadequate for this unique challenge, we adapt a conflict-based search framework and design new two-level lexicographic dual-objective optimization methods to deal with it. A high level is responsible for iteratively expanding a search tree and adding constraints to resolve conflicts among agents. A low level is responsible for finding the path of each agent for the node newly expanded in the high level. By conducting numerous computational experiments, we verify the great performance of the presented methods in solving the concerned problem. We further develop a prototype system incorporating our methods and make it public to promote their practical application. This research contributes valuable insights and solutions to pathfinding challenges in multi-agent systems with critical and acritical agents. Note to Practitioners—This work addresses a multi-agent path finding problem in multi-agent systems involving both critical and acritical agents. The former are more important than the latter since they are assigned to perform more important tasks. This is a common scenario in manufacturing and service environments. We propose a two-level lexicographic dual-objective optimization framework to deal with the problem and underscore the importance of c-agents in the path finding problem. Three solution approaches are designed for practitioners to select based on their practical application needs. The computational experimental results and statistical analyses highlight the exceptional performance of our proposed approaches. In order to facilitate the practical application, we further provide a prototype system with our proposed approaches embedded, which is openly accessible for practitioners to realize their specific applications.

A production workshop with mobile robots can be considered as a hybrid system consisting of a production system and a transportation one. Mobile robots are responsible for transferring production tasks among the machines of a production system and constitute a multi-robot transport system. It is highly coupled with a production system because of the interdependency that exists between production scheduling and mobile robot assignment. In this work, we study their integrated optimization problem for a mobile robot-based job shop with blocking properties. Its aim is to minimize total completion time as an objective function to improve overall operational efficiency. We consider the speed of a robot that varies according to whether it is loaded or not. We formulate this new problem into a mixed integer linear program to provide an algebraic description. Then, we propose a constraint programming method to solve it with high efficiency. The superiority of constraint programming over mixed integer linear programming in terms of the number of variables and constraints is analyzed. Numerous experiments on benchmark examples show that constraint programming can well handle the concerned problem. Under a one-hour time limit, it can exactly solve its instances while mixed integer linear programming cannot. Under a one-minute time limit, it obtains much better solutions than mixed integer linear programming and heuristic strategies, thus implying its high potential to be put into industrial applications. Note to Practitioners—The integration of mobile robots into production workshops has emerged as a pivotal strategy to enhance the operational efficiency of an advanced manufacturing system. This integration transforms the traditional job shop into a hybrid system, where mobile robots play a crucial role in transferring production tasks among machines. This brings a unique challenge to practitioners due to the intricate interdependencies between production scheduling and mobile robot assignment. The focus of our study is on the optimization of a mobile robot-based job shop to improve its overall operational efficiency. Our approach involves formulating this complex problem as a mixed-integer linear program, thereby providing a concise mathematical representation. We propose a constraint programming method to solve the problem efficiently. Through numerous experiments on benchmark examples, our findings indicate that the proposed constraint programming method can well solve the concerned problem given long or short solution time. This underscores its high potential for practical implementation in industrial scenarios.

Blockchain is increasingly applied to traceability applications in supply chains for its tamper-proof nature, but it must also ensure the core requirements, which are efficient data storage and verifiable queries. Existing solutions create an authenticated data structure (ADS) for each tuple and use a Merkle variant on a blockchain to maintain evidence. However, consensus algorithms slow down block generation, and limited block capacity results in excessive blockchain space usage by ADS, failing to meet efficient data storage needs. In this article, we present ScorpioBase, a batched blockchain system with two components: the storage engine (SE) and the signature manager (SM). SE packages multiple tuples into a “batch” data structure and generates a “batch” signature. SM stores the “batch” signature on the blockchain for evidence. Batching effectively reduces the blockchain storage burden, allowing the system to store more tuples with the same number of consensus events, thus increasing throughput. We design a fine-grained “batch” signature to enable ScorpioBase to support verifiable queries. “Batch” signatures can efficiently verify the integrity of both the “batch” and each tuple within it. In conclusion, ScorpioBase supports asynchronous queries for varying security and efficiency needs and ensures robustness against malicious attacks in verifiable queries. Compared to existing solutions, it significantly improves data storage capacity and the efficiency of verifiable queries.

In recent years, session-based recommender systems (SRSs) have emerged as a significant research focus within the recommendation field. Capturing user intentions to infer user interest accordingly has proven to be effective in enhancing the accuracy of SRSs. However, existing techniques assume that all sessions have the same number of intentions or that the items in one category belonging to the same session reflect the same intention. In real applications, such as e-commerce, sessions may have different numbers of intentions, and the same type of items in a session may correspond to different intentions. As a result, existing techniques cannot guarantee high-quality user interest prediction. In this article, we propose a novel Adaptive Intention Learning Network (AILN) to capture an adaptive number of intentions for each session, thereby enhancing the accuracy of user interest inference. Specifically, we design an intention evaluation network (IEN) to evaluate whether a subsequence of a session corresponds to a valid intention, and an intention generation network (IGN) to learn the representation of a valid intention. By checking each subsequence of a session, IEN and IGN enable the incremental learning of a session-specific intention hierarchy (IH) to store valid intentions of the session. To reduce the cost of building the IH, we propose a pruning strategy that exploits the intention validity to avoid unnecessary evaluation. The representative intentions are selected from IH and input into a designed interest predictor to infer the user interest. Experimental results on two real-world datasets demonstrate the superiority of our proposed AILN.

Continuous top-$k$query over sliding window is a fundamental challenge in the domain of streaming data management. Specifically, a continuous top-k query$q$monitors the window$W$, returning the$k$objects with the highest scores to the system with each slide of the window. This paper delves into one of its important variants, referred to as multiple continuous top.$k$queries over data stream, which holds significant applications. While various efforts have been made to support continuous top-k query, few have addressed the complexities of multiple continuous top-k queries. The prevailing approach involves selecting a minimal number of objects in the window as candidates, incrementally maintaining them, and using them to support query processing as efficiently as possible. However, these endeavors exhibit sensitivity to the query workload scale or query parameters such as$k$, the window length$n$, and others. Consequently, they incur high running/space cost in updating the candidate set. In this paper, we propose a novel index PH-Tree (Partition and Heap-based Binary Tree), designed to facilitate multiple continuous top-k queries. We partition the query window into a group of disjoint partitions and use PH-Tree to organize these partitions. Additionally, the PH-Tree allows for flexible candidate selection based on the size of each partition, parameter distribution of queries and score distribution of objects. We further develop a group of efficient algorithms to support candidate set incremental maintenance and query processing. The effectiveness and efficiency of the proposed algorithms are validated through extensive theoretical analysis and exneriments detailed in this paper.

Blockchain has emerged as a prevailing paradigm for decentralized applications due to its reliability and transparency. To scale up retrieval services, a common strategy is to use a hybrid storage model, where on-chain storage is responsible for small metadata and off-chain storage is for outsourced raw data. However, data security and result authenticity are ongoing challenges in this scenario, and little work has been done due to the difficulty of combining result verification and privacy preservation, especially for dynamic updates while supporting forward privacy. In this paper, we formally define the problem of efficient, verifiable, and secure conjunctive keyword search in hybrid-storage blockchains (vsChain) and propose a novel hybrid index that achieves efficient query and verification while supporting dynamic updates with forward privacy guarantee. Finally, we provide empirical evaluations using real and synthetic datasets to demonstrate the feasibility of our proposed scheme.

With the explosive growth of multimodal Internet data, cross-modal hashing retrieval has become crucial for semantically searching instances across different modalities. However, existing cross-modal retrieval methods rely on assumptions of perfect consistency between modalities and between modalities and labels, which often do not hold in real-world data. We introduce two types of inconsistency: Modality-Modality (M-M) and Modality-Label (M-L) inconsistencies. We further validate the prevalent existence of inconsistent data in multimodal datasets and highlight it will reduce the accuracy of existing Cross-Modal retrieval methods. In this paper, we propose a novel framework called Inconsistency Alleviated Cross-Modal Retrieval (IA-CMR), addressing challenges posed by these inconsistencies. We first utilize two forms of contrastive learning loss and a mutual exclusion constraint to effectively disentangle modal information into modality-common hash codes and modality-unique hash codes. Our dedicated design in modality disentanglement is capable of alleviating the M-M inconsistency. Subsequently, we refine common labels through a label refinement loss and employ a Cross-modal Common Semantic Alignment module for effective alignment. The label refinement process and the CCSA module collectively handle the M-L inconsistency issue. IA-CMR outperforms 9 comparison baselines on two benchmark multimodal datasets, achieving an improvement in retrieval accuracy of up to 25.13%. The results confirm the effectiveness of IA-CMR in alleviating inconsistency and enhancing cross-modal retrieval performance.

Complex event matching has gained a lot of at-tention for evaluating complex queries over event streams. The events composing a complex event occur within a user-specified time window and can be nonconsecutive on the stream. Existing methods widely utilize the state automaton to match complex events. However, the state automaton is typically used for matching consecutive items satisfying a pattern, e.g., the regular expression. To support nonconsecutive event matching, it has to maintain a large number of partial matches and skip irrelevant events, which results in a huge overhead. To avoid this problem, we employ the bit parallelism technique to match complex events continuously in this paper. We utilize a set of bit sequences to represent the events, where each bit is associated with a time slice, and an event is mapped to a 1-bit of the sequence if its timestamp belongs to the time slice. Then, bit-parallel operations are designed to process the constraints defined on the complex event, e.g., the time window limitation, and sequential order of the events, etc. We further propose the bit-parallel algorithms to support continuous complex event matching using these bit operations. Our experiments on real and synthetic datasets demonstrate that our method outperforms the existing methods by up to an order of magnitude in Query efficiency.

Radius-bounded$k$-core queries (RB-$k$-core queries) in geo-social networks aim to find all$k$-cores containing a given query vertex$q$while all vertices in each$k$-core fall into a circle under a given query radius$r$, which is widely used in many applications, such as team formulation and event organization. However, the query parameters$k$and$r$are hard to specify by the users without any background knowledge, which means the query results often do not meet the users' requirements, i.e., some expected vertices are missed in the query results. To tackle this issue, we investigate the problem of exploring optimal refined parameters (EOP) for expected results on RB­$k$-core queries, which aims to explore the optimal parameters that make the expected vertex$\omega$and query vertex$q$appear in the same RB-$k$-core. To address the EOP problem, we first propose two baseline algorithms, namely PriorityR and HybridR, which refine the parameters$k$and$r$simultaneously based on the effective bounds of the refined$r^{\prime}$• To enhance the efficiency of exploring optimal parameters, we develop two efficient al-gorithms. The first algorithm, Priority K, simultaneously refines both parameters based on the effective bound of the refined$k$• The second algorithm, HybridK, explores the optimal parameters using the continuous convergence bounds of the refined$k^{\prime}$and$r$• Furthermore, to enhance exploration efficiency, we develop a novel index, called HCR-Tree, based on the hierarchical coreness of vertices and R- Tree. This index accelerates the verification of whether the coreness of a vertex in any sub graph exceeds$k$in the above algorithms. Finally, we conduct extensive experiments using five real geo-social network datasets, which show that the optimal parameters can be explored effectively by the algorithms, and HybridK is the most effective. Meanwhile, the HCR- Tree performs better than the R- Tree for the EOP problem.

Blockchain has emerged as a prevailing paradigm for decentralized applications due to its reliability and transparency. To scale up retrieval services, a common strategy is to use a hybrid storage model, where on-chain storage is responsible for small metadata and off-chain storage is for outsourced raw data. However, data security and result authenticity are ongoing challenges in this scenario, and little work has been done due to the difficulty of combining result verification and privacy preservation, especially for dynamic updates while supporting forward privacy. In this paper, we formally define the problem of efficient, verifiable, and secure conjunctive keyword search in hybrid-storage blockchains (vsChain) and propose a novel hybrid index that achieves efficient query and verification while supporting dynamic updates with forward privacy guarantee. We also design two optimized schemes to improve query and verification performance by using a partition-based method and an obfuscated counting Bloom filter mechanism. Finally, we provide a theoretical security analysis and empirical evaluations using real and synthetic datasets to demonstrate the feasibility of our proposed schemes.

Data outsourcing to the cloud has become increasingly popular for high-speed storage and retrieval. However, privacy and security are pressing concerns that hinder the further development of cloud computing. A common approach is to encrypt data before outsourcing, assuming the cloud is semi-honest. However, in reality, the cloud may be malicious and forge query results unexpectedly. Moreover, most previous schemes are designed for single-user setting, where different users share the same secret key, leading to potential privacy leaks. Therefore, ensuring confidentiality and verifiability in multi-user setting is crucial but has not been well-addressed. In this paper, we formally define the notion of Verifiable and Secure Range Query in Multi-User Setting (VSRQM) and propose a prefix-aware encoding (Pcode) scheme to encode spatial data for query processing. Next, we design a Tree-Aided Verifiable and Secure Index (SATree) on top of the Pcode and symmetric re-encryption scheme. SATree preserves data privacy, provides a mechanism to verify query results’ integrity and achieves sub-linear search time. Additionally, we propose two compression schemes to reduce the space cost of storage and transmission. Finally, we present formal complexity and security analyses and conduct empirical evaluations on real and synthetic datasets to demonstrate our proposed approaches’ practical performance.

Most sequential recommendation systems (SRSs) predict the next item as the target for users given its preceding items as input, assuming the target is definitely related to its input. However, users may unintentionally click items that are inconsistent with their preference due to external factors, causing unreliable instances whose target mismatches the input. We, for the first time , verify SRSs can be misguided by such unreliable instances and design a generic SRS framework B y E liminating un R eliable D ata (BERD+), which can be flexibly plugged into existing SRSs. Specifically, BRED+ is guided with observations on the training process of instances: Unreliable instances generally have high training loss; high-loss instances are not necessarily unreliable but uncertain ones caused by blurry sequential patterns; and item attributes help rectify instance loss and uncertainty, but may also introduce disturbance. Accordingly, BERD+ models both the loss and uncertainty of each instance via a Gaussian distribution, whereby a heterogeneous uncertainty-aware graph convolution network is designed to learn accurate embeddings for different entities while reducing the disturbance caused by uncertain attribute values. Thereafter, an explicit preference extractor rectifies instance loss and uncertainty and reduces the disturbance caused by less-focused attribute types. Finally, instances with high loss and low uncertainty are eliminated as unreliable data. Extensive experiments verify the efficacy of BERD+.

Sequential recommendations have received great attention in recent years due to their wide application in e-commerce, trip planning, and online education. Contexts reveal the intention of a user in a transaction such as consuming or purchasing an item, and highly affect her behaviour. However, existing techniques cannot fully capture the context-sensitive and dynamic sequential user behaviours for effective and efficient sequential recommendation. To address this limitation, we propose a novel Dynamic Bi-layer Graph learning (DBIG)-based framework for sequential recommendation, which learns the sequence dynamics of user behaviours and contexts. Specifically, we first propose a context graph to identify the relevant contexts to a target user. Then, we propose a transaction context graph that predicts the probability of a transaction happening under certain contexts. In addition, we apply BERT (Bidirectional Encoder Representations from Transformers) to our graph embedding for understanding the user sequential behaviours in bidirectional ways and generating recommendations. Finally, we propose a cluster-structure-based algorithm, which incrementally maintains the DBIG model and BERT over dynamic transaction updates. We evaluate our DBIG-based framework by conducting extensive experiments over five public datasets. The quantitative results demonstrate the superiority of our approach in terms of effectiveness and efficiency.

We study the efficient regular expression (regex) matching problem. Existing algorithms are scanning-based algorithms that typically use an equivalent automaton compiled from the regex query to verify a document. Although some works propose various strategies to quickly jump to candidate locations in a document where a query result may appear, they still need to utilize the scanning-based method to verify these candidate locations. These methods become inefficient when there are still many candidate locations needed to be verified. In this paper, we propose a novel approach to efficiently compute all matching positions for a regex query purely based on a positional q-gram inverted index. We propose a gram-driven NFA to represent the language of a regex and show all regex matching locations can be obtained by finding positions on q-grams of GNFA that satisfy certain positional constraints. Then we propose several GNFA-based query plans to answer the query using the positional inverted index. In order to improve the query efficiency, we design the algorithm to build a tree-based query plan by carefully choosing a checking order for positional constraints. Experimental results on real-world datasets show that our method outperforms state-of-the-art methods by up to an order of magnitude in query efficiency.

Financial supervision plays a pivotal role in society as it provides early warnings of financial activities and aids the government in detecting financial crimes. Detecting anomalous activities from normal financial activities is extremely challenging due to their disguise and complexity. However, existing anomaly detection methods in real-world financial scenarios typically suffer from some limitations: (a) Their formulations are overly simplistic to effectively identify complex anomalies; (b) Machine learning-based anomaly-detection methods lack enough training label, interpretability, and confidence, making it difficult to obtain approval from governments or financial institutions; (c) Many of them only focus on the financial transaction itself, ignoring the spatio-temporal characteristics of transaction and social relationships. To circumvent the challenges mentioned above, this paper proposes a novel anomaly-detection framework to detect the anomalies from disguised normal financial activities and infer clue chains for them. In particular, we are the first to formalize ten anomalies by reference to actual bank statements, and then three types of anomaly-detecting algorithms are proposed to discover these anomalies from financial activities. Next, we utilize an intelligent search algorithm to trace the most suspicious activities (clue chains) for institutions, improving the interpretability compared with learning-based methods. More importantly, we developed an anomaly-detection system, Themis, to detect these complex financial anomalies, which has been deployed in some real scenarios. The performance of Themis is demonstrated through some comprehensive extensive experiments and case studies on synthetic datasets and real bank statements.

Sequential recommender systems (SRSs) are typically trained to predict the next item as the target given its preceding (and succeeding) items as the input. Such a paradigm assumes that every input-target pair is reliable for training. However, users can be induced to click on items that are inconsistent with their true preferences, resulting in unreliable instances, i.e., mismatched input-target pairs. Current studies on mitigating this issue suffer from two limitations: (i) they discriminate instance reliability according to models trained with unreliable data, yet without theoretical guarantees that such a seemingly contradictory solution can be effective; and (ii) most methods can only tackle either unreliable input or targets but fail to handle both simultaneously. To fill the gap, we theoretically unveil the relationship between SRS predictions and instance reliability, whereby two error-bounded strategies are proposed to rectify unreliable targets and input, respectively. On this basis, we devise a model-agnostic Bidirectional Data Rectification (BirDRec) framework, which can be flexibly implemented with most existing SRSs for robust training against unreliable data. Additionally, a rectification sampling strategy is devised and a self-ensemble mechanism is adopted to reduce the (time and space) complexity of BirDRec. Extensive experiments on four real-world datasets verify the generality, effectiveness, and efficiency of our proposed BirDRec.

Recommendation usually focuses on immediate accuracy metrics like CTR as training objectives. User retention rate, which reflects the percentage of today’s users that will return to the recommender system in the next few days, should be paid more attention to in real-world systems. User retention is the most intuitive and accurate reflection of user long-term satisfaction. However, most existing recommender systems are not focused on user retention-related objectives, since their complexity and uncertainty make it extremely hard to discover why a user will or will not return to a system and which behaviors affect user retention. In this work, we conduct a series of preliminary explorations on discovering and making full use of the reasons for user retention in recommendation. Specifically, we make a first attempt to design a rationale contrastive multi-instance learning framework to explore the rationale and improve the interpretability of user retention. Extensive offline and online evaluations with detailed analyses of a real-world recommender system verify the effectiveness of our user retention modeling. We further reveal the real-world interpretable factors of user retention from both user surveys and explicit negative feedback quantitative analyses to facilitate future model designs. The source codes are released at https://github.com/dinry/IURO.

k-closest pair (KCP for short) search is a fundamental problem in database research. Given a set of d-dimensional streaming data S, KCP search aims to retrieve k pairs with the shortest distances between them. While existing works have studied continuous 1-closest pair query (i.e., k=1) over dynamic data environments, which allow for object insertions/deletions, they require high computational costs and cannot easily support KCP search with k>1. This paper investigates the problem of KCP search over data stream, aiming to incrementally maintain as few pairs as possible to support KCP search with arbitrarily k. To achieve this, we introduce the concept of NNS (short for N earest N eighbour pair- S et), which consists of all the nearest neighbour pairs and allows us to support KCP search via only accessing O(k) objects. We further observe that in most cases, we only need to use a small portion of NNS to answer KCP search as typically kłl n. Based on this observation, we propose TNNS (short for T hreshold-based NN pair S et), which contains a small number of high-quality NN pairs, and a partition named τ-DLBP (short for τ- D istance L ower- B ound based P artition) to organize objects, with τ being an integer significantly smaller than n. τ-DLBP organizes objects using up to O(łog n / τ) partitions and is able to support the construction and update of TNNS efficiently.

The rapid growth of online service platforms has greatly influenced the way users conduct daily activities. In response to the requirements of frequent online activities, recommendation has become one of the best ways for the organizations, governments and individuals to understand their users and promote their services. Effective recommendation of online items has become critical in domains such as e-commerce and online media. Driven by the business success, academic research in this field has been active for many years. However, there are still many research challenges, such as context discovery, sequential user behavior influence, explainability and user interaction of system, big service data management. Especially, the highly dynamic online network data make these challenges even critical. Due to the high pressing interest and challenges in this area, this special issue is devoted to this topic, and focuses on the new solutions using AI and Big Data techniques.

With the boom in cloud computing, data outsourcing in location-based services is proliferating and has attracted increasing interest from research communities and commercial applications. Nevertheless, since the cloud server is probably both untrusted and malicious, concerns about data security and result integrity have become on the rise sharply. In addition, in the single-user situation assumed by most existing works, query users can capture query content from each other even though the queries are encrypted, which may incur the leakage of query privacy. Unfortunately, there exists little work that can commendably assure data security and result integrity in the multi-user setting. To this end, in this article, we study the problem of multi-user, secure, and verifiable$k$nearest neighbor query (MSV$k$kNN). To support MSV$k$NN, we first propose a novel unified structure, called verifiable and secure index (VSI). Based on this, we devise a series of secure protocols to facilitate query processing and develop a compact verification strategy. Given an MSV$k$NN query, our proposed solution can not merely answer the query efficiently while can guarantee: 1) preservingdata privacy,query privacy,result privacy, andaccess patterns privacy; 2) authenticating thecorrectnessandcompletenessof the results; 3) supportingmulti-userwith different keys. Finally, the formal security analysis and complexity analysis are theoretically proven and the performance and feasibility of our proposed approach are empirically evaluated and demonstrated.

Cross-modal hashing has attracted considerable attention for large-scale multimodal data. Recent supervised cross-modal hashing methods using multi-label networks utilize the semantics of multi-labels to enhance retrieval accuracy, where label hash codes are learned independently. However, all these methods assume that label annotations reliably reflect the relevance between their corresponding instances, which is not true in real applications. In this paper, we propose a novel framework called Bidirectional Reinforcement Guided Hashing for Effective Cross-Modal Retrieval (Bi-CMR), which exploits a bidirectional learning to relieve the negative impact of this assumption. Specifically, in the forward learning procedure, we highlight the representative labels and learn the reinforced multi-label hash codes by intra-modal semantic information, and further adjust similarity matrix. In the backward learning procedure, the reinforced multi-label hash codes and adjusted similarity matrix are used to guide the matching of instances. We construct two datasets with explicit relevance labels that reflect the semantic relevance of instance pairs based on two benchmark datasets. The Bi-CMR is evaluated by conducting extensive experiments over these two datasets. Experimental results prove the superiority of Bi-CMR over four state-of-the-art methods in terms of effectiveness.

Spatial keyword query has attracted wide-spread academic and industrial concerns due to the popularity of location-based services and Internet of Things. To efficiently support the online query processing, the data owners need to outsource their data to cloud platforms. However, the outsourcing services may raise privacy leaking issues. Moreover, access control, another important security concern, is largely ignored. Therefore, we first propose and formalize the problem of secure boolean spatial keyword query under lightweight access control while guaranteeing the widely acceptedadaptive indistinguishability against chosen keyword attackmodel. Then, we devise a novel hybrid Bloom filter encoding strategy, including a linear embedding and exponent-based transformation schemes and a secure index structure, calledSAGTree. They can maintain both geo-text and access policy information together in a secure way while answering the encrypted queries under access control without decryption. Finally, we present the in-depth security analysis and demonstrate the performance of our proposed algorithms.

We study the efficient regular expression (regex) matching problem. Existing algorithms are the scanning-based algorithms which typically use an equivalent automaton compiled from the regex query to verify a document. Although some works propose various strategies to quickly jump tocandidate locationsin a document where a query result may appear, they still need to utilize the scanning-based method to verify these candidate locations. These methods become inefficient when there are still many candidate locations needed to be verified. In this article, we propose a novel approach to efficiently compute all matching positions for a regex query purely based on a positional$q$-gram inverted index. We propose a gram-driven NFA to represent the language of a regex and show all regex matching locations can be obtained by finding positions on$q$-grams of GNFA that satisfy certain positional constraints. Then we propose several GNFA-based query plans to answer the query using the positional inverted index. In order to improve the query efficiency, we design the algorithm to build a tree-based query plan by carefully choosing a checking order for positional constraints. Experimental results on real-world datasets show that our method outperforms state-of-the-art methods by up to an order of magnitude in query efficiency.

Collaboration efficiency is of paramount importance for software development. Finding suitable developers is critical and challenging due to the difficulty of capturing developers’ expertises, relevance as well as the sparsity of explicit developer-task interactions. To tackle this problem, existing developer recommendation approaches focus on modelling the developer’s expertise or interactions with tasks based on their historical information. However, such approaches often suffer from low performance because they ignore some useful information that might help improve recommendation performance, such as 1) developers’ collaboration relationship; 2) the interaction relationship between developer and task; and 3) the tasks’ similarity relationship. To leverage the above-mentioned relationships, this paper proposes DevRec, a novel multi-relationship embedded approach for software developer recommendation. We first formally define the multi-relationships and then learn the vector representations (aka. embeddings) of developers and tasks. Second, we explicitly encoded the multi-relationships into the embedding process. Third, to refine the embeddings of developers and tasks, we recursively propagate the embeddings from their high-order connectivity based on graph convolution network. Moreover, to reveal the importance of different relationships, we generate their attentive weights based on attention mechanism. Finally, to evaluate the performance of DevRec, we conduct extensive experiments on two real-world datasets, and to investigate the usefulness of DevRec in practice, we conduct a user study at a large software company. The results show that DevRec outperforms other five state-of-the-art approaches significantly.

Most sequential recommender systems (SRSs) predict next-item as target for each user given its preceding items as input, assuming that each input is related to its target. However, users may unintentionally click on items that are inconsistent with their preference. We empirically verify that SRSs can be misguided with such unreliable instances (i.e. targets mismatch inputs). This inspires us to design a novel SRS By Eliminating unReliable Data (BERD) guided with two observations: (1) unreliable instances generally have high training loss; and (2) high-loss instances are not necessarily unreliable but uncertain ones caused by blurry sequential pattern. Accordingly, BERD models both loss and uncertainty of each instance via a Gaussian distribution to better distinguish unreliable instances; meanwhile an uncertainty-aware graph convolution network is exploited to assist in mining unreliable instances by lowering uncertainty. Extensive experiments on four real-world datasets demonstrate the superiority of our proposed BERD.

Deep hashing based retrieval models have been widely used in large-scale image retrieval systems. Recently, there has been a surging interest in studying the adversarial attack problem in deep hashing based retrieval models. However, the effectiveness of existing adversarial attacks is limited by their poor perturbation management, unawareness of ranking weight, and only laser-focusing on the attack image. These shortages lead to high perturbation costs yet low AP reductions. To overcome these shortages, we propose a novel adversarial attack framework to improve the effectiveness of adversarial attacks. Our attack designs a dimension-wise surrogate Hamming distance function to help with wiser perturbation management. Further, in generating adversarial examples, instead of focusing on a single image, we propose to collectively incorporate relevant images combined with an AP-oriented (average precision) weight function. In addition, our attack can deal with both untargeted and targeted adversarial attacks in a flexible manner. Extensive experiments demonstrate that, with the same attack performance, our model significantly outperforms state-of-the-art models in perturbation cost on both untargeted and targeted attack tasks.

With the boom in cloud computing, data outsourcing in location-based services is proliferating and has attracted increasing interest from research communities and commercial applications. Nevertheless, since the cloud server is probably both untrusted and malicious, concerns of data security and result integrity have become on the rise sharply. However, there exist little work that can commendably assure the data security and result integrity using a unified way. In this paper, we study the problem of secure and verifiable k nearest neighbor query (SVkNN). To support SVkNN, we first propose a novel unified structure, called verifiable and secure index (VSI). Based on this, we devise a series of secure protocols to facilitate query processing and develop a compact verification strategy. Given an SVkNN query, our proposed solution can not merely answer the query efficiently while can guarantee: 1) preserving the privacy of data, query, result and access patterns; 2) authenticating the correctness and completeness of the results without leaking the confidentiality. Finally, the formal security analysis and complexity analysis are theoretically proven and the performance and feasibility of our proposed approaches are empirically evaluated and demonstrated.

Deep multimodal clustering is challenging, since it needs to learn appropriate features for different modalities and find correct clusters by using consistency among the modalities. Existing methods treat the two problems separately, nevertheless, the optimization of one does not guarantee the optimization of the other. In this paper, we propose an end-to-end Deep Multimodal Clustering (DMMC) framework, which achieves a joint optimization of feature learning and multimodal clustering. We encourage the learned features of each modality to be cluster-oriented by autoencoder with Frobenius norm loss. Then, DMMC integrates features of different modalities by clustering integration layer and learns consensus feature by a consensus loss. The clustering result can be discovered in the consensus feature. Compared with existing clustering methods, our framework achieves superior performances measured by the standard clustering evaluation metrics.

Recently, GAN-based collaborative filtering methods have gained increasing attention in recommendation tasks which can learn remarkable user and item representation. However, these existing GAN-based methods mainly suffer from two limitations: (1) Their trainings are not comprehensive given the fact that the discriminator may be trained misleadingly and over-early converging since the generator may accidentally sample real items as fake ones, resulting in the emergence of contradicting labels for the same items. (2) They fail to consider implicit friends (users with the same interests.), leading to severe limitations of recommendation performance. In this paper, we propose BiGAN, an innovative bidirectional adversarial recommendation model which can alleviate the limitations mentioned above in recommendation tasks. It consists of two GANs, namely ForwardGAN and BackwardGAN. Specifically, ForwardGAN learns to generate a group of possible interacted items given a specific user, it aims to ensure that the discriminator Df can be trained effectively. Furthermore, BackwardGAN fully exploits implicit friends with similar behaviors, then propagates them back to ForwardGAN, where a similarity exploration strategy is implemented to gain more outstanding user representation. Therefore, two GANs are trained jointly in a circle, where the augment of one GAN will enhance another one, leading to the promising user and item representation. In the experimental part, we demonstrate that our model is superior to other state-of-the-art recommenders.

Recording and querying time-stamped trajectories incurs high cost of data storage and computing. In this paper, we explore characteristics of the trajectories in road networks, which have motivated the idea of coding trajectories by associating timestamps with relative spatial path and locations. Such a representation contains large number of duplicate information to achieve a lower entropy compared with the existing representations, thereby drastically cutting the storage cost. We propose techniques to compress spatial path and locations separately, which can support fast positioning and achieve better compression ratio. For locations, we propose two novel encoding schemes such that the binary code can preserve distance information, which is very helpful for LBS applications. In addition, an unresolved question in this area is whether it is possible to perform search directly on the compressed trajectories, and if the answer is yes, then how. Here we show that directly querying compressed trajectories based on our encoding scheme is possible and can be done efficiently.We design a set of primitive operations for this purpose, and propose index structures to reduce query response time. We demonstrate the advantage of our method and compare it against existing ones through a thorough experimental study on real trajectories in road network.

In recent years, spatial keyword query has attracted wide-spread research attention due to the popularity of the location-based services. To efficiently support the online spatial keyword query processing, the data owners need to outsource their data and the query processing service to cloud platforms. However, the outsourcing services may raise privacy leaking issues because the cloud server on the platforms may not be trusted for both data owners and query users. Therefore, in this work, we first propose and formalize the problem of privacy-preserving boolean spatial keyword query under the widely accepted Known Background Thread Model. And then, we devise a novel privacy-preserving spatial-textual Bloom Filter encoding structure and an encrypted R-tree index. They can maintain both spatial and text information together in a secure way while answering the encrypted spatial keyword queries without the need for data decryption. To further accelerate the query processing, a compressed encrypted index is provided to deal with the challenges of the large dimension expansion and the expensive space consumption in the encrypted R-tree index. In addition, we develop the corresponding algorithms based on the designed index, and present the in-depth security analysis to show our work's satisfaction meeting the strong secure scheme. Finally, we demonstrate the performance of our proposed index and algorithms by conducting extensive experiments on four datasets under various system settings.

Trust-aware recommender systems have received much attention recently for their abilities to capture the influence among connected users. However, they suffer from the efficiency issue due to large amount of data and time-consuming real-valued operations. Although existing discrete collaborative filtering may alleviate this issue to some extent, it is unable to accommodate social influence. In this paper we propose a discrete trust-aware matrix factorization (DTMF) model to take dual advantages of both social relations and discrete technique for fast recommendation. Specifically, we map the latent representation of users and items into a joint hamming space by recovering the rating and trust interactions between users and items. We adopt a sophisticated discrete coordinate descent (DCD) approach to optimize our proposed model. In addition, experiments on two real-world datasets demonstrate the superiority of our approach against other state-of-the-art approaches in terms of ranking accuracy and efficiency.

Social recommendation could address the data sparsity and cold-start problems for collaborative filtering by leveraging user trust relationships as auxiliary information for recommendation. However, most existing methods tend to consider the trust relationship as preference similarity in a static way and model the representations for user preference and social trust via a common feature space. In this paper, we propose TrustEV and take the view of multi-task learning to unite collaborative filtering for recommendation and network embedding for user trust. We design a special feature evolution unit that enables the embedding vectors for two tasks to exchange their features in a probabilistic manner, and further harness a meta-controller to globally explore proper settings for the feature evolution units. The training process contains two nested loops, where in the outer loop, we optimize the meta-controller by Bayesian optimization, and in the inner loop, we train the feedforward model with given feature evolution units. Experiment results show that TrustEV could make better use of social information and greatly improve recommendation MAE over state-of-the-art approaches.

A phrase is a natural, meaningful, and essential semantic unit. In topic modeling, visualizing phrases for individual topics is an effective way to explore and understand unstructured text corpora. However, from phrase quality and topical cohesion perspectives, the outcomes of existing approaches remain to be improved. Usually, the process of topical phrase mining is twofold: phrase mining and topic modeling. For phrase mining, existing approaches often suffer from order sensitive and inappropriate segmentation problems, which make them often extract inferior quality phrases. For topic modeling, traditional topic models do not fully consider the constraints induced by phrases, which may weaken the cohesion. Moreover, existing approaches often suffer from losing domain terminologies since they neglect the impact of domain-level topical distribution. In this paper, we propose an efficient method for high quality and cohesive topical phrase mining. A high quality phrase should satisfy frequency, phraseness, completeness, and appropriateness criteria. In our framework, we integrate quality guaranteed phrase mining method, a novel topic model incorporating the constraint of phrases, and a novel document clustering method into an iterative framework to improve both phrase quality and topical cohesion. We also describe efficient algorithmic designs to execute these methods efficiently. The empirical verification demonstrates that our method outperforms the state-of-the-art methods from the aspects of both interpretability and efficiency.

The growing size of modern file system is expected to reach EB-scale. Therefore, an efficient and scalable metadata service is critical to system performance. Distributed metadata management schemes, which use multiple metadata servers (MDS's) to store metadata, provide a highly effective approach to alleviate the workload of a single server. However, it is difficult to maintain good metadata locality and load balancing among MDS's at the same time. In this paper, we propose a novel hashing scheme called AngleCut to partition metadata namespace tree and serve large-scale distributed storage systems. AngleCut first uses a locality preserving hashing (LPH) function to project the namespace tree into linear keyspace, i.e., multiple Chord-like rings. Then we design a history-based allocation strategy to adjust the workload of MDS's dynamically. Besides, we propose a two-layer metadata cache mechanism, including server-side cache and client-side cache to provide the two stage access acceleration. Last but not least, we introduce a distributed metadata processing 2PC Protocol Based on Message Queue (2PC-MQ) to ensure data consistency. In general, our scheme preserves good metadata locality as well as maintains a high load balancing between MDS's. The theoretical proof and extensive experiments on Amazon EC2 demonstrate the superiority of AngleCut over previous literature.

The behavior of metadata server (MDS) cluster is critically important to the overall performance of today's petabyte-scale or even exabyte-scale distributed file system. How to maintain a high level of both system locality and load balancing is a significant challenge to MDS clusters. However, traditional metadata management schemes, including hash-based mapping and subtree partitioning, have severe bias on either system locality or load balancing. In this paper, we propose D2-Tree, a distributed double-layer namespace tree partition scheme, for metadata management in large-scale storage systems. The innovative idea is to design a greedy strategy to split the namespace tree into global layer and local layer subtrees, of which global layer is replicated to maintain load balancing and the lower-half subtrees are allocated separately to MDS's by a mirror division method to preserve locality. Both theoretical analysis based on empirical cumulative distribution and extensive experiments are provided to validate the efficiency of D2-Tree. Experiments using actual trace data on Amazon EC2 also exhibit the superior performance of D2-Tree compared with much previous literature.

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into subwindows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. It is the first algorithm that achieves logarithmic complexity w.r.t. k for incremental maintaining the candidate set even in the worst case.

String similarity join, as an essential operation in applications including data integration and data cleaning, has attracted significant attention in the research community. Previous studies focus on global similarity join. In this paper, we study local similarity join with edit distance constraints, which finds string pairs from two string collections that have similar substrings. We study two kinds of local similarity join problems: checking local similar pairs and locating local similar pairs. We first consider the case where if two strings are locally similar to each other, they must share a common gram of a certain length. We show how to do efficient local similarity verification based on a matching gram pair. We propose two pruning techniques and an incremental method to further improve the efficiency of finding matching gram pairs. Then we devise a method to locate the longest similar substring pair for two local similar strings. We conducted a comprehensive experimental study to evaluate the efficiency of these techniques.

Phrase embedding aims at representing phrases in a vector space and it is important for the performance of many NLP tasks. Existing models only regard a phrase as either full-compositional or non-compositional, while ignoring the hybrid-compositionality that widely exists, especially in long phrases. This drawback prevents them from having a deeper insight into the semantic structure for long phrases and as a consequence, weakens the accuracy of the embeddings. In this paper, we present a novel method for jointly learning compositionality and phrase embedding by adaptively weighting different compositions using an implicit hierarchical structure. Our model has the ability of adaptively adjusting among different compositions without entailing too much model complexity and time cost. To the best of our knowledge, our work is the first effort that considers hybrid-compositionality in phrase embedding. The experimental evaluation demonstrates that our model outperforms state-of-the-art methods in both similarity tasks and analogy tasks.

The problem of k-truss search has been well defined and investigated to find the highly correlated user groups in social networks. But there is no previous study to consider the constraint of users' spatial information in k-truss search, denoted as co-located community search in this paper. The co-located community can serve many real applications. To search the maximum co-located communities efficiently, we first develop an efficient exact algorithm with several pruning techniques. After that, we further develop an approximation algorithm with adjustable accuracy guarantees and explore more effective pruning rules, which can reduce the computational cost significantly. To accelerate the real-time efficiency, we also devise a novel quadtree based index to support the efficient retrieval of users in a region and optimise the search regions with regards to the given query region. Finally, we verify the performance of our proposed algorithms and index using five real datasets.

Recording and querying time-stamped trajectories incurs high cost of data storage and computing. In this paper, we explore several characteristics of the trajectories in road networks, which have motivated the idea of coding trajectories by associating timestamps with relative spatial path and locations. Such a representation contains a large number of duplicate information to achieve a lower entropy compared with the existing representations, thereby drastically cutting the storage cost. We propose several techniques to compress spatial path and locations separately, which can support fast positioning and achieve better compression ratio. For locations, we propose two novel encoding schemes such that the binary code can preserve distance information, which is very helpful for LBS applications. In addition, an unresolved question in this area is whether it is possible to perform a search directly on the compressed trajectories, and if the answer is yes, then how. Here, we show that directly querying compressed trajectories based on our encoding scheme is possible and can be done efficiently. We design a set of primitive operations for this purpose, and propose index structures to reduce query response time. We demonstrate the advantage of our method and compare it against existing ones through a thorough experimental study on real trajectories in road network.

In this paper, we study a novel variant of obstructed nearest neighbor queries, namely,range-based obstructed nearest neighbor(RONN) search. As a natural generalization ofcontinuous obstructed nearest-neighbor(CONN), an RONN query retrieves a set ofobstructed nearest neighborscorresponding to every point in a specified range. We propose a new index, namely binary obstructed tree (calledOB-tree), for indexing complex objects in the obstructed space. The novelty of OB-tree lies in the idea ofdividing the obstructed space into non-obstructed subspaces, aiming to efficiently retrieve highly qualified candidates for RONN processing. We develop an algorithm for construction of the OB-tree and propose a space division scheme, calledoptimal obstacle balance(OOB2) scheme, to address the tree balance problem. Accordingly, we propose an efficient algorithm, calledRONN by OB-tree Acceleration(RONN-OBA), which exploits the OB-tree and a binary traversal order of data objects to accelerate query processing of RONN. In addition, we extend our work in several aspects regarding the shape of obstacles, and range-based$k$NN queries in obstructed space. At last, we conduct a comprehensive performance evaluation using both real and synthetic datasets to validate our ideas and the proposed algorithms. The experimental result shows that the RONN-OBA algorithm outperforms the two R-tree based algorithms and RONN-OA significantly.

Phrase mining is a key research problem for semantic analysis and text-based information retrieval. The existing approaches based on NLP, frequency, and statistics cannot extract high quality phrases and the processing is also time consuming, which are not suitable for dynamic on-line applications. In this paper, we propose an efficient high-quality phrase mining approach (EQPM). To the best of our knowledge, our work is the first effort that considers both intra-cohesion and inter-isolation in mining phrases, which is able to guarantee appropriateness. We also propose a strategy to eliminate order sensitiveness, and ensure the completeness of phrases. We further design efficient algorithms to make the proposed model and strategy feasible. The empirical evaluations on four real data sets demonstrate that our approach achieved a considerable quality improvement and the processing time was 2.3X - 29X faster than the state-of-the-art works.

Detecting social communities in large social networks provides an effective way to analyze the social media users' behaviors and activities. It has drawn extensive attention from both academia and industry. One essential aspect of communities in social networks is outer influence which is the capability to spread internal information of communities to external users. Detecting the communities of high outer influence has particular interest in a wide range of applications, e.g., Ads trending analytics, social opinion mining and news propagation pattern discovery. However, the existing detection techniques largely ignore the outer influence of the communities. To fill the gap, this work investigates the Most Influential Community Search problem to disclose the communities with the highest outer influences. We firstly propose a new community model, maximal kr-Clique community, which has desirable properties, i.e., society, cohesiveness, connectivity, and maximum. Then, we design a novel tree-based index structure, denoted as C-Tree, to maintain the offline computed r-cliques. To efficiently search the most influential communities, we also develop four advanced index-based algorithms which improve the search performance of non-indexed solution by about 200 times. The efficiency and effectiveness of our solution have been extensively verified using six real datasets and a small case study.

This issue of Data Science and Engineering contains a collection of five papers from the APWeb-WAIM 2017, with one additional paper from the regular submissions to the journal.APWeb-WAIM, or the Asia Pacific Web and Web-Age Information Management Joint Conference on Web and Big Data, is an annual international database conference, aiming at attracting professionals of different communities such as industry and academic from not only Asia Pacific countries but also other continents.The objective is to share and exchange ideas, experience and techniques in the area of World Wide Web with the underlying techniques and applications, including Web technologies, database systems, information management, software engineering, and big data.The 2017 edition of APWeb-WAIM was held in Beijing, China, and attracted a total of 240 regular paper submissions, spanning over numerous active and emerging topic areas.The conference program committee selected 44 regular papers and 32 short papers to be presented at the conference and published in the conference proceedings [1].

String similarity join, as an essential operation in applications including data integration and data cleaning, has attracted significant attention in the research community. Previous studies focus on global similarity join. In this paper, we study local similarity join with edit distance constraints, which finds string pairs from two string collections that have similar substrings. We study two kinds of local similarity join problems: checking local similar pairs and locating local similar pairs. We first consider the case where if two strings are locally similar to each other, they must share a common gram of a certain length. We show how to do efficient local similarity verification based on a matching gram pair. We propose two pruning techniques and an incremental method to further improve the efficiency of finding matching gram pairs. Then, we devise a method to locate the longest similar substring pair for two local similar strings. We conducted a comprehensive experimental study to evaluate the efficiency of these techniques.

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on the sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into sub-windows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. To our best knowledge, it is the first algorithm that achieves logarithmic complexity w.r.t. k for incrementally maintaining the candidate set even in the worstcase scenarios.

Recently, answering keyword queries on graph data has drawn a great deal of attention from database communities. However, most graph keyword search solutions proposed so far primarily focus on a single query setting. We observe that for a popular keyword query system, the number of keyword queries received could be substantially large even in a short time interval, and the chance that these queries share common keywords is quite high. Therefore, answering keyword queries in batches would significantly enhance the performance of the system. Motivated by this, this paper studies efficient batch processing for multiple keyword queries on graph data. Realized that finding both the optimal query plan for multiple queries and the optimal query plan for a single keyword query on graph data are computationally hard, we first propose two heuristic approaches which target maximizing keyword overlap and give preferences for processing keywords with short sizes. Then we devise a cardinality based cost estimation model that takes both graph data statistics and search semantics into account. Based on the model, we design an A* based algorithm to find the global optimal execution plan for multiple queries. We evaluate the proposed model and algorithms on two real datasets and the experimental results demonstrate their efficacy.

In this paper, we study a novel variant of obstructed nearest neighbor queries, namely, range-based obstructed nearest neighbor (RONN) search. A natural generalization of continuous obstructed nearest-neighbor (CONN), an RONN query retrieves the obstructed nearest neighbor for every point in a specified range. To process RONN, we first propose a CONN-Based (CONNB) algorithm as our baseline, which reduces the RONN query into a range query and four CONN queries processed using an R-tree. To address the shortcomings of the CONNB algorithm, we then propose a new RONN by R-tree Filtering (RONN-RF) algorithm, which explores effective filtering, also using R-tree. Next, we propose a new index, called O-tree, dedicated for indexing objects in the obstructed space. The novelty of O-tree lies in the idea of dividing the obstructed space into non-obstructed subspaces, aiming to efficiently retrieve highly qualified candidates for RONN processing. We develop an O-tree construction algorithm and propose a space division scheme, called optimal obstacle balance (OOB) scheme, to address the tree balance problem. Accordingly, we propose an efficient algorithm, called RONN by O-tree Acceleration (RONN-OA), which exploits O-tree to accelerate query processing of RONN. In addition, we extend O-tree for indexing polygons. At last, we conduct a comprehensive performance evaluation using both real and synthetic datasets to validate our ideas and the proposed algorithms. The experimental result shows that the RONN-OA algorithm outperforms the two R-tree based algorithms significantly. Moreover, we show that the OOB scheme achieves the best tree balance in O-tree and outperforms two baseline schemes.

The problem of finding matches of a regular expression (RE) on a string exists in many applications, such as text editing, biosequence search, and shell commands. Existing techniques first identify candidates using substrings in the RE, then verify each of them using an automaton. These techniques become inefficient when there are many candidate occurrences that need to be verified. In this article, we propose a novel technique that prunes false negatives by utilizing negative factors , which are substrings that cannot appear in an answer. A main advantage of the technique is that it can be integrated with many existing algorithms to improve their efficiency significantly. We present a detailed description of this technique. We develop an efficient algorithm that utilizes negative factors to prune candidates, then improve it by using bit operations to process negative factors in parallel. We show that negative factors, when used with necessary factors (substrings that must appear in each answer), can achieve much better pruning power. We analyze the large number of negative factors, and develop an algorithm for finding a small number of high-quality negative factors. We conducted a thorough experimental study of this technique on real datasets, including DNA sequences, proteins, and text documents, and show significant performance improvement of the state-of-the-art tools by an order of magnitude.

We study efficient query processing for approximate string queries, which find strings within a string collection whose edit distances to the query strings are within the given thresholds. Existing methods typically hinge on the property that globally similar strings must share at least certain number of identical substrings or subsequences. They become ineffective when there are burst errors or when the number of errors is large. In this paper, we explore the opposite paradigm focusing on finding out the differences of database strings to the query string. We propose a new filtering method, called local filtering, based on the idea that two strings exhibiting substantial local dissimilarities must be globally dissimilar. We propose the concept of (positional) local distance to quantify the minimum amount of errors a query fragment contributes to the edit distance between the query and a data string. It also leads to effective pruning rules and can speed up verification via early termination. We devise a family of indexing methods based on the idea of precomputing (positional) local distances for all possible combinations of query fragments and edit distance thresholds. Based on careful analyses of subtle relationships among local distances, novel techniques are proposed to drastically reduce the amount of enumeration with no or little impact on the pruning power. Efficient query processing methods exploiting the new index and bit-parallelism are also proposed. Experimental results on real datasets show that our local filtering-based methods can achieve substantial speedup compared with state-of-the-art methods, and they are robust against factors such as dataset characteristics and large edit distance thresholds.

ABSTRACT The increasing popularity of social networks in various application domains has raised privacy concerns for the individuals involved. In this work, we formally present the definition of profile privacy leakage, which is a newly identified privacy leakage in social networks. However, applying existing methods straightforwardly cannot provide efficient privacy protection for the profiles meanwhile incurring a large amount of information loss. We propose k‐obfuscation to protect profiles against graph property based attacks. We develop a general framework for obtaining k‐obfuscation. In this framework, we propose a novel safe vertex‐profile mapping mechanism, named as k‐mapping. We also design a number of techniques to make the k‐mapping method efficient meanwhile maintaining the data utilities. Extensive experiments on real datasets show the satisfactory performance of our methods in terms of privacy protection, efficiency, and practical utilities. Copyright © 2014 John Wiley & Sons, Ltd.

ABSTRACT The prevalence of social networks has raised the concern for individual privacy leakage. Although preserving user privacy in social networks has been studied extensively, there is still a lot of room for improvement in the state of the art techniques. For example, the recently proposed K‐automorphism model can prevent node identity attack by constructing a K‐automorphism graph; however, it ignores preserving the privacy of the edges, resulting in path length leakage and edge leakage in the anonymous graph. Another example is the K‐isomorphism model, which was proposed to improve the K‐automorphism model by transforming the graph of social networks into K disjoined isomorphic subgraphs. However, it cuts off the connection among subgraphs, which impairs the data utility of the released anonymous graph. In this paper, we design a secure and high utility privacy preserving model, called AK‐secure, to prevent node identity attack, path length leakage, and edge leakage effectively. On the basis of the AK‐secure privacy preserving model, we propose a graph anonymous algorithm, which constructs an anonymous graph satisfying the AK‐secure privacy preserving model, minimizing information loss and guaranteeing high data utility. Extensive experiments on real data sets show the security, effectiveness of our AK‐secure privacy preserving model and the high data utility of the released anonymous graph. Copyright © 2013 John Wiley & Sons, Ltd.

The goal of graph anonymization is avoiding disclosure of privacy in social networks through graph modifications meanwhile preserving data utility of the anonymized graph for social network analysis. Graph reachability is an important data utility as reachability queries are not only common on graph databases, but also serving as fundamental operations for many other graph queries. However, the graph reachability is severely distorted after the anonymization. In this paper, we solve this problem by designing a reachability preserving anonymization (RPA for short) algorithm. The main idea of RPA is to organize vertices into groups and greedily anonymizes each vertex with low anonymization cost on reachability. We propose the reachable interval to efficiently measure the anonymization cost incurred by an edge addition, which guarantees the high efficiency of RPA. Extensive experiments illustrate that anonymized social networks generated by our methods preserve high utility on reachability.

The explosive growth in the amount of data produced by next-generation sequencing poses significant computational challenges on how to store, transmit and query these data, efficiently and accurately. A unique characteristic of the genomic sequence data is that many of them can be highly similar to each other, which has motivated the idea of compressing sequence data by storing only their differences to a reference sequence, thereby drastically cutting the storage cost. However, an unresolved question in this area is whether it is possible to perform search directly on the compressed data, and if so, how. Here we show that directly querying compressed genomic sequence data is possible and can be done efficiently. We describe a set of novel index structures and algorithms for this purpose, and present several optimization techniques to reduce the space requirement and query response time. We demonstrate the advantage of our method and compare it against existing ones through a thorough experimental study on real genomic data.

The problem of finding matches of a regular expression (RE) on a string exists in many applications such as text editing, biosequence search, and shell commands. Existing techniques first identify candidates using substrings in the RE, then verify each of them using an automaton. These techniques become inefficient when there are many candidate occurrences that need to be verified. In this paper we propose a novel technique that prunes false negatives by utilizing negative factors, which are substrings that cannot appear in an answer. A main advantage of the technique is that it can be integrated with many existing algorithms to improve their efficiency significantly. We give a full specification of this technique. We develop an efficient algorithm that utilizes negative factors to prune candidates, then improve it by using bit operations to process negative factors in parallel. We show that negative factors, when used together with necessary factors (substrings that must appear in each answer), can achieve much better pruning power. We analyze the large number of negative factors, and develop an algorithm for finding a small number of high-quality negative factors. We conducted a thorough experimental study of this technique on real data sets, including DNA sequences, proteins, and text documents, and show the significant performance improvement when applying the technique in existing algorithms. For instance, it improved the search speed of the popular Gnu Grep tool by 11 to 74 times for text documents.

With the exponential increment of data, compression technology becomes an important tool in the field of data management, especially in text management. An increasing pressing challenge is how to efficiently query these massive amounts of sequence data in their compressed format. In this paper we study the problem of answering subsequence-search queries on LZ78 format of texts. We propose the concept of conditional common sub strings of queries to improve query performance. We present a techniques to find minimal conditional common sub strings in compressed text and a local uncompressing technique to verify and locate positions of answers in text. Finally, the experimental results over real data demonstrate the efficiency of our algorithm.

We study the problem of local alignment, which is finding pairs of similar subsequences with gaps. The problem exists in biosequence databases. BLAST is a typical software for finding local alignment based on heuristic, but could miss results. Using the Smith-Waterman algorithm, we can find all local alignments in O( mn ) time, where m and n are lengths of a query and a text, respectively. A recent exact approach BWT-SW improves the complexity of the Smith-Waterman algorithm under constraints, but still much slower than BLAST. This paper takes on the challenge of designing an accurate and efficient algorithm for evaluating local-alignment searches, especially for long queries. In this paper, we propose an efficient software called ALAE to speed up BWT-SW using a compressed suffix array. ALAE utilizes a family of filtering techniques to prune meaningless calculations and an algorithm for reusing score calculations. We also give a mathematical analysis and show that the upper bound of the total number of calculated entries using ALAE could vary from 4.50 mn 0.520 to 9.05 mn 0.896 for random DNA sequences and vary from 8.28 mn 0.364 to 7.49 mn 0.723 for random protein sequences. We demonstrate the significant performance improvement of ALAE on BWT-SW using a thorough experimental study on real biosequences. ALAE guarantees correctness and accelerates BLAST for most of parameters.

The graph structure is a very important means to model schemaless data with complicated structures, such as protein-protein interaction networks, chemical compounds, knowledge query inferring systems, and road networks. This paper focuses on the index structure for similarity search on a set of large sparse graphs and proposes an efficient indexing mechanism by introducing the Q-Gram idea. By decomposing graphs to small grams (organized by κ-Adjacent Tree patterns) and pairing-up on those κ-Adjacent Tree patterns, the lower bound estimation of their edit distance can be calculated for candidate filtering. Furthermore, we have developed a series of techniques for inverted index construction and online query processing. By building the candidate set for the query graph before the exact edit distance calculation, the number of graphs need to proceed into exact matching can be greatly reduced. Extensive experiments on real and synthetic data sets have been conducted to show the effectiveness and efficiency of the proposed indexing mechanism.

Approximate queries on a collection of strings are important in many applications such as record linkage, spell checking, and Web search, where inconsistencies and errors exist in data as well as queries. Several existing algorithms use the concept of "grams," which are substrings of strings used as signatures for the strings to build index structures. A recently proposed technique, called VGRAM, improves the performance of these algorithms by using a carefully chosen dictionary of variable-length grams based on their requencies in the string collection. Since an index structure using fixed-length grams can be viewed as a special case of VGRAM, a fundamental problem arises naturally: what is the relationship between the gram dictionary and the performance of queries? We study this problem in this paper. We propose a dynamic programming algorithm for computing a tight lower bound on the number of common grams shared by two similar strings in order to improve query performance. We analyze how a gram dictionary affects the index structure of the string collection and ultimately the performance of queries. We also propose an algorithm for automatically computing a dictionary of high-quality grams for a workload of queries. Our experiments on real data sets show the improvement on query performance achieved by these techniques. To our best knowledge, this study is the first cost-based quantitative approach to deciding good grams for approximate string queries.

In data publishing, if the data is published carelessly, public users could use common knowledge to infer more information from the published data, causing leakage of sensitive information. To address related research challenges, we develop a system called XGuard, which can help data owners publish a partial XML document without leaking sensitive information, even if public users can do inference. Specifically, the system has the following functionalities. i) It allows the data owner to define sensitive information and specify common knowledge as XML constraints. ii) Given a partial document, the system can validate if the document can cause information leakage due to common knowledge and how much data can be leaked. iii) The system can help the data owner interactively analyze the data inference and produce a secure valid partial document using the algorithms.

As the Internet is a global network, there is a demand on accessing closely related data without browsing through different Web documents. A significant amount of these data are presented in HTML documents. Since data contents of HTML documents are intervened by markups, it is not trivial to integrate and provide a unified view of closely related data in different HTML documents. In this paper we present an approach for integrating semantically related data in any HTML tables that belong to a particular domain of interest (ID), such as house/apartment rental, by using the semantic hierarchies generated from the tables and the predefined meta-data sets that indicate related column names in ID. In our approach, we capture each data source as semi-structured data, called semantic hierarchy, and the end result of integrating different HTML tables of ID is a unified view of data in the tables, which is presented in an XML document. Besides HTML tables, our approach can be adopted by any system that integrates semi-structured data across different platforms.