Multi-vector retrieval models (e.g., ColBERTv2) offer high retrieval accuracy but suffer from efficiency problems at scale. Recently, several methods have been developed to enhance the efficiency of multi-vector retrieval. On one hand, the state-of-the-art GPU-based method PLAID-GPU exploits the massive parallelism of the GPU to accelerate computation, but it needs to process a considerable amount (e.g., ten thousand) of document candidates. On the other hand, the state-of-the-art (SOTA) CPU-based method IGP employs a more effective strategy to reduce the number of candidates, but fails to utilize the massive parallelism of the GPU. To get the best of both worlds, we propose GIGP+, a GPU-based method designed to achieve high parallelism and low computational overhead. Our contributions are: (1) an efficient candidate generation kernel that enjoys parallelism while retaining the effectiveness of IGP, (2) a score reordering mechanism that reduces the synchronization overhead and (3) a scheduling strategy for efficient batch processing. Our experiments demonstrate that GIGP+ achieves a 11.0× improvement in query per second (QPS) and reduces latency by 7.6× compared to PLAID-GPU, while maintaining equivalent retrieval accuracy. As for cloud pricing, GIGP+ delivers a 2.3× improvement in queries per dollar over SOTA CPU-based solutions.

Cross-modal Approximate Nearest Neighbor Search (ANNS) is crucial for a growing number of applications, including search engines and recommendation systems.However, existing vector search indexes often struggle with either poor search efficiency or slow index construction when handling cross-modal ANNS queries.To overcome these limitations, we introduce ParaGraph, a CPU-GPU co-processing system that enhances both search efficiency and construction speed for cross-modal ANNS.ParaGraph employs novel multi-round top-𝑚 projection and batched search-and-refine techniques for index construction.Additionally, it leverages modern heterogeneous hardware architectures by distributing computationally distinct tasks across the GPU and CPU, augmented with in-depth optimizations to maximize parallelism and performance.Compared to the state-of-the-art cross-modal ANNS index, Para-Graph achieves a 4.1× to 4.9× speedup in index construction and a 50% reduction in index size, while maintaining search efficiency.

Neural embedding models are extensively employed in retrieval applications, including passage retrieval, question answering, and web search. In particular, multi-vector models (e.g., ColBERTv2), which represent a document as multiple embedding vectors, have been demonstrated to achieve superior retrieval quality. Nevertheless, these models incur significant overhead at the retrieval time due to the massive amount of embedding vectors. Several promising proposals (e.g., PLAID, DESSERT, EMVB, and MUVERA) have been made to optimize the query latency. To yield high recall, these methods need to generate a considerable amount (e.g., ten thousands) of document candidates, rendering both the candidate generation phase and the refinement phase inefficient. In this paper, we propose a high-quality candidate generation technique that produces only hundreds of candidates yet achieves high recall. Specifically, we develop an incremental next-similar retrieval technique for a proximity graph index in order to facilitate high-quality candidate generation. Our experiments on real datasets show that our proposed method IGP achieves 2x-3x query throughput compared to existing methods at the same accuracy level.

Hash tables are widely used to support fast lookup operations for various applications on key-value stores and relational databases. In recent years, hash tables have been significantly improved by utilizing the high memory bandwidth and large parallelism degree offered by Graphics Processing Units (GPUs). However, there is still a lack of comprehensive analysis of the lookup performance on existing GPU-based hash tables. In this work, we develop a micro-benchmark and devise an effective and general performance analysis model, which enables uniform and accurate lookup performance evaluation of GPU-based hash tables. Moreover, we propose GPH, a novel GPU-based hash table, to improve lookup performance with the guidance of the benchmark results from the analysis model devised above. In particular, GPH employs the perfect hashing scheme that ensures exactly 1 bucket probe for every lookup operation. Besides, we optimize the bucket requests to global memory in GPH by devising vectorization and instruction-level parallelism techniques. We also introduce the insert kernel in GPH to support dynamic updates (e.g., processing insert operations) on GPU. Experimentally, GPH achieves over 8500 million operations per second (MOPS) for lookup operation processing in both synthetic and real-world workloads, which outperforms all evaluated GPU-based hash tables.

The growing scale of graph data across various applications demands efficient distributed graph processing systems. Despite the widespread use of the Scatter-Gather model for large-scale graph processing across distributed machines, the performance still can be significantly improved as the computation ability of each machine is not fully utilized and the communication costs during graph processing are expensive in the distributed environment. In this work, we propose a novel and efficient distributed graph processing system Nezha on heterogeneous hardware, where each machine is equipped with both CPU and GPU processors and all these machines in the distributed cluster are interconnected via Remote Direct Memory Access (RDMA).To reduce the communication costs, we devise an effective communication mode with a graph-friendly communication protocol in the graph-based RDMA communication adapter of Nezha. To improve the computation efficiency, we propose a multi-device cooperative execution mechanism in Nezha, which fully utilizes the CPU and GPU processors of each machine in the distributed cluster. We also alleviate the workload imbalance issue at inter-machine and intra-machine levels via the proposed workload balancer in Nezha. We conduct extensive experiments by running 4 widely-used graph algorithms on 5 graph datasets to demonstrate the superiority of Nezha over existing systems.

Recent studies have made it possible to integrate learning techniques into database systems for practical utilization. In particular, the state-of-the-art studies hook the conventional query optimizer to explore multiple execution plan candidates, then choose the optimal one with a learned model. This framework simplifies the integration of learning techniques into the database system. However, these methods still have room for improvement due to their limited plan exploration space and ineffective learning from execution plans. In this work, we propose Athena, an effective learning-based framework of query optimizer enhancer. It consists of three key components: (i) an order-centric plan explorer, (ii) a Tree-Mamba plan comparator and (iii) a time-weighted loss function. We implement Athena on top of the open-source database PostgreSQL and demonstrate its superiority via extensive experiments. Specifically, We achieve 1.75x, 1.95x, 5.69x, and 2.74x speedups over the vanilla PostgreSQL on the JOB, STATS-CEB, TPC-DS, and DSB benchmarks, respectively. Athena is 1.74x, 1.87x, 1.66x, and 2.28x faster than the state-of-the-art competitor Lero on these benchmarks. Additionally, Athena is open-sourced and it can be easily adapted to other relational database systems as all these proposed techniques in Athena are generic.

Graph neural networks (GNNs) are models specialized for graph data and widely used in applications. To train GNNs on large graphs that exceed CPU memory, several systems have been designed to store data on disk and conduct out-of-core processing. However, these systems suffer from either read amplification when conducting random reads for node features that are smaller than a disk page, or degraded model accuracy by treating the graph as disconnected partitions. To close this gap, we build DiskGNN for high I/O efficiency and fast training without model accuracy degradation. The key technique is offline sampling , which decouples graph sampling from model computation . In particular, by conducting graph sampling beforehand for multiple mini-batches, DiskGNN acquires the node features that will be accessed during model computation and conducts pre-processing to pack the node features of each mini-batch contiguously on disk to avoid read amplification for computation. Given the feature access information acquired by offline sampling, DiskGNN also adopts designs including four-level feature store to fully utilize the memory hierarchy of GPU and CPU to cache hot node features and reduce disk access, batched packing to accelerate feature packing during pre-processing, and pipelined training to overlap disk access with other operations. We compare DiskGNN with state-of-the-art out-of-core GNN training systems. The results show that DiskGNN has more than 8x speedup over existing systems while matching their best model accuracy. DiskGNN is open-source at https://github.com/Liu-rj/DiskGNN.

