296 research outputs found
Perfect cuckoo filters
No full textBloom filters and cuckoo filters are used in many applications to reduce the amount of memory needed to check if an element belongs to a set. The main drawback of these filters is that with low probability, a positive is returned for an element that is not in the set. Recently, the concept of Bloom filters with a false positive free zone has been introduced showing that false positives can be avoided when the universe from which elements are taken and the number of elements inserted in the filter are both small. Unfortunately, this limits the use of such false positive free Bloom filters in many practical applications. In this paper, a false positive free, i.e. perfect, cuckoo filter is presented and evaluated. The proposed design supports universe sizes of billions of elements and stores millions of elements, making it practical for a wide range of applications. The perfect cuckoo filter can be also used to perform mapping, further extending the range of scenarios in which can be used. The benefits of the proposed perfect cuckoo filter are illustrated with two case studies: IP address blacklisting and longest prefix match for IP forwarding
Less-is-Better Protection (LBP) for memory errors in kNNs classifiers
No full textClassification is used in a wide range of applications to determine the class of a new element; for example, it can be used to determine whether an object is a pedestrian based on images captured by the safety sensors of a vehicle. Classifiers are commonly implemented using electronic components and thus, they are subject to errors in memories and combinational logic. In some cases, classifiers are used in safety critical applications and thus, they must operate reliably. Therefore, there is a need to protect classifiers against errors. The k Nearest Neighbors (kNNs) classifier is a simple, yet powerful algorithm that is widely used; its protection against errors in the neighbor computations has been recently studied. This paper considers the protection of kNNs classifiers against errors in the memory that stores the dataset used to select the neighbors. Initially, the effects of errors in the most common memory configurations (unprotected, Parity-Check protected and Single Error Correction-Double Error Detection (SEC-DED) protected) are assessed. The results show that surprisingly, for most datasets, it is better to leave the memory unprotected than to use error detection codes to discard the element affected by an error in terms of tolerance. This observation is then leveraged to develop Less-is-Better Protection (LBP), a technique that does not require any additional parity bits and achieves better error tolerance than Parity-Check for single bit errors (reducing the classification errors by 59% for the Iris dataset) and SEC-DED codes for double bit errors (reducing the classification errors by 42% for the Iris dataset).S. Liu and F. Lombardi would like to acknowledge the support of National Science Foundation, USA grants CCF-1953961 and 1812467, and P. Reviriego would like to acknowledge the support of the ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Ministry of Science and Innovation and by the Madrid Community research project TAPIR-CM P2018/TCS-4496
Cuckoo Filters and Bloom Filters: Comparison and Application to Packet Classification
No full textBloom filters are used to perform approximate membership checking in a wide range of applications in both computing and networking, but the recently introduced cuckoo filter is also gaining popularity. Therefore, it is of interest to compare both filters and provide insights into their features so that designers can make an informed decision when implementing approximate membership checking in a given application. This article first compares Bloom and cuckoo filters focusing on a packet classification application. The analysis identifies a shortcoming of cuckoo filters in terms of false positive rate when they do not operate close to full occupancy. Based on that observation, this article also proposes the use of a configurable bucket to improve the scaling of the false positive rate of the cuckoo filter with occupancy.Pedro Reviriego and David Larrabeiti would like to acknowledge the support of the ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Ministry of Science and Innovation and of the Madrid Community research project TAPIRCM grant no. P2018/TCS-4496. David Larrabeiti acknowledges the support of EU project PASSION, Grant Agreement 780326. Salvatore Pontarelli has been partly funded by the EU commission in the context of the 5G-PICTURE project, Grant Agreement 762057
Improving Packet Flow Counting With Fingerprint Counting
No full textIn many applications, there is a need to estimate the frequency of elements. For example, in networking to know the number of packets of each flow. This poses a challenge as the number of flows and packets per second can be very large and therefore an exact count would require a large amount of fast memory. In those cases, an alternative is to use data structures, commonly referred to as sketches, that provide an estimate of the frequency of elements using a much smaller amount of memory. For example, the Count Min Sketch (CMS) hashes each element to a few counters and returns as estimate the minimum value among them. The CMS in general overestimates the frequency of an element as other elements may also map to the same counters and increment them. In this letter, fingerprint counting, a scheme to reduce the counter overestimation is presented and evaluated. The main idea is to add a fingerprint to the counters and use it to check if consecutive increments to a counter belong to the same element. When they do not, the counters can be incremented by half a packet instead of a full packet thus reducing the overestimation. The evaluation results show that the proposed scheme is able to reduce the overestimation and improve the CMS accuracy. In more detail, the overestimation is reduced by more than 20% in many of the configurations tested reaching values over 50% in some cases. A scheme to encode the fingerprints in the counters that practically eliminates the additional memory required for the fingerprints is also presented. Therefore, the improvement in the accuracy is achieved with a negligible impact on the size of the memory needed to implement the CMS
{CFBF}: Reducing the Insertion Time of Cuckoo Filters With an Integrated Bloom Filter
No full textCuckoo filters (CFs) are an alternative to Bloom filters (BFs) that supports deletions and can often be configured to have a lower false positive rate. A drawback of cuckoo filters is that the insertion process is complex and requires a large number of memory accesses when the filter operates at high occupancy. Therefore, insertion complexity may limit the applicability of cuckoo filters in many networking applications that require fast updates of the filter contents. In this letter, the cuckoo filter is extended to integrate a Bloom filter that is used to improve the performance of insertions. The proposed CFBF does not require additional memory accesses for lookup operations and preserves the support for deletion of the original cuckoo filter. The CFBF targets hardware implementations where the Bloom filter can be checked with negligible cost and where the memory width can also be adjusted to the bucket size. The evaluation results show that it can be used to reduce worst case insertion time by a factor of ten and achieve an average insertion time similar to that of a lookup. The CFBF can support bursts of hundreds of insertions for large filters and moderate false positive rates. Therefore, it can enable the use of hardware implemented cuckoo filters in applications that need to support bursts of insertions or to provide a low worst case insertion time
More Accurate Streaming Cardinality Estimation With Vectorized Counters
No full textCardinality estimation, also known as count-distinct, is the problem of finding the number of different elements in a set with repeated elements. Among the many approximate algorithms proposed for this task, HyperLogLog (HLL) has established itself as the state of the art due to its ability to accurately estimate cardinality over a large range of values using a small memory footprint. When elements arrive in a stream, as in the case of most networking applications, improved techniques are possible. We specifically propose a new algorithm that improves the accuracy of cardinality estimation by grouping counters, and by using their new organization to further track all updates within a given counter size range (compared with just the last update as in the standard HLL). Results show that when using the same number of counters, one configuration of the new scheme reduces the relative error by approximately 0.86x using the same amount of memory as the streaming HLL and another configuration achieves a similar accuracy reducing the memory needed by approximately 0.85x
Fast Updates for Line-Rate {HyperLogLog} based Cardinality Estimation
No full textIn a network it is interesting to know the different number of flows that traverse a switch or link or the number of connections coming from a specific sub-network. This is generally known as cardinality estimation or count distinct. The HyperLogLog (HLL) algorithm is widely used to estimate cardinality with a small memory footprint and simple per packet operations. However, with current line rates approaching a Terabit per second and switches handling many Terabits per second, even implementing HLL is challenging. This is mostly due to a bottleneck in accessing the memory as a random position has to be accessed for each packet. In this letter, we present and evaluate Fast Update HLL (FU-HLL), a scheme that eliminates the need to access the memory for most packets. Results show that FU-HLL can indeed significantly reduce the number of memory accesses when the cardinality is much larger than the number of registers used in HLL as it is commonly the case in practical settings
Error-Tolerant Computation for Voting Classifiers With Multiple Classes
No full textIn supervised learning, labeled data are provided as inputs and then learning is used to classify new observations. Error tolerance should be guaranteed for classifiers when they are employed in critical applications. A widely used type of classifiers is based on voting among instances (referred to as single voter classifiers) or multiple voters (referred to as ensemble classifiers). When the classifiers are implemented on a processor, Time-Based Modular Redundancy (TBMR) techniques are often used for protection due to the inflexibility of the hardware. In TBMR, any single error can be handled at the cost of additional computing either once for detection or twice for correction after detection; however, this technique increases the computation overhead by at least 100%. The Voting Margin (VM) scheme has recently been proposed to reduce the computation overhead of TBMR, but this scheme has only been utilized for k Nearest Neighbors ( k NNs) classifiers with two classes. In this paper, the VM scheme is extended to multiple classes, as well as other voting classifiers by exploiting the intrinsic robustness of the algorithms. k NNs (that is a single voter classifier) and Random Forest (RF) (that is an ensemble classifier) are considered to evaluate the proposed scheme. Using multiple datasets, the results show that the proposed scheme significantly reduces the computation overhead by more than 70% for k NNs with good classification accuracy and by more than 90% for RF in all cases. However, when extended to multiple classes, the VM scheme for k NNs is not efficient for some datasets. In this paper, a new protection scheme referred to as k + 1 NNs is presented as an alternative option to provide efficient protection in those scenarios. In the new scheme, the computation overhead can be further reduced at the cost of allowing a very low percentage of errors that can modify the classification outcome.This work was supported in part by the ACHILLES
Project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Ministry of Economy and Competitivity, in part by the Department of Research and Innovation of Madrid Regional Authority, in part by the EMPATIA-CM Research Project (Reference Y2018/TCS-5046), and in part by NSF under Grants CCF-1953961 and 181246
The Artificial Papyrologist at Work
No full textThe chapter focuses on the recent advancements in Artificial Intelligence (AI) and Machine Learning (ML) applications within papyrological research. These technologies have a profound impact on the cognitive aspects involved in the papyrological workflow. Despite the notable achievements in Digital Papyrology, electronic tools and strategies applied to papyrological research have not yet replaced the human role in the most intellectual aspects. However, the increasing relevance of AI across various research domains now poses a challenge to the traditional role of “human” papyrologists. Ongoing projects are venturing into complex endeavors such as automating handwriting recognition, fragment restoration and reconstruction, recovery of carbonized papyri, filling in textual gaps, and stylometric analysis. This contribution aims to explore the theoretical and practical implications of these projects on the development of papyrological methodology, seeking to envision both the potentials and perils of this new “artificial papyrologist” in action. It will be shown how these latest developments can aid us in becoming better papyrologists without replacing our intellectual engagement with the objects of our study
- …
