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.

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.

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.

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.

Abstract Social recommendation often incorporates trusted social links with user-item interactions to enhance rating prediction. Although methods that aggregate explicit social links have shown promising prospects, they are often constrained by the absence of explicit social data and the assumption of homogeneity, thus overlooking variations in social influence and consistency. These limitations hinder semantic expression and recommendation performance. Therefore, we propose a novel framework for social recommendation. First, we design a bipartite network embedding scheme, which learns vertex representations in the embedding space by modeling 1st-order explicit relations and higher-order implicit relations between vertices. Then, the similarity of the embedding vectors is used to extract top-k semantically consistent friends for each user. Next, we design an algorithm to assign a specific influence value to each user. Finally, we combine the top-k friends of the user and their influence values into an ensemble and add it as a regularization term to the rating prediction process of the user to correct the bias. Experiments on three real benchmark datasets show significant improvements in EISF over state-of-the-art methods.

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+.

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.

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.

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.

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.

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.

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.

Clustering is a popular technique for analyzing microarray data sets, with n genes and m experimental conditions. As explored by biologists, there is a real need to identify coregulated gene clusters, which include both positive and negative regulated gene clusters. The existing pattern-based and tendency-based clustering approaches cannot directly be applied to find such coregulated gene clusters, because they are designed for finding positive regulated gene clusters. In this paper, in order to cluster coregulated genes, we propose a coding scheme that allows us to cluster two genes into the same cluster if they have the same code, where two genes that have the same code can be either positive or negative regulated. Based on the coding scheme, we propose a new algorithm for finding maximal subspace coregulated gene clusters with new pruning techniques. A maximal subspace coregulated gene cluster clusters a set of genes on a condition sequence such that the cluster is not included in any other subspace coregulated gene clusters. We conduct extensive experimental studies. Our approach can effectively and efficiently find maximal subspace coregulated gene clusters. In addition, our approach outperforms the existing approaches for finding positive regulated gene clusters.