In this paper, we present an advanced analysis of near optimal algorithms that use limited space to solve the frequency estimation, heavy hitters, frequent items, and top-k approximation in the bounded deletion model. We define the family of SpaceSaving± algorithms and explain why the original SpaceSaving± algorithm only works when insertions and deletions are not interleaved. Next, we propose the new Double SpaceSaving±, Unbiased Double SpaceSaving±, and Integrated SpaceSaving± algorithms and prove their correctness. The three proposed algorithms represent different trade-offs, in which Double SpaceSaving± can be extended to provide unbiased estimations while Integrated SpaceSaving± uses less space. Since data streams are often skewed, we present an improved analysis of these algorithms and show that errors do not depend on the hot items. We also demonstrate how to achieve relative error guarantees under mild assumptions. Moreover, we establish that the important mergeability property is satisfied by all three algorithms, which is essential for running the algorithms in distributed settings.

Log Structured Merge Trees (LSM-tree) based key-value stores are widely used in many storage systems to support a variety of operations such as updates, point reads, and range reads. Traditionally, the merge policy of LSM-trees organizes data into multiple levels of exponentially increasing capacity to support high-speed writes. However, we contend that the traditional merge policies are not optimized for reads. In this work, we present Autumn, a scalable and read-optimized LSM-tree based key-value store with near-optimal worst-case point and range read costs. The key idea in improving read performance is to dynamically adjust the capacity ratio between two adjacent levels as more data are stored. As a result, lower levels gradually increase their capacities and more actively merges. In particular, point and range read cost improves from the previous known O(logN) complexity to$O(\sqrt{logN})$in Autumn by applying the novel Garnering merge policy. While the Garnering merge policy optimizes for both point reads and range reads, it maintains high performance for writes by inherently prioritizing the merges in the lower levels, as Garnering schedules more merges for the lower levels. We implemented Autumn on top of RocksDB and LevelDB and experimentally show the gain in performance for real-world workloads.

Translating natural language questions into SQL queries (NL2SQL) is a challenging task of great practical importance. Prior work has extensively studied how to address NL2SQL using Large Language Models (LLMs) with solutions ranging from careful prompt engineering, to fine-tuning existing LLMs, or even training custom models. However, a remaining challenging problem in NL2SQL is the inherent ambiguity in the natural language questions asked by users. In this paper, we introduce Sphinteract, a framework designed to assist LLMs in generating high-quality SQL answers that accurately reflect the user intent. Our key insight to resolve ambiguity is to take into account minimal user feedback interactively. We introduce the Summarize, Review, Ask (SRA) paradigm, which guides LLMs in identifying ambiguities in NL2SQL tasks and generates targeted questions for the user to answer. We propose three different methods of how to process user feedback and generate SQL queries based on user input. Our experiments on the challenging KaggleDBQA and BIRD benchmarks demonstrate that by means of asking clarification questions to the user, LLMs can efficiently incorporate the feedback, resulting in accuracy improvements of up to 42%.

This errata article points out an implicit assumption in the work of four of us published in VLDB 2022. The SpaceSaving± algorithm in bounded deletion data stream presented in the paper implicitly assumed deletions happen after all insertions. When insertions and deletions are interleaved, that algorithm may severely underestimate item's frequency. We first illustrate this phenomenon by an example and then present a modified algorithm with minor changes to allow interleaving between insertions and deletions. We also include a pointer to a full analysis of the new algorithms.

System operators are often interested in extracting different feature streams from multi-dimensional data streams; and reporting their distributions at regular intervals, including the heavy hitters that contribute to the tail portion of the feature distribution. Satisfying these requirements to increase data rates with limited resources is challenging. This paper presents the design and implementation of Panakos that makes the best use of available resources to report a given feature's distribution accurately, its tail contributors, and other stream statistics (e.g., cardinality, entropy, etc.). Our key idea is to leverage the skewness inherent to most feature streams in the real world. We leverage this skewness by disentangling the feature stream into hot, warm, and cold items based on their feature values. We then use different data structures for tracking objects in each category. Panakos provides solid theoretical guarantees and achieves high performance for various tasks. We have implemented Panakos on both software and hardware and compared Panakos to other state-of-the-art sketches using synthetic and real-world datasets. The experimental results demonstrate that Panakos often achieves one order of magnitude better accuracy than the state-of-the-art solutions for a given memory budget.

In this paper, we propose the first deterministic algorithms to solve the frequency estimation and frequent item problems in the bounded-deletion model. We establish the space lower bound for solving the deterministic frequent items problem in the bounded-deletion model, and propose Lazy SpaceSaving ± and SpaceSaving ± algorithms with optimal space bound. We develop an efficient implementation of the SpaceSaving ± algorithm that minimizes the latency of update operations using novel data structures. The experimental evaluations testify that SpaceSaving ± has accurate frequency estimations and achieves very high recall and precision across different data distributions while using minimal space. Our experiments clearly demonstrate that, if allowed the same space, SpaceSaving± is more accurate than the state-of-the-art protocols with up to logU - 1/ logU of the items deleted, where U is the size of the input universe. Moreover, motivated by prior work, we propose Dyadic SpaceSaving ± , the first deterministic quantile approximation sketch in the bounded-deletion model.

Recently the long standing problem of optimal construction of quantile sketches was resolved by K arnin, L ang, and L iberty using the KLL sketch (FOCS 2016). The algorithm for KLL is restricted to online insert operations and no delete operations. For many real-world applications, it is necessary to support delete operations. When the data set is updated dynamically, i.e., when data elements are inserted and deleted, the quantile sketch should reflect the changes. In this paper, we propose KLL ± , the first quantile approximation algorithm to operate in the bounded deletion model to account for both inserts and deletes in a given data stream. KLL ± extends the functionality of KLL sketches to support arbitrary updates with small space overhead. The space bound for KLL ± is [EQUATION], where ∈ and δ are constants that determine precision and failure probability, and α bounds the number of deletions with respect to insert operations. The experimental evaluation of KLL ± highlights that with minimal space overhead, KLL ± achieves comparable accuracy in quantile approximation to KLL.