Learned indexes, which model key-value data structures by machine learning models, have been extensively studied. However, the fastest immutable learned indexes (e.g., RMI) do not provide the same tight lookup bounds as classical indexes such as B-trees. There are learned indexes that provide tight bounds (e.g., PGM) but those fall short in query performance. This gives rise to an interesting open question: whether there exists a learned index that simultaneously achieves state-of-the-art empirical performance and matching complexity? In this paper, we give a positive answer to this standing problem.We propose two new online model-building policies: (1) simplifying distribution by the adoption of a proper granularity (i.e., grouping multiple keys together for model-building) and (2) actively tuning distribution through key repositioning. Additionally, we introduce a general framework that combines these two policies for performance optimization under a given memory budget. We put everything together to design VEGA, a learned index that simultaneously achieves competitive theoretical and empirical performance compared to state-of-the-art learned indexes. We conducted extensive evaluations, demonstrating VEGA achieves both better lookup and building performance.

Estimating per-flow cardinality from high-speed data streams has many applications such as anomaly detection and resource allocation. Yet despite tracking single flow cardinality with approximation algorithms offered, there remain algorithmical challenges for monitoring multi-flows especially under unbalanced cardinality distribution: existing methods adopt a uniform sketch layout and incur a large memory footprint to achieve high accuracy. Furthermore, they are hard to implement in the compact hardware used for line-rate processing. In this paper, we propose Couper, a memory-efficient measurement framework that can estimate cardinality for multi-flows under unbalanced cardinality distribution. We propose a two-layer structure based on a classic coupon collector's principle, where numerous mice flows are confined to the first layer and only the potential elephant flows are allowed to enter the second layer. Our two-layer structure can better fit the unbalanced cardinality distribution in practice and achieve much higher memory efficiency. We implement Couper in both software and hardware. Extensive evaluation under real-world and synthetic data traces show more than 20× improvements in terms of memory-efficiency compared to state-of-the-art.

Marketing optimization plays an important role to enhance user engagement in online Internet platforms. Existing studies usually formulate this problem as a budget allocation problem and solve it by utilizing two fully decoupled stages, i.e., machine learning (ML) and operation research (OR). However, the learning objective in ML does not take account of the downstream optimization task in OR, which causes that the prediction accuracy in ML may be not positively related to the decision quality.

Online controlled experiments play a crucial role in enabling data-driven decisions across a wide range of companies. Variance reduction is an effective technique to improve the sensitivity of experiments, achieving higher statistical power while using fewer samples and shorter experimental periods. However, typical variance reduction methods (e.g., regression-adjusted estimators) are built upon the intuitional assumption of Gaussian distributions and cannot properly characterize the real business metrics with heavy-tailed distributions. Furthermore, outliers diminish the correlation between pre-experiment covariates and outcome metrics, greatly limiting the effectiveness of variance reduction.

Estimating per-flow cardinality from high-speed data streams has many applications such as anomaly detection and resource allocation. Yet despite tracking single flow cardinality with approximation algorithms offered, there remain algorithmical challenges for monitoring multi-flows especially under unbalanced cardinality distribution: existing methods adopt a uniform sketch layout and incur a large memory footprint to achieve high accuracy. Furthermore, they are hard to implement in the compact hardware used for line-rate processing.In this paper, we propose Couper, a memory-efficient measurement framework that can estimate cardinality for multi-flows under unbalanced cardinality distribution. We propose a two-layer structure based on a classic coupon collector’s principle, where numerous mice flows are confined to the first layer and only the potential elephant flows are allowed to enter the second layer. Our two-layer structure can better fit the unbalanced cardinality distribution in practice and achieve much higher memory efficiency. We implement Couper in both software and hardware. Extensive evaluation under real-world and synthetic data traces show more than 20× improvements in terms of memory-efficiency compared to state-of-the-art.

Classic contextual combinatorial multi-armed bandit problems aim to maximize the expected cumulative joint reward in the long run, where a learner plays a set of arms (i.e., a super arm) with time-invariant linear rewards of context features in each round. However, in many real-world applications, linear-reward assumptions often fail to be satisfied and the environment is in general non-stationary, leading to low performance with the bandit models above. Existing works fail to deal with non-linear rewards in the non-stationary environment and the algorithmic challenge remains. In this paper, we initiate the study of a non-stationary neural contextual combinatorial bandit problem, where the reward function of each individual arm can be estimated by a deep neural network based on boundedness assumption and a time-variant reward mapping function. Furthermore, we design an algorithm NNCMAB, which dynamically partitions the context subspace into multiple subspaces and fits reward mapping functions for each subspace by neural networks such that only the models of related subspaces are re-trained when local environment changes happen. NNCMAB can provably achieve $\tilde{O}\left(T^{\frac{3}{4}}+\sqrt{T}N_{c}\right)$ regret, where T is the number of rounds, and $N_{c}$ is a parameter associated with the distribution change. Evaluation results under synthetic and real-world LastFM datasets show that NNCMAB significantly outperforms other state-of-the-art with both linear and non-linear individual rewards under non-stationary environments.