Understanding and diagnosing query optimizers is crucial to guarantee the correctness and efficiency of query processing in database systems. However, achieving this is non-trivial as there are three technical challenges: (i) hundreds and thousands of query plans are generated for each query during the query optimization procedure; (ii) the transformation logic among query plans is not easy to investigate even for expert database system developers; and (iii) navigating users to the root causes of the bugs/errors is inherently hard as the changes of the operators among query plans are missing in the query processing log. In this work, we propose QOVIS to overcome these challenges, which identifies the query optimization bugs/issues and investigates their root causes via a visualization-assisted approach. Specifically, QOVIS consists of data preprocessing layer, transformation logic computation layer, and visual analysis layer. We conduct extensive experimental studies (e.g., user study, case study, and performance study) to evaluate the efficiency and effectiveness of QOVIS. In particular, our user study (on 24 database developers and researchers) confirms that QOVIS significantly reduces the time required to investigate the bugs/errors in the query optimizer. Moreover, the generality of QOVIS is verified by utilizing it to understand and diagnose the real-world reported bugs/errors in different query optimizers of three widely-used systems: Apache Spark, Apache Hive, and DuckDB.

The two paradigms to identify records of preference in a multi-objective setting rely either on dominance (e.g., the skyline operator) or on a utility function defined over the records’ attributes (typically using a top- k query). Despite their proliferation, each has its own palpable drawbacks. Motivated by these drawbacks, we identify three hard requirements for practical decision support, namely, personalization, controllable output size, and flexibility in preference specification. With these requirements as a guide, we combine elements from both paradigms and propose two new operators, ORD and ORU . We present a suite of algorithms for their efficient processing, dedicating more technical effort to ORU , whose nature is inherently more challenging. Specifically, besides a sophisticated algorithm for ORD , we describe two exact methods for ORU and one approximate. We perform a qualitative study to demonstrate how our operators work and evaluate the performance of our algorithms against adaptations of previous work that mimic their output.

Improving the performance of GPU query processing is a well-studied problem in database community. However, its performance is still unsatisfactory due to the low utilization of GPU memory bandwidth. In the literature, employing software prefetching techniques to improve the bandwidth utilization is a common practice in CPU database as it overlaps computation cost and memory access latency. However, it was ignored by GPU database even though the software prefetching ability has been provided by modern GPU architecture (i.e., from NVIDIA Ampere).

Embedding models represent users and products as high-dimensional embedding vectors and are widely used for recommendation. In this paper, we study the reverse$k-\mathbf{ranks}$query, which finds the users that are the most interested in a product and has many applications including product promotion, targeted advertising, and market analysis. As reverse$k-\mathbf{ranks}$solutions for low dimensionality (e.g., trees) fail for the high-dimensional embeddings generated by embedding models, we propose the QSRP framework. QSRP precomputes the score table between all user and product embeddings to facilitate pruning and refinement at query time. As the score table is usually large, QSRP samples some of its columns as the index to fit in memory. To tackle the problem that naive uniform sampling results in poor pruning effect, we propose query-aware sampling, which conducts sampling by explicitly maximizing the pruning effect for a set of sample queries. Moreover, we introduce regression-based pruning, which fits cheap linear functions to predict the bounds used for pruning. We also design techniques to build the index with limited memory, reduce index building time, and handle updates. We evaluate QSRP under various configurations and compare with state-of-the-art baselines. The results show that QSRP achieves shorter query time than the baselines in all cases, and the speedup is usually over 100x.

The traditional top-k query was proposed to obtain a small subset from the database according to the user preference, which is explicitly expressed as a ranking scheme (i.e., utility function). However, a poorly-designed utility function may create discrimination, which in turn may cause harm to minority groups, e.g., women and ethnic minorities, and thus, fairness is becoming increasingly important in many situations, e.g., hiring and admission decisions. Motivated by this, we study fair ranking to alleviate discrimination. We design a fairness model, called α-fairness, to quantify the fairness of utility functions. We propose an efficient exact framework with a basic implementation and an improved implementation to find the fairest utility function with the minimum modification penalty. We conducted extensive experiments on both real and synthetic datasets to demonstrate our effectiveness and efficiency compared with the prior studies.

Global popularity (GP) bias is the phenomenon that popular items are recommended much more frequently than they should be, which goes against the goal of providing personalized recommendations and harms user experience and recommendation accuracy. Many methods have been proposed to reduce GP bias but they fail to notice the fundamental problem of GP, i.e., it considers popularity from a global perspective of all users and uses a single set of popular items, and thus cannot capture the interests of individual users. As such, we propose a user-aware version of item popularity named personal popularity (PP), which identifies different popular items for each user by considering the users that share similar interests. As PP models the preferences of individual users, it naturally helps to produce personalized recommendations and mitigate GP bias. To integrate PP into recommendation, we design a general personal popularity aware counterfactual (PPAC) framework, which adapts easily to existing recommendation models. In particular, PPAC recognizes that PP and GP have both direct and indirect effects on recommendations and controls direct effects with counterfactual inference techniques for unbiased recommendations. All codes and datasets are available at https://github.com/Stevenn9981/PPAC.

It is an open challenge for cloud database service providers to guarantee tenants' service-level objectives (SLOs) and enjoy high resource utilization simultaneously. In this work, we propose a novel system Tao to overcome it. Tao consists of three key components: (i) tasklet-based DAG generator, (ii) tasklet-based DAG executor, and (iii) SLO-guaranteed scheduler. The core concept in Tao is tasklet, a coroutine-based lightweight execution unit of the physical execution plan. In particular, we first convert each SQL operator in the traditional physical execution plan into a set of fine-grained tasklets by the tasklet-based DAG generator. Then, we abstract the tasklet-based DAG execution procedure and implement the tasklet-based DAG executor using C++20 coroutines. Finally, we introduce the SLO-guaranteed scheduler for scheduling tenants' tasklets across CPU cores. This scheduler guarantees tenants' SLOs with a token bucket model and improves resource utilization with an on-demand core adjustment strategy. We build Tao on an open-sourced relational database, Hyrise, and conduct extensive experimental studies to demonstrate its superiority over existing solutions.

In recent years, many CPU-GPU heterogeneous graph processing systems have been developed in both academic and industrial to facilitate large-scale graph processing in various applications, e.g., social networks and biological networks. However, the performance of existing systems can be significantly improved by addressing two prevailing challenges: GPU memory over-subscription and efficient CPU-GPU cooperative processing. In this work, we propose CGgraph, an ultra-fast CPU-GPU graph processing system to address these challenges. In particular, CGgraph overcomes GPU-memory over-subscription by extracting a subgraph which only needs to be loaded into GPU memory once, but its vertices and edges can be used in multiple iterations during the graph processing procedure. To support efficient CPU-GPU co-processing, we design a CPU-GPU cooperative processing scheme, which balances the workloads between CPU and GPU by on-demand task allocation. To evaluate the efficiency of CG-graph, we conduct extensive experiments, comparing it with 7 state-of-the-art systems using 4 well-known graph algorithms on 6 real-world graphs. Our prototype system CGgraph outperforms all existing systems, delivering up to an order of magnitude improvement. Moreover, CGgraph on a modern commodity machine with a CPU-GPU co-processor yields superior (or at the very least, comparable) performance compared to existing systems on a high-end CPU-GPU server.

