In the current era of data-intensive applications, the demand for high-performance, cost-effective storage solutions is paramount. This paper introduces a Space-Performance Cost Model for key-value store, designed to guide cost-effective storage configuration decisions. The model quantifies the trade-offs between performance and storage costs, providing a framework for optimizing resource allocation in large-scale data serving environments. Guided by this cost model, we present Tier-Base, a distributed key-value store developed by Ant Group that optimizes total cost by strategically synchronizing data between cache and storage tiers, maximizing resource utilization and effectively handling skewed workloads. To enhance cost-efficiency, TierBase incorporates several optimization techniques, including pre-trained data compression, elastic threading mechanisms, and the utilization of persistent memory. We detail TierBase's architecture, key components, and the implementation of cost optimization strategies. Extensive evaluations using both synthetic benchmarks and real-world workloads demonstrate TierBase's superior cost-effectiveness compared to existing solutions. Furthermore, case studies from Ant Group's production environments showcase TierBase's ability to achieve up to 62% cost reduction in primary scenarios, highlighting its practical impact in large-scale online data serving.

Log data is a vital resource for capturing system events and states. With the increasing complexity and widespread adoption of modern software systems and IoT devices, the daily volume of log generation has surged to tens of petabytes, leading to significant collection and storage costs. To address this challenge, lossless log compression has emerged as an effective solution, enabling substantial resource savings without compromising log information. In this paper, we first conduct a characterization study on extensive public log datasets and identify four key observations. Building on these insights, we propose LogLite, a lightweight, plug-and-play, streaming lossless compression algorithm designed to handle both TEXT and JSON logs throughout their life cycle. LogLite requires no predefined rules or pre-training and is inherently adaptable to evolving log structures. Our evaluation shows that, compared to state-of-the-art baselines, LogLite achieves Pareto optimality in most scenarios, delivering an average improvement of up to 67.8% in compression ratio and up to 2.7X in compression speed.

The advancement in location technology and the increase in trajectory data have made trajectory data mining a focal point in the field of spatiotemporal data analysis. Unlike the extensive research focused on the similarity of entire trajectories, this paper delves into subtrajectory similarity within collections containing a large number of trajectories, under a specified trajectory similarity metric. We propose the Top-k Representative Similar Subtrajectory Query problem, with the objective of identifying the top-k representative subtrajectories which are most similar to the query trajectory within a large trajectory set. To ensure diversity in the results, we adopt the concept of representative similarity, where only the subtrajectory with the highest similarity score to the query trajectory is reported, thus avoiding the redundancy in the top-$k$results. To address the challenge of high computational costs, we propose a learning-based framework, leveraging a deep learning model called Representative Similarity Score Estimation (RSSE) to approximate subtrajectory similarity scores efficiently and reduce the candidate set significantly. Empirical evaluations conducted on various real-world datasets substantiate the effectiveness and efficiency of our proposed method.

Recently, transportation-as-a-service (TaaS) becomes an increasing trend, and online taxi platforms start to apply electric vehicles to serve passengers. Since the recharging time of an electric vehicle is long and non-negligible, it is necessary to smartly arrange the recharging schedules of electric vehicles in working schedules. In order to maximize the number of served taxi-calling tasks, online taxi platforms assign electric vehicles whose remaining electric power is enough to serve the dynamically arriving taxi-calling tasks and schedule suitable idle vehicles to recharging piles to recharge. We formally define the power-aware electric vehicle assignment (PAEVA) problem to serve as many taxi-calling tasks as possible under the constraints of remaining electric power and deadline. We prove that the PAEVA problem is NP-hard. To solve PAEVA, we design a novel strategy to help arrange the schedules of electric vehicles. Specifically, the strategy requires that, in a time slot and an area gird, the ratio of the number of electric vehicles whose remaining electric power is higher than a threshold$\alpha$to the number of predicted taxi-calling tasks should be higher than a threshold$\beta$. We propose two approximation approaches with theoretical guarantees to adaptively determine the values of the two thresholds of the strategy. We evaluate our solutions’ effectiveness and efficiency by comprehensive experiments on real datasets.