Approximate membership query (AMQ) data structures can efficiently indicate whether an element exists in a data set. Therefore, they are widely used in data mining applications such as IoT streaming data mining, anomaly detection, duplicate detection, record linkage, and community discovery. The data amount to be processed in real-world applications often changes frequently and dynamically. Thus, before using the AMQ data structures, it is necessary to configure their capacity to the maximum number of elements that will be stored during runtime. We observe that when the number of elements stored in an AMQ data structure is lower than its capacity, a significant amount of space is wasted, making the false positive rate much higher than expected. To tackle this problem, we propose the variable-length encoding framework. It dynamically adjusts the encoding length of each element according to the number of elements stored in the AMQ data structure. Based on this design, the variable-length encoding framework can make full use of the memory space allocated to AMQ data structures, thereby improving the space efficiency and reducing the false positive rate. In addition, as a general encoding scheme, the variable-length encoding framework can be widely used in different types of AMQ data structures. Theoretical analysis and evaluation results show that AMQ data structures using the variable-length encoding framework have significantly lower false positive rates compared with state-of-the-art AMQ data structures. For example, when the load factor is 25%, the variable-length encoding framework can reduce the false positive rate of AMQ data structures by 88.15% on average (up to 99.40%).

Approximate query processing (AQP) is one of the key techniques to cope with big data querying problem on account that it obtains approximate answers efficiently. To address non-trivial sample selection and heavy sampling cost issues in AQP, we propose ShadowAQP, an efficient and accurate approach based on attribute-oriented sample size allocation and data generation. We select samples according to group-by and join attributes, and determine the sample size for each group of unique value combinations to improve query accuracy. We design a conditional variational autoencoder model with automatic table data encoding and model update strategies. To further improve accuracy and efficiency, we propose a set of extensions, including parallel multi-round sampling aggregation, data outlier-aware sampling, and dimension reduction optimization. Evaluation results on diversified datasets show that, compared with SOTA approaches, ShadowAQP achieves 5.8× query speed performance improvement on average (up to 12.8×), while reducing query error by 74% on average (up to 95%) at the same time.

The approximate membership query (AMQ) data structure is a kind of space-efficient probabilistic data structure. It can approximately indicate whether an element exists in a set. The AMQ data structure has been widely used in database indexing, network security, IoT applications, etc. Resizing is an extensively utilized operation of the AMQ data structure, but it can lead to system performance degradation. We summarize two main problems that lead to such degradation. Specifically, one of them is that the resizing operation can block other operations, while the other is that the performance of AMQ structures will deteriorate after multiple resizing operations. However, existing related work cannot alleviate both of them. Therefore, we propose a novel AMQ data structure called bamboo filter, which can alleviate the two problems simultaneously. Bamboo filters can insert, search and delete an element in constant time. Moreover, bamboo filters can dynamically resize in a fine-grained way according to the number of contained elements. Experimental results show that bamboo filters significantly outperform state-of-the-art resizable AMQ data structures in insertion, lookup, and deletion operations. For example, bamboo filters achieve$\mathbf{2.46}\times$lookup throughput of the dynamic cuckoo filter, on average.

Online bipartite matching has attracted wide interest since it can successfully model the popular online car-hailing problem and sharing economy. Existing works consider this problem under either adversary setting or i.i.d. setting. The former is too pessimistic to improve the performance in the general case; the latter is too optimistic to deal with the varying distribution of vertices. In this article, we initiate the study of the non-stationary online bipartite matching problem, which allows the distribution of vertices to vary with time and is more practical. We divide the non-stationary online bipartite matching problem into two subproblems, the matching problem and the selecting problem, and solve them individually. Combining Batch algorithms and deep Q-learning networks, we first construct a candidate algorithm set to solve the matching problem. For the selecting problem, we use a classical online learning algorithm, Exp3, as a selector algorithm and derive a theoretical bound. We further propose CDUCB as a selector algorithm by integrating distribution change detection into UCB. Rigorous theoretical analysis demonstrates that the performance of our proposed algorithms is no worse than that of any candidate algorithms in terms of competitive ratio. Finally, extensive experiments show that our proposed algorithms have much higher performance for the non-stationary online bipartite matching problem comparing to the state-of-the-art.