Merkle Patricia Trie (MPT) is a type of trie structure that offers efficient lookup and insert operators for immutable data systems that require multi-version access and tamper-evident controls, such as blockchains and verifiable databases. The performance of these systems is critically dependent on the throughput of the underlying index structure MPT. In this paper, we present a novel approach to accelerate MPT by leveraging the massive parallelism of GPU. However, achieving it is challenging as (i) lock-free data structures are difficult to implement and (ii) traditional fine-grained locking does not scale on GPU. To address them, we first analyze the technical challenges of accelerating MPT via GPU, including node splitting conflicts and hash computing conflicts caused by parallel insert operations. We then propose a lock-free algorithm PhaseNU and a lock-based algorithm LockNU on GPU to resolve the node splitting conflict. We also devise a decision model for users to choose the proper one for different workloads. We next propose a GPU-based hash-compute algorithm PhaseHC to avoid hash computing conflicts. Last, we demonstrate the effectiveness of our proposed techniques by: (i) integrating them into both the real-world blockchain system Geth and verifiable database LedgerDB, and demonstrating its superiority with corresponding workloads; and (ii) conducting extensive experimental studies on two real-world datasets and one synthetic dataset. Our proposed solutions significantly outperform the deployed MPT solution in Geth in all datasets.

Influence maximization (IM) is a classic problem that aims to identify a small group of critical individuals, known as seeds, who can influence the largest number of users in a social network through word-of-mouth. This problem finds important applications including viral marketing, infection detection, and misinformation containment. The conventional IM problem is typically studied with the oversimplified goal of selecting a single seed set. Many real-world scenarios call for multiple sets of seeds, particularly on social media platforms where various viral marketing campaigns need different sets of seeds to propagate effectively. To this end, previous works have formulated various IM variants, central to which is the requirement of multiple seed sets, naturally modeled as a matroid constraint. However, the current best-known solutions for these variants either offer a weak (1/2 - ε )-approximation, or offer a (1 - 1/ e - ε )-approximation algorithm that is very expensive. We propose an efficient seed selection method called AMP, an algorithm with a (1 - 1/ e - ε )-approximation guarantee for this family of IM variants. To further improve efficiency, we also devise a fast implementation, called RAMP. We extensively evaluate the performance of our proposal against 6 competitors across 4 IM variants and on 7 real-world networks, demonstrating that our proposal outperforms all competitors in terms of result quality, running time, and memory usage. We have also deployed RAMP in a real industry strength application involving online gaming, where we show that our deployed solution significantly improves upon the baselines.

In this paper, we propose nsDB, a novel neuro-symbolic database system that integrates neural and symbolic system architectures natively to address the weaknesses of each, providing a strong database capable of data managing, model learning, and complex analytical query processing over multi-modal data. We employ a real-world NBA data analytical query as an example to illustrate the functionality of each component in nsDB and highlight the research challenges to build it. We then present the key design principles and our preliminary attempts to address them. In a nutshell, we envision that the next generation database system nsDB integrates the complex neural system with the simple symbolic system. Undoubtedly, nsDB will serve as a bridge between databases with AI models, which abstracts away the AI complexities but allows end users to enjoy the strong capabilities of them. We are in the early stages of the journey to build nsDB, there are many opening challenges, e.g., in-database model training, multi-objective query optimization, and database agent development. We hope the researchers from different communities (e.g., system, architecture, database, artificial intelligence) could tackle them together.

Benchmarking is crucial for evaluating a DBMS, yet existing benchmarks often fail to reflect the varied nature of user workloads. As a result, there is increasing momentum toward creating databases that incorporate real-world user data to more accurately mirror business environments. However, privacy concerns deter users from directly sharing their data, underscoring the importance of creating synthesized databases for benchmarking that also prioritize privacy protection. Differential privacy (DP)-based data synthesis has become a key method for safeguarding privacy when sharing data, but the focus has largely been on minimizing errors in aggregate queries or downstream ML tasks, with less attention given to benchmarking factors like query runtime performance. This paper delves into differentially private database synthesis specifically for benchmark publishing scenarios, aiming to produce a synthetic database whose benchmarking factors closely resemble those of the original data. Introducing PrivBench , an innovative synthesis framework based on sum-product networks (SPNs), we support the synthesis of high-quality benchmark databases that maintain fidelity in both data distribution and query runtime performance while preserving privacy. We validate that PrivBench can ensure database-level DP even when generating multi-relation databases with complex reference relationships. Our extensive experiments show that PrivBench efficiently synthesizes data that maintains privacy and excels in both data distribution similarity and query runtime similarity.

Visualizing large-scale trajectory dataset is a core subroutine for many applications. However, rendering all trajectories could result in severe visual clutter and incur long visualization delays due to large data volume. Naively sampling the trajectories reduces visualization time but usually harms visual quality, i.e., the generated visualizations may look substantially different from the exact ones without sampling. In this paper, we propose$\mathsf {CheetahTraj}$, a principled sampling framework that achieves both high visualization quality and low visualization latency. We first define thevisual quality functionmeasuring the similarity between two visualizations, based on which we formulate the quality optimal sampling problem (${\sf QOSP}$). To solve${\sf QOSP}$, we design theVisualQualityGuaranteedSampling algorithms, which reduce visual clutter while guaranteeing visual quality by considering both trajectory data distribution and human perception properties. We also develop a quad-tree-based index ($\mathsf {InvQuad}$) that allows using trajectory samples computed offline for interactive online visualization. Extensive experiments including case-, user-, and quantitative-studies are conducted on three real-world trajectory datasets, and the results show that$\mathsf {CheetahTraj}$consistently provides higher visual quality and better efficiency than baseline methods. Compared with visualizing all trajectories,$\mathsf {CheetahTraj}$reduces the visualization latency by up to 3 orders of magnitude while avoiding visual clutter.

A knowledge graph contains many real-world facts that can be used to support various analytical tasks, e.g., exceptional fact discovery and the check of claims. In this work, we attempt to extract top-$k$frequent and diversified patterns from knowledge graph by well capturing user interest. Specifically, we first formalize the core-based top-$k$frequent pattern discovery problem, which finds the top-$k$frequent patterns that are extended from a core pattern specified by user query and have the highest frequency. In addition, to diversify the top-$k$frequent patterns, we define a distance function to measure the dissimilarity between two patterns, and return top-$k$patterns in which the pairwise diversity of any two resultant patterns exceeds a given threshold. As the search space of candidate patterns is exponential w.r.t. the number of nodes and edges in the knowledge graph, discovering frequent and diversified patterns is computationally challenging. To achieve high efficiency, we propose a suite of techniques, including (1) We devise a meta-index to avoid generating invalid candidate patterns; (2) We propose an upper bound of the frequency score (i.e., MNI) of the candidate pattern, which is used to prune unqualified candidates earlier and prioritize the enumeration order of patterns; (3) We design an advanced join-based approach to compute the MNI of candidate patterns efficiently; and (4) We develop a lower bound for distance function and incrementally compute the pairwise diversity among the patterns. Using real-world knowledge graphs, we experimentally verify the efficiency and effectiveness of our proposed techniques. We also demonstrate the utility of the extracted patterns by case studies.

Multi-domain recommendation (MDR) aims to provide recommendations for different domains (e.g., types of products) with overlapping users/items and is common for platforms such as Amazon, Facebook, and LinkedIn that host multiple services. Existing MDR models face two challenges: First, it is difficult to disentangle knowledge that generalizes across domains (e.g., a user likes cheap items) and knowledge specific to a single domain (e.g., a user likes blue clothing but not blue cars). Second, they have limited ability to transfer knowledge across domains with small overlaps. We propose a new MDR method named EDDA with two key components, i.e., embedding disentangling recommender and domain alignment, to tackle the two challenges respectively. In particular, the embedding disentangling recommender separates both the model and embedding for the inter-domain part and the intra-domain part, while most existing MDR methods only focus on model-level disentangling. The domain alignment leverages random walks from graph processing to identify similar user/item pairs from different domains and encourages similar user/item pairs to have similar embeddings, enhancing knowledge transfer. We compare EDDA with 12 state-of-the-art baselines on 3 real datasets. The results show that EDDA consistently outperforms the baselines on all datasets and domains. All datasets and codes are available at https://github.com/Stevenn9981/EDDA.