Computing Multi-source Shortest Path query with Assembly points ($\mathsf {MSPA}$) is a fundamental graph problem. The$\mathsf {MSPA}$problem locates a set of assembly points to minimize the overall distance for transporting objects from different sources to a destination, where we can assemble objects at assembly points to reduce the total cost. We prove that the$\mathsf {MSPA}$problem is NP-hard. The intuitive method for computing the optimal set of assembly points and the corresponding set of paths is by Branch-and-Bound. However, the combination of different assembly points is exponential. By analyzing the structure of the path set based on the proposed distance graph, we find that the used paths can be combined into a tree. Hence, by defining the state of subtrees and the state transition equation, we propose a dynamic programming (DP) algorithm by pruning the redundant computation of subtrees. The experiment shows that the DP algorithm can achieve three orders of magnitude speedup in query processing time compared with the optimized Branch-and-Bound algorithm. Moreover, we reduce the transition candidates of the DP algorithm from the entire vertex set to certain neighbors. Extensive experiments are conducted on different types of real-world networks to demonstrate the performance of our DP algorithm.

As a fundamental graph problem, community search is applied in various areas, e.g., social networks, the world wide web, and biology. A common requirement from real applications is to return a community with a bounded size while most existing solutions do not constrain community size. Recent studies on size-constrained community search still have some critical issues, e.g., the existence of a better cohesiveness objective, some queries returning empty results, and inefficiency on partial queries. Thus, in this paper, we study the size-constrained truss community search (STCS). Given a graph$G$, a query vertex$q$, and size constraint$[l,h]$, the STCS problem aims to find a subgraph containing$q$with the largest min-support among all connected subgraphs having at least$l$and at most$h$vertices. We prove the STCS problem is NP-hard and APX-hard unless P = NP. An effective heuristic is proposed to quickly find a high-quality initial result. Then, a branch and bound algorithm is introduced to find the exact result, with novel optimizations, e.g., budget-cost-based bounding and branching strategies. Extensive experiments verify that the community quality returned by our algorithm is better and our algorithm is faster by up to 5 orders of magnitude, compared with the state-of-the-art.

Set intersection is a fundamental operation in many applications, such as common neighbor computation in graph-based algorithms, set similarity computation, item recommendation, etc. In the literature, many set intersection methods are proposed. We observe that the state-of-the-art algorithm${\sf RCode}$bears several limitations, such as high index time complexity, inefficient for large-sized sets, and not friendly to the generic set intersection. In this paper, we introduce theBucket Signature forSet(${\sf BigSet}$), an efficient generic set intersection algorithm.${\sf BigSet}$consists of two phases, namely the preprocessing phase and the query phase. In the preprocessing phase,${\sf BigSet}$partitions the elements of a record into$O(2^{k})$buckets and uses a bitmap to indicate the status of the buckets where$n$is the record length and$k$is the number of bits in the signature. In the query phase,${\sf BigSet}$calculates the results using a candidate generating-and-verification framework. Specifically, a set of candidate elements is identified as those falling in the same buckets. Then, for each bucket,${\sf BigSet}$collects the common elements using a merge-based method. To improve the performance, we introduce two optimizations, including bucket sharing and size-aware signature construction techniques. We conduct experiments on 10 real graph datasets and 5 real generic set datasets to evaluate the performance of our proposals. The experiment results show that${\sf BigSet}$is 20× faster than the leading generic set intersection algorithms. Besides it outperforms the${\sf RCode}$with 5× speedup, and while uses up to 8× less memory.

Hop-constrained s-t simple path (k-st path) enumeration is a fundamental problem in graph databases and plays an important role in many real-world applications. Given a dynamic graph G, a source-target pair s-t, and a hop constraint k, we aim to efficiently compute k-st paths: list all simple paths within length k from s to t, and then continuously maintain the results against edge updates. Although the k-st path enumeration has been well studied in static setting, the existing works on static graphs cannot be applied or adapted to handle dynamic graphs efficiently. To address the challenges on dynamic computation, we propose a partial path-based index structure and an efficient enumeration algorithm based on the index. We also propose several well-designed techniques to efficiently maintain the index and locate the affected results with graph updates. Comprehensive experiments verify that our proposed CPEupdatealgorithm outperforms the state-of-the-art methods by up to 4 orders of magnitude on dynamic graphs. The experiment results also show that the time cost of our initialization step CPEstartup(including index construction) is similar to the state-of-the-art static method.

Machine-generated data is rapidly growing and poses challenges for data-intensive systems, especially as the growth of data outpaces the growth of storage space. To cope with the storage issue, compression plays a critical role in storage engines, particularly for data-intensive applications, where a high compression ratio and efficient random access are essential. However, existing compression techniques tend to focus on general-purpose and data block approaches, but overlook the inherent structure of machine-generated data and hence result in low compression ratios or limited lookup efficiency. To address these limitations, we introduce the Pattern-Based Compression (PBC) algorithm, which specifically targets patterns in machine-generated data to achieve Pareto-optimality in most cases. Unlike traditional data block-based methods, PBC compresses data on a per-record basis, facilitating rapid random access. Our experimental evaluation demonstrates that PBC, on average, achieves a compression ratio twice as high as the state-of-the-art techniques while maintaining competitive compression and decompression speeds. We also integrate PBC to a production database system and achieve improvements on both comparison ratio and throughput.

