Set measurements are fundamental in numerous areas including network measurement, database queries, and data mining. These measurements are typically executed on multisets. Existing algorithms optimize a specific set measurement task, leading to sophisticated but narrowly focused solutions. This specialization often results in inefficiencies when multiple set measurement tasks are required simultaneously, consuming excessive computational and storage resources. This paper introduces DaVinci Sketch, a versatile sketch designed to efficiently handle various set measurement tasks using a single unified data structure. DaVinci Sketch employs a novel approach by utilizing a dedicated structure to store frequent elements, thereby reducing collisions among flows that have the most significant impact on results. Remarkably, DaVinci Sketch can simultaneously perform up to nine different measurement tasks with a single data structure and a unified operation, whereas other approaches typically support fewer tasks. The experimental results demonstrate that DaVinci Sketch achieves high accuracy across 9 measurement tasks. Furthermore, in multi-task scenarios, DaVinci Sketch significantly reduces the memory usage (by more than 59%) and achieves high throughput (more than 23 times faster than other methods).

Rapidly developing remote sensing technologies expand the volume and variety of hyperspectral images (HSIs). An HSI classification (HSIC) model should be able to adapt to new classes continually while retaining knowledge of previously learned classes to reduce training resources. However, popular HSIC models based on deep neural networks exhibit a significant performance decline in previously learned classes, known as the catastrophic forgetting phenomenon. To efficiently address this issue in HSIC, we propose an analytic continual learning method based on feature cross (CrossACL). CrossACL introduces a novel and training-free feature cross module (FCM) to better adapt to the increasingly complex feature space as the number of HSI classes increases. Furthermore, it utilizes an analytic recursive ridge regression classifier with a closed-form solution. This formulation achieves conditional equivalence between continual learning and joint training on all data seen so far, providing a theoretical guarantee against catastrophic forgetting. In addition, CrossACL introduces a simple but effective oversampling strategy to mitigate classification discrimination due to class-imbalanced HSI samples. Experiments on HSIC datasets demonstrate that CrossACL achieves competitive results compared with state-of-the-art methods at significantly lower computational consumption.

Sketch has been widely used in the field of large-scale data stream processing. However, common fixed-counter algorithms such as Count-Min Sketch have to allocate larger counters, which wastes a lot of memory due to the high skewness of real-world data streams. To reduce memory usage, we propose to dynamically adjust the counter size that matches the distribution of the data stream. We introduce BitMatcher, a fast global-adjusting algorithm that automatically adjusts the counter to the appropriate size to match the data stream. During stream processing, BitMatcher identifies items hashed into a bucket based on isolated fingerprints. If it overflows, BitMatcher changes the flag bits in the bucket and dynamically increases or shrinks the size of some counters in a fine-grained manner. BitMatcher can also relocate a cold item in the bucket with the idea of cuckoo hashing to preserve the potential hot item while achieving global load balancing. Through the above way of dealing with overflow caused by skewed data, BitMatcher precisely manipulates allocated bits and maximizes memory utilization. The experiments show that BitMatcher has high throughput and can outperform SOTA by up to 4 orders of magnitude in terms of accuracy. We also deployed BitMatcher on several platforms, showing its software and hardware scalability.

High-performance anti-spoofing countermeasures (CMs) have been widely used to protect automatic speaker verification systems by identifying and filtering spoofing speech. However, their performance degrades severely when confronted with out-of-domain (OOD) samples. To solve this issue, recent papers investigate the strategy that a CM can opt for abstention when it is not confident about the decision. In this paper, we develop an effective approach to enhance the performance of CMs with abstention. Specifically, we introduce supervised contrastive learning to group samples into known classes more tightly and employ data augmentation to enhance the diversity of known samples. The experiments are conducted on ASV spoof 2019 logical access corpus and another test set consisting of different OOD samples from other databases. With our scheme, CMs with abstention can achieve an equal error rate (EER) of 1.84 % on the LA test set and 0.86 % on the other test set. These results demonstrate that CMs trained with our approach show better OOD detection performance and can make more confident decisions.

Membership (membership query/membership testing) is a fundamental problem across databases, networks and security. However, previous research has primarily focused on either approximate solutions, such as Bloom Filters, or exact methods, like perfect hashing and dictionaries, without attempting to develop an integral theory. In this paper, we propose a unified and complete theory, namely chain rule, for general membership problems, which encompasses both approximate and exact membership as extreme cases. Building upon the chain rule, we introduce a straightforward yet versatile algorithm framework, namely ChainedFilter, to combine different elementary filters without losing information. Our evaluation results demonstrate that ChainedFilter improves performance of many applications including static dictionary, lossless data compression, Cuckoo Hashing, LSM-Tree and Learned Filters.