In recent years, the performance of hash indexes has been significantly improved by exploiting emerging persistent memory (PMem). However, the performance improvement of hash indexes mainly comes from exploiting the hardware features of PMem. Only a few studies optimize the hash index itself to fully exploit the potential of PMem. Interestingly, many of these studies improve the performance of write, but disregard the performance of read, of hash indexes on PMem. With extensive experimental evaluation, we find the major reason for inefficient read in the hash index on PMem is that the overhead of hash collision processing is expensive.To address that, we propose a novel Efficient Extendible Perfect Hashing (EEPH) on PMem-DRAM hybrid data layout to improve read performance of hash indexes. Specifically, we reduce the overhead of dynamic perfect hashing extension on PMem by combing extendible hashing. We then design a hybrid data layout to unlock the inherent read strengths of perfect hashing (i.e., zero collision). Last, we devise a complement move algorithm to efficiently guarantee the zero collision of perfect hashing when data move is conducted on PMem. We compare EEPH with the state-of-the-art hash indexes on PMem by conducting comprehensive experiments on several real-world read-intensive and read-skew workloads. The experimental results confirm the superiority of our EEPH as it achieves up to 2.21× higher throughput and about 1/3 of the 99th percentile latency than state-of-the-art hash indexes.

Influence maximization (IM) aims to identify a small number of influential individuals to maximize the information spread and finds applications in various fields. It was first introduced in the context of viral marketing, where a company pays a few influencers to promote the product. However, apart from the cost factor, the capacity of individuals to consume content poses challenges for implementing IM in real-world scenarios. For example, players on online gaming platforms can only interact with a limited number of friends. In addition, we observe that in these scenarios, (i) the initial adopters of promotion are likely to be the friends of influencers rather than the influencers themselves, and (ii) existing IM solutions produce sub-par results with high computational demands. Motivated by these observations, we propose a new IM variant called capacity constrained influence maximization (CIM), which aims to select a limited number of influential friends for each initial adopter such that the promotion can reach more users. To solve CIM effectively, we design two greedy algorithms, MG-Greedy and RR-Greedy, ensuring the 1/2-approximation ratio. To improve the efficiency, we devise the scalable implementation named RR-OPIM+ with (1/2-ε)-approximation and near-linear running time. We extensively evaluate the performance of 9 approaches on 6 real-world networks, and our solutions outperform all competitors in terms of result quality and running time. Additionally, we deploy RR-OPIM+ to online game scenarios, which improves the baseline considerably.

While many systems have been developed to train graph neural networks (GNNs), efficient model evaluation, which computes node embedding according to a given model, remains to be addressed. For instance, using the widely adopted node-wise approach, model evaluation can account for over 90% of the time in the end-to-end training process due to neighbor explosion, which means that a node accesses its multi-hop neighbors. The layer-wise approach avoids neighbor explosion by conducting computation layer by layer in GNN models. However, layer-wise model evaluation takes considerable implementation efforts because users need to manually decompose the GNN model into layers, and different implementations are required for GNN models with different structures.

Given a graph \mathcalG , the spanning centrality (SC) of an edge e measures the importance of e for \mathcalG to be connected. In practice, SC has seen extensive applications in computational biology, electrical networks, and combinatorial optimization. However, it is highly challenging to compute the SC of all edges (AESC) on large graphs. Existing techniques fail to deal with such graphs, as they either suffer from expensive matrix operations or require sampling numerous long random walks. To circumvent these issues, this paper proposes TGT and its enhanced version TGT+, two algorithms for AESC computation that offers rigorous theoretical approximation guarantees. In particular, TGT remedies the deficiencies of previous solutions by conducting deterministic graph traversals with carefully-crafted truncated lengths. TGT+ further advances TGT in terms of both empirical efficiency and asymptotic performance while retaining result quality, based on the combination of TGT with random walks and several additional heuristic optimizations. We experimentally evaluate TGT+ against recent competitors for AESC using a variety of real datasets. The experimental outcomes authenticate that TGT+ outperforms state of the arts often by over one order of magnitude speedup without degrading the accuracy.

Graph visualization is a vital component in many real-world applications (e.g., social network analysis, web mining, and bioinformatics) that enables users to unearth crucial insights from complex data. Lying in the core of graph visualization is the node distance measure, which determines how the nodes are placed on the screen. A favorable node distance measure should be informative in reflecting the full structural information between nodes and effective in optimizing visual aesthetics. However, existing node distance measures yield sub-par visualization quality as they fall short of these requirements. Moreover, most existing measures are computationally inefficient, incurring a long response time when visualizing large graphs. To overcome such deficiencies, we propose a new node distance measure, PDist, geared towards graph visualization by exploiting a well-known node proximity measure,personalized PageRank. Moreover, we propose an efficient algorithm Tau-Push for estimating PDist under both single- and multi-level visualization settings. With several carefully-designed techniques, TauPush offers non-trivial theoretical guarantees for estimation accuracy and computation complexity. Extensive experiments show that our proposal significantly outperforms 13 state-of-the-art graph visualization solutions on 12 real-world graphs in terms of both efficiency and effectiveness (including aesthetic criteria and user feedback). In particular, our proposal can interactively produce satisfactory visualizations within one second for billion-edge graphs.

Due to the advancement of geo-positioning technology, the terrain data has become increasingly popular and has drawn a lot of research effort from both academia and industry. The distance computation on the terrain surface is a fundamental and important problem that is widely applied in geographical information systems and 3D modeling. As could be observed from the existing studies, online computation of the distance on the terrain surface is very expensive. All existing index-based methods are only efficient under the case where the distance query must be performed among a small set of predefined points-of-interest known apriori. But, in general cases, they could not scale up to sizable datasets due to their intolerable oracle building time and space consumption. In this paper, we studied the arbitrary point-to-arbitrary point distance query on the terrain surface in which no assumption is imposed on the query points, and the distance query could be performed between any two arbitrary points. We propose an indexing structure, namely Efficient Arbitrary Point-to-Arbitrary Point Distance Oracle (EAR-Oracle), with theoretical guarantee on the accuracy, oracle building time, oracle size and query time. Our experiments demonstrate that our oracle enjoys excellent scalability and it scales up to enormous terrain surfaces but none of the existing index-based methods could be able to. Besides, it significantly outperforms all existing online computation methods by orders of magnitude in terms of the query time.

Fast query execution requires learning-based cardinality estimators to have short inference time (as model inference time adds to end-to-end query execution time) and high estimation accuracy (which is crucial for finding good execution plan). However, existing estimators cannot meet both requirements due to the inherent tension between model complexity and estimation accuracy. We propose a novel Learning-based Progressive Cardinality Estimator (LPCE), which adopts a query re-optimization methodology. In particular, LPCE consists of an initial model (LPCE-I), which estimates cardinality before query execution, and a refinement model (LPCE-R), which progressively refines the cardinality estimations using the actual cardinalities of the executed operators. During query execution, re-optimization is triggered if the estimations of LPCE-I are found to have large errors, and more efficient execution plans are selected for the remaining operators using the refined estimations provided by LPCE-R. Both LPCE-I and LPCE-R are light-weight query-driven estimators but they achieve both good efficiency and high accuracy when used jointly. Besides designing the models for LPCE-I and LPCE-R, we also integrate re-optimization and LPCE into PostgreSQL, a popular database engine. Extensive experiments show that LPCE yields shorter end-to-end query execution time than state-of-the-art learning-based estimators.