In this article, we study the problem of maximal biclique enumeration on large uncertain bipartite graphs. Given an uncertain bipartite graph$\mathcal {G}=(U,V,E,p)$, a probability threshold$\tau$, and two size constraints$\alpha$and$\beta$, we aim to efficiently enumerate all maximal$\tau$-bicliques in$\mathcal {G}$, where a maximal$\tau$-biclique$B(L,R)$is a complete subgraph of$\mathcal {G}$with (1) the probability of$B$is no less than$\tau$, (2)$|L| \geq \alpha$and$|R| \geq \beta$, and (3)$B$is a maximal complete subgraph satisfying (1) and (2). This problem has many applications, such as biclustering of gene expression data, fraud detection, similar group identification, etc. Despite the wide range of applications, to the best of our knowledge, we note that there are no efficient and scalable solutions to this problem in the literature. This problem is computationally challenging due to its #P-completeness. In this article, we propose a competitive branch-and-bound method, namely${\sf MBEN}$, which explores the search space in a depth-first manner with a variety of pruning techniques. To improve the performance of${\sf MBEN}$, we propose several novel and efficient search processing optimizations. First, we always select the side with fewer candidates to expand the search space. With this search strategy, we have a chance to prune the fruitless branches early. Second, we devise an advanced pruning technique by considering the size pruning and probability pruning at the same time to boost the pruning capacity. Last, we implement${\sf MBEN}$with pre-allocated arrays and pointer maintaining techniques such that the frequent work sets creating operations can be substituted by array element switching operations. In addition, we introduce useful graph reduction techniques to further accelerate the computation. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by more than two orders of magnitude.

The existence of anomalies is quite common, but they are hidden within the complex structure and high-dimensional node attributes of the attributed networks. As a latent hazard in existing systems, anomalies can be transformed into important instruction information once we detect them, e.g., computer network admins can react to the leakage of sensitive data if network traffic anomalies are identified. Extensive research in anomaly detection on attributed networks has proposed various techniques, which do improve the quality of data in networks, while they rarely cope with the few-shot anomaly detection problem. Few-shot anomaly detection task with only a few dozen labeled anomalies is more practical since anomalies are rare in number for real-world systems.

Structural clustering (SCAN) is one of the most popular graph clustering paradigms. However, SCAN assumes that the input graph is undirected and can not cluster the directed graphs. To address this problem, in this paper, we propose a new structural clustering model based on SCAN to cluster directed graphs. Following the new model, we propose an index-based approach to support the efficient clustering of a given graph. Moreover, we also devise efficient index maintenance algorithms to handle the case that the input graph is dynamically updated. We conduct extensive experiments on nine real directed graphs, one of which contains more than 2 billion edges. The results demonstrate the effectiveness and efficiency of our proposed methods.

Multilayer graphs are very powerful in representing the multiplex relationships among entities. The truss decomposition on single-layer graphs is a well-studied problem which divides a graph into a hierarchy structure, and has a series of applications. However, little attention has been paid to the truss decomposition on multilayer graphs. In addition, truss decomposition on multilayer graphs derives new challenges compared to the scenario on single-layer graphs. In this paper, we devise an efficient algorithm to compute the truss decomposition on multilayer graphs. Extensive experiments on 5 real-life datasets validate the effectiveness and efficiency of our methods.

Subgraph matching is a basic operation widely used in many applications. However, due to its NP-hardness and the explosive growth of graph data, it is challenging to compute subgraph matching, especially in large graphs. In this paper, we aim at scaling up subgraph matching on a single machine using FPGAs. Specifically, we propose a CPU-FPGA co-designed framework. On the CPU side, we first develop a novel auxiliary data structure called candidate search tree (CST) which serves as a complete search space of subgraph matching. CST can be partitioned and fully loaded into FPGAs' on-chip memory. Then, a workload estimation technique is proposed to balance the load between the CPU and FPGA. On the FPGA side, we design and implement the first FPGA-based subgraph matching algorithm, called FAST. To take full advantage of the pipeline mechanism on FPGAs, task parallelism optimization and task generator separation strategy are proposed for FAST, achieving massive parallelism. Moreover, we carefully develop a BRAM-only matching process to fully utilize FPGA's on-chip memory, which avoids the expensive intermediate data transfer between FPGA's BRAM and DRAM. Comprehensive experiments show that FAST achieves up to 462.0x and 150.0x speedup compared with the state-of-the-art algorithm DAF and CECI, respectively. In addition, FAST is the only algorithm that can handle the billion-scale graph using one machine in our experiments.

