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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.