In this work, we focus on the performance benchmarking problem of storage services in cloud-native database systems, which are widely used in various cloud applications. The core idea of these systems is to separate computation and storage in traditional monolithic OLTP databases. Specifically, we first present the characteristics of two representative real I/O workloads at the storage tier of ByteDance's cloud-native database veDB. We then elaborate the limitations of using standard benchmarks such as TPC-C and YCSB to resemble these workloads. To overcome these limitations, we devise a learning-based I/O workload benchmark called CDS-Ben. We demonstrate the superiority of CDSBen by deploying it at ByteDance and showing that its generated I/O traces accurately resemble the real I/O traces in production. Additionally, we verify the accuracy and flexibility of CDSBen by generating a wide range of I/O workloads with different I/O characteristics.

Nowadays, Apache Hive has been widely used for large-scale data analysis applications in many organizations. Various visual analytical tools are developed to help Hive users quickly analyze the query execution process and identify the performance bottleneck of executed queries. However, existing tools mostly focus on showing the time usage of query sub-components (jobs and operators) but fail to provide enough evidence to analyze the root reasons for the slow execution progress. To tackle this problem, we develop a visual analytical system DHive to visualize and analyze the query execution progress via dataflow analysis. DHive shows the dataflow during query execution at multiple levels: query level, job level and task level, which enable users to identify the key jobs/tasks and explain their time usage by linking them to the auxiliary information such as the system configuration and hardware status. We demonstrate the effectiveness of DHive by two cases in a production cluster. DHive is open-source at https://github.com/DBGroup-SUSTech/DHive.git.

Many systems are designed to run graph algorithms efficiently in memory but they achieve only cache efficiency or work efficiency. We tackle this fundamental trade-off in existing systems by designing CoroGraph, a system that attains both cache efficiency and work efficiency for in-memory graph processing. CoroGraph adopts a novel hybrid execution model , which generates update messages at vertex granularity to prioritize promising vertices for work efficiency, and commits updates at partition granularity to share data access for cache efficiency. To overlap the random memory access of graph algorithms with computation, CoroGraph extensively uses coroutine , i.e., a lightweight function in C++ that can yield and resume with low overhead, to prefetch the required data. A suite of designs are incorporated to reap the full benefits of coroutine, which include prefetch pipeline, cache-friendly graph format, and stop-free synchronization. We compare CoroGraph with five state-of-the-art graph algorithm systems via extensive experiments. The results show that CoroGraph yields shorter algorithm execution time than all baselines in 18 out of 20 cases, and its speedup over the best-performing baseline can be over 2x. Detailed profiling suggests that CoroGraph achieves both cache efficiency and work efficiency with a low memory stall and a small number of processed edges.

Measuring the closeness of friendships is an important problem that finds numerous applications in practice. For example, online gaming platforms often host friendship-enhancing events in which a user (called the source) only invites his/her friend (called the target) to play together. In this scenario, the measure of friendship closeness is the backbone for understanding source invitation and target adoption behaviors, and underpins the recommendation of promising targets for the sources. However, most existing measures for friendship closeness only consider the information between the source and target but ignore the information of groups where they are located, which renders inferior results. To address this issue, we present new measures for friendship closeness based on the social identity theory (SIT), which describes the inclination that a target endorses behaviors of users inside the same group. The core of SIT is the process that a target assesses groups of users as them or us. Unfortunately, this process is difficult to be captured due to perceptual factors. To this end, we seamlessly reify the factors of SIT into quantitative measures, which consider local and global information of a target's group. We conduct extensive experiments to evaluate the effectiveness of our proposal against 8 state-of-the-art methods on 3 online gaming datasets. In particular, we demonstrate that our solution can outperform the best competitor on the behavior prediction (resp. online target recommendation) by up to 23.2% (resp. 34.2%) in the corresponding evaluation metric.

Heterogeneous Information Networks (HINs) are labeled graphs that depict relationships among different types of entities (e.g., users, movies and directors). For HINs,meta-path-based recommenders (MPRs) utilize meta-paths (i.e., abstract paths consisting of node and link types) to predict user preference, and have attracted a lot of attention due to their explainability and performance. We observe that the performance of MPRs is highly sensitive to the meta-paths they use, but existing works manually select the meta-paths from many possible ones. Thus, to discover effective meta-paths automatically, we propose the Reinforcement learning-based Meta-path Selection (RMS) framework. Specifically, we define a vector encoding for meta-paths and design a policy network to extend meta-paths. The policy network is trained based on the results of downstream recommendation tasks and an early stopping approximation strategy is proposed to speed up training. (RMS) is a general model, and it can work with all existing MPRs. We also propose a new MPR called RMS-HRec, which uses an attention mechanism to aggregate information from the meta-paths. We conduct extensive experiments on real datasets. Compared with the manually selected meta-paths, the meta-paths identified by (RMS) consistently improve recommendation quality. Moreover, RMS-HRec outperforms state-of-the-art recommender systems by an average of 7% in hit ratio. The codes and datasets are available on https://github.com/Stevenn9981/RMS-HRec.

Images occupy a large amount of storage in data centers. To cope with the explosive growth of the image storage requirement, image compression techniques are devised to shrink the size of every single image at first. Furthermore, image deduplication methods are proposed to reduce the storage cost as they could be used to eliminate redundancy among images. However, state-of-the-art image deduplication methods either can only eliminate file-level coarse-grained redundancy or cannot guarantee lossless deduplication. In this work, we propose a new lossless image deduplication framework to eliminate fine-grained redundancy among images. It first decodes images to expose similarity, then eliminates fine-grained redundancy on the decoded data by delta compres-sion, and finally re-compresses the remaining data by image compression encoding. Based on this framework, we propose a novel lossless similarity-based deduplication (SBD) scheme for decoded image data (called imDedup). Specifically, imDedup uses a novel and fast sampling method (called Feature Map) to detect similar images in a two-dimensional way, which greatly reduces computation overhead. Meanwhile, it uses a novel delta encoder (called Idelta) which incorporates image compression encoding characteristics into deduplication to guarantee the remaining deduplicated image data to be friendly re-compressed via image encoding, which significantly improves the compression ratio. We implement a prototype of imDedup for JPEG images, and demonstrate its superiority on four datasets: Compared with exact image deduplication, imDedup achieves a 19%-38% higher compression ratio by efficiently eliminating fine-grained redundancy. Compared with the similarity detector and delta encoder of state-of-the-art SBD schemes running on the decoded image data, imDedup achieves a 1.8×-3.4× higher throughput and a 1.3 ×-1. 6 × higher compression ratio, respectively.

Knowledge graphs capture the complex relationships among various entities, which can be found in various real world applications, e.g., Amazon product graph, Freebase, and COVID-19. To facilitate the knowledge graph analytical tasks, a system that supports interactive and efficient query processing is always in demand. In this demonstration, we develop a prototype system, CheetahKG, that embeds with our state-of-the-art query processing engine for the top-$k$frequent pattern discovery. Such discovered patterns can be used for two purposes, (i) identifying related patterns and (ii) guiding knowledge exploration. In the demonstration sessions, the attendees will be invited to test the efficiency and effectiveness of the query engine and use the discovered patterns to analyze knowledge graphs on CheetahKG.