Graph plays a vital role in representing entities and their relationships in a variety of fields, such as e-commerce networks, social networks and biological networks. Given two verticessandt, one of the fundamental problems in graph databases is to investigate the relationships betweensandt. A well-studied problem in such area is k-hop constraineds-tsimple path enumeration. Nevertheless, all existing algorithms targeting this problem follow the DFS-based paradigm, which cannot scale up well. Moreover, using hardware devices like FPGA to accelerate graph computation has become popular. Motivated by this, in this paper, we propose the first FPGA-based algorithm PEFP to solve the problem of k-hop constrained s-t simple path enumeration efficiently. On the host side, we propose a preprocessing algorithm Pre-BFS to reduce the graph size and search space. On the FPGA side in PEFP, we propose a novel DFS-based batching technique to save on-chip memory efficiently. In addition, we also propose caching techniques to cache necessary data in BRAM, which overcome the latency bottleneck brought by the read/write operations from/to FPGA DRAM. Finally, we propose a data separation technique to enable dataflow optimization for the path verification module; hence the sub-stages in that module can be executed in parallel. Comprehensive experiments show that PEFP outperforms the state-of-the-art algorithm JOIN by more than 1 order of magnitude by average, and up to 2 orders of magnitude in terms of preprocessing time, query processing time and total time, respectively.

Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this demonstration, we present IndoorViz, a new indoor spatial data management system that integrates three novel index structures proposed in [4] and [6] with well designed query processing algorithms and 3D visualization functions. The IndoorViz is able to support indoor spatial object indexing, efficient query processing and interactive 3D display.

We are pleased to present a special issue of Data Science and Engineering (DSE), which contains a collection of six extended papers from the APWeb-WAIM 2020 conference.We also include a regular submission paper in this issueAPWeb-WAIM conferences focus on research, development, and applications in relation to Web information management, including a wide range of topics, such as text analysis, graph data processing, social networks, recommender systems, information retrieval, data streams, knowledge graph, data mining and application, query processing, machine learning, database and Web applications, big data, and blockchain.

Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this paper, we first propose two novel indexes called Indoor Partitioning Tree (IP-Tree) and Vivid IP-Tree (VIP-Tree) that are carefully designed by utilizing the properties of indoor venues. The proposed indexes are lightweight, have small pre-processing cost and provide near-optimal performance for shortest distance and shortest path queries. We are also the first to study spatial keyword queries in indoor venues. We propose a novel data structure called Keyword Partitioning Tree (KP-Tree) that indexes objects in an indoor partition. We propose an efficient algorithm based on VIP-Tree and KP-Trees to efficiently answer spatial keyword queries. Our extensive experimental study on real and synthetic data sets demonstrates that our proposed indexes outperform the existing solutions by several orders of magnitude.

Given a set of facilities and a set of users, a reverse nearest neighbors (RNN) query retrieves every user$u$for which the query facility$q$is its closest facility. Since$q$is the closest facility to$u$, the user$u$is said to be influenced by$q$. In this paper, we propose arelaxeddefinition of influence where a user$u$is said to be influenced by not only its closest facility but also every other facility that isalmostas close to$u$as its closest facility is. Based on this definition of influence, we propose reverse approximate nearest neighbors (RANN) queries. Formally, given a value$x>1$, an RANN query$q$returns every user$u$for which$dist(u,q) \leq x\times NNDist(u)$where$NNDist(u)$denotes the distance between a user$u$and its nearest facility, i.e.,$q$is an approximate nearest neighbor of$u$. In this paper, we study bothsnapshotandcontinuousversions of RANN queries. In a snapshot RANN query, the underlying data sets do not change and the results of a query are to be computed only once. In the continuous version, the users continuously change their locations and the results of RANN queries are to be continuously monitored. Based on effective pruning techniques and several non-trivial observations, we propose efficient RANN query processing algorithms for both the snapshot and continuous RANN queries. We conduct extensive experiments on both real and synthetic data sets and demonstrate that our algorithm for both snapshot and continuous queries are significantly better than the competitors.

