Compressing sorted keys is a fundamental operation in data management and information retrieval. Inspired by the success of learned index, recent studies apply simple ML models to compress large-scale sorted keys, leading to the concept of learned compressor. Intuitively, learned compressors losslessly encode sorted keys by approximating them with an error-bounded ML model (e.g., a piecewise linear function) and a residual array to ensure lossless key restoration. However, determining the optimal configuration of underlying ML models to maximize compression efficacy is nontrivial. To address this, by analyzing the distribution characteristics of input keys, we propose BitTuner, a novel framework that automatically sets model hyper-parameters to provably achieve the best compression ratio. We demonstrate BitTuner on two real-world scenarios: inverted list compression and vectorDB codebook compression. The results show that BitTuner automates the parameter tuning procedure and achieves superior compression efficacy when compared to generic compressors such as LZ4 and LZMA.

Learned indexes have attracted significant research interest due to their potential to offer better space-time trade-offs compared to B+-tree variants. Among various learned indexes, the PGM-Index based on error-bounded piecewise linear approximation is an elegant data structure that has demonstrated provably superior performance over conventional B+-tree indexes. However, despite numerous efforts to optimize the design of the PGM-Index, few systematically study the root causes of performance mismatches observed in practice. In this paper, we explore two key research questions. Q1 : Why are PGM-Indexes theoretically effective? and Q2 : Why do PGM-Indexes underperform in practice? For Q1 , we show that for a set of N sorted keys, the PGM-Index can achieve a lookup time of O (log log N ) while using O ( N ) space. For Q2 , we identify that querying PGM-Indexes is highly memory-bound, where the internal index search operations often become the bottleneck. To fill the performance gap, we propose PGM++, a simple yet effective extension to the original PGM-Index that employs a mixture of different search strategies, with hyper-parameters automatically tuned through a cost model calibrated by theoretical findings. Extensive experiments show that, at comparable space costs, PGM++ speeds up index lookup queries by up to 2.31X and 1.56X when compared to the original PGM-Index and SOTA baselines.

The rapid advancements of generative artificial intelligence (GenAI) have recently led to renewed attention towards approximate nearest neighbor (ANN) search and vector databases (VectorDB). Among various ANN methodologies, vector quantization techniques like product quantization (PQ) are widely used to generate space-efficient representations for large-scale dense vectors. However, the code-books generated by PQ often reach several gigabytes in size, making them impractical for web-scale, high-dimensional vectors in resource-constrained environments like mobile devices. In this study, we propose SegPQ , a simple yet effective framework for losslessly compressing codebooks generated by any PQ variants, enabling efficient in-memory vector search on devices with limited memory. SegPQ represents the raw PQ codewords as a trained error-bounded piecewise linear approximation model (ϵ-PLA) and pre-computed low-bit residuals. We theoretically demonstrate that, with high probability, the number of bits per compressed codeword is 1.721 + ⌈log 2 ϵ OPT ⌉, where ϵ OPT is the optimal error parameter that can be determined by data characteristics. To accelerate query execution, we further design SIMD-aware query processing algorithms on compressed codebooks to fully exploit the hardware parallelism offered by modern architectures. Extensive experimental studies on real datasets showcase that, for 1 billion vectors, SegPQ reduces PQ codebook memory consumption by up to 4.7 x (approx. 851 MB ) while incurring only 3.3% additional query processing overhead caused by decompression.

Recently, crowdsourcing has emerged as a new computing paradigm to solve problems that need human intrinsic, such as image annotation. However, there are two limitations in existing crowdsourcing platforms, i.e. non-transparent incentive mechanism and isolated profiles of workers, which harms the interests of both requesters and workers. Meanwhile, Blockchain technology introduces a solution to build a transparent, immutable data model in the Byzantine environment. Moreover, Blockchain systems (e.g. Ethereum) can also support the Tuning-complete script called smart contracts. Thus, we are motivated to use the feature of the transparent data model and smart contract in Blockchain to address the two limitations. Based on the proposed solutions, we have designed a Blockchain based framework which supports foundations of general crowdsourcing platforms. In addition, our framework also has following novel features: (1) it provides the transparent incentive mechanisms; (2) it supports a trusted worker's profile sharing in a cross-platform mode.

With the success of Bitcoin, the technique behind it, Blockchain, is catching massive attention recently. Blockchain is a collection of several techniques like cryptology, P2P and distributed consensus protocol. The main idea of Blockchain is that nodes in the network keep the same distributed ledger. Because of this immutable ledger, a trusted bridge is built among parties without fully trust. Blockchain can be used in variety of areas, especially in financial fields, like supply chain management, cross-border payment and global bank settlement. Meanwhile, we can observe that mobile network is growing rapidly and nibbling the PC market. However, the current public Blockchain applications like Bitcoin or Ethereum require the nodes to store the whole ledger which exceeds the capacity of the mobile devices. Thus, we need to develop a blockchain platform to support mobile devices. In this demo, we introduce Jupiter, a mobile-based Blockchain platform which provides a novel concept called consensus unit (CU) to alleviate the storage problem of mobile. We present the system architecture and demonstrate several CU scenarios via Jupiter.

Recently, Blockchain becomes a hot research topic due to the success of Blockchain in many applications, such as cryptocurrency, smart contract, digital assets, distributed cloud storage and so on. The power of Blockchain is that it can achieve the consensus of an ordered set of transactions among nodes which do not trust each other, even with the existence of malicious nodes. However, compared to traditional databases, the current Blockchain technology still cannot handle a massive number of transactions, which is caused by many factors, such as the consensus protocol, structure of the blocks and storage challenge. Among them, the high storage requirement is a key factor that prevents the wide usage of Blockchain on various devices such as mobile phones or low-end PCs. In this paper, to address the storage challenge, we introduce a novel concept called Consensus Unit (CU), which organizes different nodes into one unit and lets them to store at least one copy of Blockchain data in the system together. Based on this idea, we further define the Blocks Assignment Optimization (BAO) problem which determines the optimal assignment of blocks such that the storage space is fully used and the query cost is minimized. We prove that the BAO problem is NP-hard. Thus, we propose three efficient heuristic algorithms to solve the static assignment problem. Furthermore, we present solutions to address the dynamic scenarios when new blocks arrive and nodes join or depart from the CU. To verify the effectiveness of CU, we have conducted extensive experiments on synthetic data and BLOCKBENCH [1]. The results have confirmed the superiority of CU in saving the storage and maintaining the system throughput.