Distance distributions have been widely applied in many real-world applications, e.g., graph analysis. Unfortunately, due to the large data volume and expensive distance computation, the exact distance distribution computation is excessively slow. Motivated by this, we present a novel approximate solution in this paper that (i) achieves error-bound guarantees and (ii) is generic to various distance measures. Our proposed method outperforms the baseline in terms of accuracy and efficiency when evaluating on three widely used distance measures with real-world datasets.

Analyzing and mining of time series have been widely studied in both academia and industry in recent years. Given a set of long time series, data analysts can utilize the window-based similarity search to explore subsequences in arbitrary time windows. Existing techniques are not efficient for window-based query processing. In particular, the whole matching index approach needs to build an individual index for each window, which incurs huge space cost. The existing window-based approach can only cluster neighboring windows, which leads to loose bounds of each group, and thus degrades the query processing efficiency. In this paper, we propose a compact time series index (WinIdx) for efficient window query processing. Specifically, i) we propose a novel distance measurement to capture the similarity between windows, ii) WinIdx provides a compact index structure for windows within a cluster by exploiting the similarity among subsequences relationships, and iii) several optimizations (e.g., sortable summarization, summarization envelop) are equipped in WinIdx to improve the efficiency of index construction, query processing and index footprints. We conduct extensive experiments on both real and synthetic time series to demonstrate the superiority of WinIdx against state-of-the-art approaches.

Within the rapidly expanding Internet of Things (IoT), growing amounts of spatially referenced data are being generated. Due to the dynamic, decentralized, and heterogeneous nature of the IoT, spatial IoT data (SID) quality has attracted considerable attention in academia and industry. How to invent and use technologies for managing spatial data quality and exploiting low-quality spatial data are key challenges in the IoT. In this tutorial, we highlight the SID consumption requirements in applications and offer an overview of spatial data quality in the IoT setting. In addition, we review pertinent technologies for quality management and low-quality data exploitation, and we identify trends and future directions for quality-aware SID management and utilization. The tutorial aims to not only help researchers and practitioners to better comprehend SID quality challenges and solutions, but also offer insights that may enable innovative research and applications.

As a distributed, fault-tolerant data warehouse system for large-scale data analytics, Apache Hive has been used for various applications in many organizations (e.g., Facebook, Amazon, and Huawei). Exploiting the large degrees of parallelism of GPU to improve the performance of online analytical processing (OLAP) in database system is a common practice in the industry. Meanwhile, it is a common practice to exploit the large degrees of parallelism of GPU to improve the performance of online analytical processing (OLAP) in database systems. This demo presents GHive, which enables Apache Hive to accelerate OLAP queries by jointly utilizing CPU and GPU in intelligent and efficient ways. The takeaways for SIGMOD attendees include: (1) the superior performance of GHive compared with vanilla Hive that only uses CPU; (2) intuitive visualizations of execution statistics for Hive and GHive to understand where the acceleration of GHive comes from; (3) detailed profiling of the time taken by each operator on CPU and GPU to show the advantages of GPU execution.

Top-k related queries in continuous preference space (e.g., k-shortlist preference query kSPR, uncertain top-k query UTK, output-size specified utility-based query ORU) have numerous applications but are expensive to process. Existing algorithms process each query via specialized optimizations, which are difficult to generalize. In this work, we propose a novel and general index structure T-LevelIndex, which can be used to process various queries in continuous preference space efficiently. We devise efficient approaches to build the T-LevelIndex by fully exploiting the properties of continuous preference space. We conduct extensive experimental studies on both real- and synthetic- benchmarks. The results show that (i) our proposed index building approaches have low costs in terms of both space and time, and (ii) T-LevelIndex significantly outperforms specialized solutions for processing a spectrum of queries in continuous preference space, and the speedup can be two to three orders of magnitude.

With the development of learning-based embedding models, embedding vectors are widely used for analyzing and searching unstructured data. As vector collections exceed billion-scale, fully managed and horizontally scalable vector databases are necessary. In the past three years, through interaction with our 1200+ industry users, we have sketched a vision for the features that next-generation vector databases should have, which include long-term evolvability, tunable consistency, good elasticity, and high performance. We present Manu, a cloud native vector database that implements these features. It is difficult to integrate all these features if we follow traditional DBMS design rules. As most vector data applications do not require complex data models and strong data consistency, our design philosophy is to relax the data model and consistency constraints in exchange for the aforementioned features. Specifically, Manu firstly exposes the write-ahead log (WAL) and binlog as backbone services. Secondly, write components are designed as log publishers while all read-only analytic and search components are designed as independent subscribers to the log services. Finally, we utilize multi-version concurrency control (MVCC) and a delta consistency model to simplify the communication and cooperation among the system components. These designs achieve a low coupling among the system components, which is essential for elasticity and evolution. We also extensively optimize Manu for performance and usability with hardware-aware implementations and support for complex search semantics. Manu has been used for many applications, including, but not limited to, recommendation, multimedia, language, medicine and security. We evaluated Manu in three typical application scenarios to demonstrate its efficiency, elasticity, and scalability.

Underlying many types of data analytics, a spatiotemporal quantile monitoring (SQM) query continuously returns the quantiles of a dataset observed in a spatiotemporal range. In this paper, we study SQM in an Internet of Things (IoT) based edge computing environment, where concurrent SQM queries share the same infrastructure asynchronously. To minimize query latency while providing result accuracy guarantees, we design a processing framework that virtualizes edge-resident data sketches for quantile computing. In the framework, a coordinator edge node manages edge sketches and synchronizes edge sketch processing and query executions. The co-ordinator also controls the processed data fractions of edge sketches, which helps to achieve the optimal latency with error-bounded results for each single query. To support concurrent queries, we employ a grid to decompose queries into subqueries and process them efficiently using shared edge sketches. We also devise a relaxation algorithm to converge to optimal latencies for those subqueries whose result errors are still bounded. We evaluate our proposals using two high-speed streaming datasets in a simulated IoT setting with edge nodes. The results show that our proposals achieve efficient, scalable, and error-bounded SQM.

In this work we study the distance distribution computation problem. It has been widely used in many real-world applications, e.g., human genome clustering, cosmological model analysis, and parameter tuning. The straightforward solution for the exact distance distribution computation problem is unacceptably slow due to (i) massive data size, and (ii) expensive distance computation. In this paper, we propose a novel method to compute approximate distance distributions with error bound guarantees. Furthermore, our method is generic to different distance measures. We conduct extensive experimental studies on three widely used distance measures with real-world datasets. The experimental results demonstrate that our proposed method outperforms the sampling-based solution (without error guarantees) by up to three orders of magnitude.

In recent years, the widespread use of sensors has substantially stimulated researchers' interest in time series data mining. Real-world time series often include natural structures. For example, a time series captured from a patient rehabilitation app can be divided into a series of movements, e.g., sitting, standing, and walking. Finding time series natural structures (i.e., latent semantic states) is one of the core subroutines in time series mining applications. However, this task is not trivial as it has two challenges: (1) how to determine the correct change points between consecutive segments, and (2) how to cluster segments into different states.In this paper, we propose a novel graph-based approach, GRAB, to discover time series natural structures. In particular, GRAB first partitions the time series into a set of non-overlapping fragments via the similarity between subsequences. Then, it constructs a fragment-based graph and employs a graph partition method to cluster the fragments into states. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of our GRAB method. Specifically, GRAB finds high-quality latent states, and it outperforms state-of-the-art solutions by orders of magnitude.