In this paper, we study the problem of set containment join. Given two collections R and S of records, the set containment join R ∞I⊆ S retrieves all record pairs {(r, s)} ∈ R × S such that r ⊆ s. This problem has been extensively studied in the literature and has many important applications in commercial and scientific fields. Recent research focuses on the in-memory set containment join algorithms, and several techniques have been developed following intersection-oriented or union-oriented computing paradigms. Nevertheless, we observe that two computing paradigms have their limits due to the nature of the intersection and union operators. Particularly, intersection-oriented method relies on the intersection of the relevant inverted lists built on the elements of S. A nice property of the intersection-oriented method is that the join computation is verification free. However, the number of records explored during the join process may be large because there are multiple replicas for each record in S. On the other hand, the union-oriented method generates a signature for each record in R and the candidate pairs are obtained by the union of the inverted lists of the relevant signatures. The candidate size of the union-oriented method is usually small because each record contributes only one replica in the index. Unfortunately, union-oriented method needs to verify the candidate pairs, which may be cost expensive especially when the join result size is large. As a matter of fact, the state-of-the-art union-oriented solution is not competitive compared to the intersection-oriented ones. In this paper, we propose a new union-oriented method, namely TT-Join, which not only enhances the advantage of the previous union-oriented methods but also integrates the goodness of intersection-oriented methods by imposing a variant of prefix tree structure. We conduct extensive experiments on 20 real-life datasets by comparing our method with 7 existing methods. The experiment results demonstrate that TT-Join significantly outperforms the existing algorithms on most of the datasets, and can achieve up to two orders of magnitude speedup.

We study the problem of structural graph clustering, a fundamental problem in managing and analyzing graph data. Given an undirected unweighted graph, structural graph clustering is to assign vertices to clusters, and to identify the sets of hub vertices and outlier vertices as well, such that vertices in the same cluster are densely connected to each other while vertices in different clusters are loosely connected. In this paper, we develop a new two-step paradigm for scalable structural graph clustering based on our three observations. Then, we present a pSCAN approach, within the paradigm, aiming to reduce the number of structural similarity computations, and propose optimization techniques to speed up checking whether two vertices are structure-similar. pSCAN outputs exactly the same clusters as the existing approaches SCAN and SCAN++, and we prove that pSCAN is worst-case optimal. Moreover, we propose efficient techniques for updating the clusters when the input graph dynamically changes, and we also extend our techniques to other similarity measures, e.g., Jaccard similarity. Performance studies on large real and synthetic graphs demonstrate the efficiency of our new approach and our dynamic cluster maintenance techniques. Noticeably, for the twitter graph with 1 billion edges, our approach takes 25 minutes while the state-of-the-art approach cannot finish even after 24 hours.

Given a set of users, a set of facilities and a query facility q , a reverse k nearest neighbors (R k NN) query returns every user u for which the query is one of its k closest facilities. R k NN queries have been extensively studied under a variety of settings and many sophisticated algorithms have been proposed to answer these queries. However, the existing experimental studies suffer from a few limitations. For example, some studies estimate the I/O cost by charging a fixed penalty per I/O and we show that this may be misleading. Also, the existing studies either use an extremely small buffer or no buffer at all which puts some algorithms at serious disadvantage. We show that the performance of these algorithms is significantly improved even when a small buffer (containing 100 pages) is used. Finally, in each of the existing studies, the proposed algorithm is mainly compared only with its predecessor assuming that it was the best algorithm at the time which is not necessarily true as shown in our experimental study. Motivated by these limitations, we present a comprehensive experimental study that addresses these limitations and compares some of the most notable algorithms under a wide variety of settings. Furthermore, we also present a carefully developed filtering strategy that significantly improves TPL which is one of the most popular R k NN algorithms. Specifically, the optimized version is up to 20 times faster than the original version and reduces its I/O cost up to two times.

Given a set of facilities and a set of users, a reverse k nearest neighbors (RkNN) query q returns every user for which the query facility is one of the k-closest facilities. Due to its importance, RkNN query has received significant research attention in the past few years. Almost all of the existing techniques adopt a pruning-and-verification framework. Regions-based pruning and half-space pruning are the two most notable pruning strategies. The half-space based approach prunes a larger area and is generally believed to be superior. Influenced by this perception, almost all existing RkNN algorithms utilize and improve the half-space pruning strategy. We observe the weaknesses and strengths of both strategies and discover that the regions-based pruning has certain strengths that have not been exploited in the past. Motivated by this, we present a new RkNN algorithm called SLICE that utilizes the strength of regions-based pruning and overcomes its limitations. Our extensive experimental study on synthetic and real data sets demonstrate that SLICE is significantly more efficient than the existing algorithms. We also provide a detailed theoretical analysis to analyze various aspects of our algorithm such as I/O cost, the unpruned area, and the cost of its verification phase etc. The experimental study validates our theoretical analysis.