In this paper, we propose the streaming MaxBRNNquery, which finds the optimal region to deploy a new service point when both the service points and client points are under continuous updates. The streaming MaxBRNN query has many applications such as taxi scheduling, shared bike placements, etc. Existing MaxBRNN solutions are insufficient for streaming updates as they need to re-run from scratch even for a small amount of updates, resulting in long query processing time. To tackle this problem, we devise an efficient slot partitioning-based algorithm (SlotP), which divides the space into equal-sized slots and processes each slot independently. The superiorities of our proposal for streaming MaxBRNN query are: (i) an update affects only a smaller number of slots and works done on the unaffected slots can be reused directly; (ii) the influence value upper bound of each slot can be derived efficiently and accurately, which facilitate pruning many slots from expensive computation. We conducted extensive experiments to validate the performance of the SlotP algorithm. The results show that SlotP is 2-3 orders of magnitude faster than state-of-the-art baselines.

Knowledge graph is a way of structuring information in graph form, by representing entities as nodes and relationships between entities as edges. A knowledge graph often consists of large amount of facts in real-world which can be used in supporting many analytical tasks, e.g., exceptional facts discovery and fact check of claims. In this work, we study a core-based top-k frequent pattern discovery problem which is frequently used as a subroutine in analyzing knowledge graphs. The main challenge of the problem is search space of the candidate patterns is exponential to the combinations of the nodes and edges in the knowledge graph.To reduce the search space, we devise a novel computation framework FastPat with a suite of optimizations. First, we devise a meta-index, which can be used to avoid generating invalid candidate patterns. Second, we propose an upper bound of the frequency score (i.e., MNI) of the candidate pattern that prunes unqualified candidates earlier and prioritize the enumeration order of the patterns. Lastly, we design a join-based approach to compute the MNI of candidate pattern efficiently. We conduct extensive experimental studies in real-world datasets to verify the superiority of our proposed method over the baselines. We also demonstrate the utility of the discovered frequent patterns by a case study in COVID-19 knowledge graph.

In this paper, we propose the GAIPS framework for efficient maximum inner product search (MIPS) on GPU. We observe that a query can usually find a good lower bound of its maximum inner product in some large norm items that take up only a small portion of the dataset and utilize this fact to facilitate pruning. In addition, we design norm-based, residue-based and hash-based pruning techniques to avoid computation for items that are unlikely to be the MIPS results. Experiment results show that compared with FAISS, the state-of-the-art GPU-based similarity search framework, GAIPS has significantly shorter query processing time at the same recall.

In this paper, we study the m-impact region problem (mIR). In a context where users look for available products with top-k queries, mIR identifies the part of the product space that attracts the most user attention. Specifically, mIR determines the kind of attribute values that lead a (new or existing) product to the top-k result for at least a fraction of the user population. mIR has several applications, ranging from effective marketing to product improvement. Importantly, it also leads to (exact and efficient) solutions for standing top-k impact problems, which were previously solved heuristically only, or whose current solutions face serious scalability limitations. We experiment, among others, on data mined from actual user reviews for real products, and demonstrate the practicality and efficiency of our algorithms, both for mIR and for standing top-k impact problems.

The two most common paradigms to identify records of preference in a multi-objective setting rely either on dominance (e.g., the skyline operator) or on a utility function defined over the records' attributes (typically, using a top-k query). Despite their proliferation, each of them has its own palpable drawbacks. Motivated by these drawbacks, we identify three hard requirements for practical decision support, namely, personalization, controllable output size, and flexibility in preference specification. With these requirements as a guide, we combine elements from both paradigms and propose two new operators, ORD and ORU. We perform a qualitative study to demonstrate how they work, and evaluate their performance against adaptations of previous work that mimic their output.

Graph neural networks (GNNs) have achieved remarkable performance in many graph analytics tasks such as node classification, link prediction and graph clustering. Existing GNN systems (e.g., PyG and DGL) adopt a tensor-centric programming model and train GNNs with manually written operators. Such design results in poor usability due to the large semantic gap between the API and the GNN models, and suffers from inferior efficiency because of high memory consumption and massive data movement. We demonstrateSeastar, a novel GNN training framework that adopts avertex-centric programming paradigm and supportsautomatic kernel generation, to simplify model development and improve training efficiency. We will (i) show how to express GNN models succinctly using a visual "drag-and-drop'' interface or Seastar's vertex-centric python API; (ii) demonstrate the performance advantage of Seastar over existing GNN systems in convergence speed, training throughput and memory consumption; and (iii) illustrate how Seastar's optimizations (e.g., operator fusion and constant folding) improve training efficiency by profiling the run-time performance.

Recent years, many applications have been driven advances by the use of Machine Learning (ML). Nowadays, it is common to see industrial-strength machine learning jobs that involve millions of model parameters, terabytes of training data, and weeks of training. Good efficiency, i.e., fast completion time of running a specific ML training job, therefore, is a key feature of a successful ML system. While the completion time of a long-running ML job is determined by the time required to reach model convergence, that is also largely influenced by the values of various system settings. In this paper, we contribute techniques towards building self-tuning parameter servers. Parameter Server (PS) is a popular system architecture for large-scale machine learning systems; and by self-tuning we mean while a long-running ML job is iteratively training the expert-suggested model, the system is also iteratively learning which system setting is more efficient for that job and applies it online. Our techniques are general enough to various PS-style ML systems. Experiments on TensorFlow show that our techniques can reduce the completion times of a variety of long-running TensorFlow jobs from 1.4× to 18×.

Recently, the spatial-temporal data of urban moving objects, e.g., cars and buses, are collected and widely used in urban trajectory exploratory analysis. Urban bus service is one of the most common public transportation services. Urban bus data analysis plays an important role in smart city applications. For example, data analysts in bus companies use the urban bus data to optimize their bus scheduling plan. Map services providers, e.g., Google map, Ten-cent map, take urban bus data into account to improve their service quality (e.g., broadcast road update instantly). Unlike urban moving cars or pedestrians, urban buses travel on known bus routes. The operating buses form the "bus flows" in a city. Efficient analyzing urban bus flows has many challenges, e.g., how to analyze the dynamics of given bus routes? How to help users to identify traffic flow of interests easily? In this work, we present CheetahVIS, a visual analytical system for efficient massive urban bus data analysis. CheetahVIS builds upon Spark and provides a visual analytical platform for the stakeholders (e.g., city planner, data analysts in bus company) to conduct effective and efficient analytical tasks. In the demonstration, demo visitors will be invited to experience our proposed CheetahVIS system with different urban bus data analytical functions, e.g., bus route analysis, public bus flow overview, multiple region analysis, in a real-world dataset. We also will present a case study, which compares different regions in a city, to demonstrate the effectiveness of CheetahVIS.

202402 bcch

Big urban trajectory exploration extracts insights from trajectories. It has many smart-city applications, e.g., traffic jam detection, taxi movement pattern analysis. The challenges of big urban trajectory data exploration are: (i) the data analysts probably do not have experience or knowledge on issuing their analysis tasks by SQL-like queries or analysis operations accurately; and (ii) big urban trajectory data is naturally complex, e.g., unpredictability, interrelation, etc. In this work, we architect and implement a visualization-assisted big urban trajectory data exploration system (Vaiet) to address these chanllenges. Vaiet includes three layers, from data collection to results visualization. We devise novel visualization views in Vaiet to support interactive big urban trajectory exploratory analysis. We demonstrate the effectiveness of Vaiet by the real world applications.

Recommender systems are widely used in many applications, e.g., social network, e-commerce. Inner product retrieval IPR is the core subroutine in Matrix Factorization (MF) based recommender systems. It consists of two phases: i) inner product computation and ii) top-k items retrieval. The performance bottleneck of existing solutions is inner product computation phase. Exploiting Graphics Processing Units (GPUs) to accelerate the computation intensive workloads is the gold standard in data mining and machine learning communities. However, it is not trivial to apply CPU-GPU systems to boost the performance of IPR solutions due to the nature complex of the IPR problem. In this work, we analyze the time cost of each phase in IPR solutions at first. Second, we exploit the characteristics of CPU-GPU systems to improve performance. Specifically, the computation tasks of IPR solution are heterogeneously processed in CPU-GPU systems. Third, we demonstrate the efficiency of our proposal on four standard real datasets.

Top- k queries are extensively used to retrieve the k most relevant options (e.g., products, services, accommodation alternatives, etc) based on a weighted scoring function that captures user preferences. In this paper, we take the viewpoint of a business owner who plans to introduce a new option to the market, with a certain type of clientele in mind. Given a target region in the consumer spectrum, we determine what attribute values the new option should have, so that it ranks among the top- k for any user in that region. Our methodology can also be used to improve an existing option, at the minimum modification cost, so that it ranks consistently high for an intended type of customers. This is the first work on competitive option placement where no distinct user(s) are targeted, but a general clientele type, i.e., a continuum of possible preferences. Here also lies our main challenge (and contribution), i.e., dealing with the interplay between two continuous spaces: the targeted region in the preference spectrum, and the option domain (where the new option will be placed). At the core of our methodology lies a novel and powerful interlinking between the two spaces. Our algorithms offer exact answers in practical response times, even for the largest of the standard benchmark datasets.

Real-time city crowd flows are extremely important for facility placement, transportation management, and public safety. In this paper, we show how to derive the real-time city crowd flows with heterogeneous urban data. Unlike existing prediction-based approaches, our proposal does not rely on the training data and learning models. We propose a computation framework for it by exploiting the massive heterogeneous urban data, which includes both immutable data (i.e., bus and subway stations, commercial-based regions) and mutable data (i.e., real-time taxi, bus, subway transactions and trajectories). In addition, our solution provides accurate and timely city crowd-flows.To provide a practical solution for it, we first partition the city into commercial-based regions with geographic information (e.g., road network, administrative regions). Then, we devise three major components (i.e., urban data fusion model, heterogeneous urban data integration model, and effective crowd flows computation model) in the computation framework to process massive heterogeneous urban data effectively and derive city crowd flows accurately. Finally, we conduct extensive experiments to demonstrate the effectiveness and efficiency of our proposed solution with real heterogeneous urban data in Shenzhen, China.

Traditional rank-aware processing assumes a dataset that contains available options to cover a specific need (e.g., restaurants, hotels, etc) and users who browse that dataset via top- k queries with linear scoring functions, i.e., by ranking the options according to the weighted sum of their attributes, for a set of given weights. In practice, however, user preferences (weights) may only be estimated with bounded accuracy, or may be inherently uncertain due to the inability of a human user to specify exact weight values with absolute accuracy. Motivated by this, we introduce the uncertain top-k query ( UTK ). Given uncertain preferences, that is, an approximate description of the weight values, the UTK query reports all options that may belong to the top- k set. A second version of the problem additionally reports the exact top- k set for each of the possible weight settings. We develop a scalable processing framework for both UTK versions, and demonstrate its efficiency using standard benchmark datasets.

20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, 21-24 March 2017

202402 bcch

In high-dimensional kNN search, both exact and approximate kNN solutions incur considerable time in the candidate refinement phase. In this paper, we investigate a caching solution to reduce the candidate refinement time. Our caching method HC-O is faster than EXACT caching by at least an order of magnitude, on an approximate index (C2LSH). Our work is also applicable to exact indexes (e.g., iDistance, VPtree and VA-file).

OLAP tools have been extensively used by enterprises to make better and faster decisions. Nevertheless, they require users to specify group-by attributes and know precisely what they are looking for. This paper takes the first attempt towards automatically extracting top-k insights from multi-dimensional data. This is useful not only for non-expert users, but also reduces the manual effort of data analysts. In particular, we propose the concept of insight which captures interesting observation derived from aggregation results in multiple steps (e.g., rank by a dimension, compute the percentage of measure by a dimension). An example insight is: ``Brand B's rank (across brands) falls along the year, in terms of the increase in sales''. Our problem is to compute the top-k insights by a score function. It poses challenges on (i) the effectiveness of the result and (ii) the efficiency of computation. We propose a meaningful scoring function for insights to address (i). Then, we contribute a computation framework for top-k insights, together with a suite of optimization techniques (i.e., pruning, ordering, specialized cube, and computation sharing) to address (ii). Our experimental study on both real data and synthetic data verifies the effectiveness and efficiency of our proposed solution.

In rank-aware processing, user preferences are typically represented by a numeric weight per data attribute, collectively forming a weight vector. The score of an option (data record) is defined as the weighted sum of its individual attributes. The highest-scoring options across a set of alternatives (dataset) are shortlisted for the user as the recommended ones. In that setting, the user input is a vector (equivalently, a point) in a d-dimensional preference space, where d is the number of data attributes. In this paper we study the problem of determining in which regions of the preference space the weight vector should lie so that a given option (focal record) is among the top-k score-wise. In effect, these regions capture all possible user profiles for which the focal record is highly preferable, and are therefore essential in market impact analysis, potential customer identification, profile-based marketing, targeted advertising, etc. We refer to our problem as k-Shortlist Preference Region identification (kSPR), and exploit its computational geometric nature to develop a framework for its efficient (and exact) processing. Using real and synthetic benchmarks, we show that our most optimized algorithm outperforms by three orders of magnitude a competitor we constructed from previous work on a different problem.

High-dimensional$k$nearest neighbor (kNN) search has a wide range of applications in multimedia information retrieval. Existing disk-based$k$NN search methods incur significant I/O costs in the candidate refinement phase. In this paper, we propose to cache compact approximate representations of data points in main memory in order to reduce the candidate refinement time during$k$NN search. This problem raises two challenging issues: (i) which is the most effective encoding scheme for data points to support$k$NN search? and (ii) what is the optimal number of bits for encoding a data point? For (i), we formulate and solve a novel histogram optimization problem that decides the most effective encoding scheme. For (ii), we develop a cost model for automatically tuning the optimal number of bits for encoding points. In addition, our approach is generic and applicable to exact / approximate$k$NN search methods. Extensive experimental results on real datasets demonstrate that our proposal can accelerate the candidate refinement time of$k$NN search by at least an order of magnitude.

Commercial web search engines adopt parallel and replicated architecture in order to support high query throughput. In this paper, we investigate the effect of caching on the throughput in such a setting. A simple scheme, called uniform caching, would replicate the cache content to all servers. Unfortunately, it does not exploit the variations among queries, thus wasting memory space on caching the same cache content redundantly on multiple servers. To tackle this limitation, we propose a diversified caching problem, which aims to diversify the types of queries served by different servers, and maximize the sharing of terms among queries assigned to the same server. We show that it is NP-hard to find the optimal diversified caching scheme, and identify intuitive properties to seek good solutions. Then we present a framework with a suite of techniques and heuristics for diversified caching. Finally, we evaluate the proposed solution with competitors by using a real dataset and a real query log.