检索结果-内蒙古大学图书馆

An approximate L¹-difference algorithm or massive data streams

SIAM JOURNAL ON COMPUTING 2003年第1期32卷 131-151页

作者： Feigenbaum, J Kannan, S Strauss, MJ Viswanathan, M Yale Univ Dept Comp Sci New Haven CT 06520 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA AT&T Labs Res Florham Pk NJ 07932 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA

Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and the monitoring and operations of large systems. In network operations, raw data typically arrive in streams, and decisions must be made by algorithms that make one pass over each stream, throw much of the raw data away, and produce "synopses" or "sketches" for further processing. Moreover, network-generated massive data sets are often distributed: Several different, physically separated network elements may receive or generate data streams that, together, comprise one logical data set;to be of use in operations, the streams must be analyzed locally and their synopses sent to a central operations facility. The enormous scale, distributed nature, and one-pass processingrequirement on the data sets of interest must be addressed with new algorithmic techniques. We present one fundamental new technique here: a space-efficient, one-pass algorithm for approximating the L-1-difference Sigma(i)\a(i)-b(i)\ between two functions, when the function values a(i) and b(i) are given as data streams, and their order is chosen by an adversary. Our main technical innovation, which may be of interest outside the realm of massive data stream algorithmics, is a method of constructing families {V-j(s)} of limited-independence random variables that are range-summable, by which we mean that Sigma(j=0)(c-1) V-j(s) is computable in time polylog(c) for all seeds s. Our L-1-difference algorithm can be viewed as a "sketching" algorithm, in the sense of [Broder et al., J. Comput. System Sci., 60 (2000), pp. 630-659], and our technique performs better than that of Broder et al. when used to approximate the symmetric difference of two sets with small symmetric difference.

关键词： streaming algorithms distance approximation

来源：评论

学校读者我要写书评

暂无评论

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

引用

ACM TRANSACTIONS ON algorithms 2019年第1期15卷 1–27页

作者： Bhattacharyya, Arnab Dey, Palash Woodruff, David P. Indian Inst Sci CSA Dept Bangalore Karnataka India IIT Kharagpur CSE Dept Kharagpur W Bengal India Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Indian Inst Technol Dept Comp Sci & Engn A-204 Kharagpur 721302 W Bengal India

We give the first optimal bounds for returning the l(1)-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in {1, 2,...,n} and parameters 0 < epsilon < phi <= 1, let f(i) denote the frequency of item I, i.e., the number of times item i occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items i for which f(i) >= phi m, returns no items j for which f(j) <= (phi - epsilon)m, and returns approximations (f) over tilde (i) with vertical bar(f) over tilde (i) - f(i)vertical bar <= epsilon m for each item i that it returns. Our algorithm uses O(epsilon(-1) log phi(-1) + phi(-1) log n + log log m) bits of space, processes each stream update in O(1) worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive epsilon m error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on algorithms for Data Streams for the case of l(1)-heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.

关键词： Heavy hitters streaming algorithms voting winner determination

来源：评论

学校读者我要写书评

暂无评论

Tracking triadic cardinality distributions for burst detection in high-speed graph streams

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2021年第4期63卷 939-969页

作者： Zhao, Junzhou Wang, Pinghui Chen, Zhouguo Ding, Jianwei Lui, John C. S. Towsley, Don Guan, Xiaohong Xi An Jiao Tong Univ MOE Key Lab Intelligent Networks & Network Secur Xian 710049 Peoples R China Xi An Jiao Tong Univ Shenzhen Res Inst Shenzhen 518057 Peoples R China China Elect Technol Grp Corp Sci & Technol Commun Secur Lab Res Inst 30 Chengdu 610041 Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China Univ Massachusetts Sch Comp Sci Amherst MA 01003 USA

In everyday life, we often observe unusually frequent interactions among people before or during important events, e.g., people send/receive more greetings to/from their friends on holidays than regular days. We also observe that some videos or hashtags suddenly go viral through people's sharing on online social networks (OSNs). Do these seemingly different phenomena share a common structure? All these phenomena are associated with the sudden surges of node interactions in networks, which we call "bursts" in this work. We uncover that, in many scenarios, the emergence of a burst is accompanied with the formation of triangles in networks. This finding motivates us to propose a new and robust method for burst detection on an OSN. We first introduce a new measure, i.e., "triadic cardinality distribution," corresponding to the fractions of nodes with different numbers of triangles, i.e., triadic cardinalities, in a network. We show that this distribution not only changes when a burst occurs, but it also has a robustness property that it is immunized against common spamming social-bot attacks. Hence, by tracking triadic cardinality distributions, we can more reliably detect bursts than simply counting node interactions on an OSN. To avoid handling massive activity data generated by OSN users during the triadic tracking, we design an efficient "sample-estimate" framework to provide maximum likelihood estimate of the triadic cardinality distribution. We propose several sampling methods and provide insights into their performance difference through both theoretical analysis and empirical experiments on real-world networks.

关键词： Burst detection Graph sampling streaming algorithms Online social network Estimation theory

来源：评论

学校读者我要写书评

暂无评论

A High-Throughput Hardware Accelerator for Network Entropy Estimation Using Sketches

引用

IEEE ACCESS 2021年 9卷 85823-85838页

作者： Soto, Javier E. Ubisse, Paulo Fernandez, Yaime Hernandez, Cecilia Figueroa, Miguel Univ Concepcion Elect Engn Dept Concepcion 4030000 Chile Univ Concepcion Comp Sci Dept Concepcion 4030000 Chile Ctr Biotechnol & Bioengn CeBiB Santiago 8370456 Chile

Network traffic monitoring uses empirical entropy to detect anomalous events such as various types of attacks. However, the exact computation of the entropy in high-speed networks is a difficult process due to the limited memory resources available in the data plane hardware. In this paper, we present a method and hardware accelerator to approximate the empirical entropy of a large data set with high throughput and sublinear memory requirements. Our method uses streaming algorithms that exploit the fine-grained parallelism of existing hardware platforms for data plane processing, such as field-programmable gate arrays (FPGAs). The method uses sketches to compute the cardinality of the stream and the frequencies of the top-K elements on line, and then it estimates the contribution to the entropy of the rest of the stream assuming a simple uniform distribution for these elements. Implemented on a Xilinx UltraScale+ ZCU102 FPGA, the accelerator implements the method using only on-chip memory, with less than 50% resource usage. Tested on real network traces of up to 120 million packets and more than 5 million flows, the accelerator estimates the empirical entropy with less than 1.5% mean relative error and 21 mu s latency, and supports a minimum throughput of 204 gigabits per second.

关键词： Empirical entropy network monitoring hardware acceleration field-programmable gate arrays streaming algorithms sketches

来源：评论

学校读者我要写书评

暂无评论

Identifying Taxonomic Units in Metagenomic DNA Streams on Mobile Devices

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第2期20卷 1092-1103页

作者： Zheng, Vicky Sariyuce, Ahmet Erdem Zola, Jaroslaw Univ Buffalo Dept Comp Sci Buffalo NY 14260 USA

With the emergence of portable DNA sequencers, such as Oxford Nanopore Technology MinION, metagenomic DNA sequencing can be performed in real-time and directly in the field. However, because metagenomic DNA analysis tasks, e.g., classification, taxonomic units assignment, etc., are compute and memory intensive, and the available methods are designed for batch processing, the current metagenomic tools are not well suited for mobile devices. In this work, we propose a new memory-efficient approach to identify Operational Taxonomic Units (OTUs) in metagenomic DNA streams on mobile devices. Our method is based on finding connected components in overlap graphs constructed over a real-time stream of long DNA reads as produced by the MinION platform. We propose an efficient algorithm to maintain connected components when an overlap graph is streamed and show how redundant information can be removed from the stream by transitive closures. We also propose how our algorithms can be integrated into a larger DNA analysis pipeline tailored for mobile computing. Through experiments on simulated and real-world metagenomic data, executed on the actual mobile device, we demonstrate that our resulting solution is able to recover OTUs with high precision. Our experiments also demonstrate the compounding benefits of introducing feedback loops in the DNA analysis pipeline.

关键词： Connected components metagenomics nanopore sequencing streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for Sliding Bloom Filters

引用

ALGORITHMICA 2015年第4期73卷 652-672页

作者： Naor, Moni Yogev, Eylon Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel

A Bloom filter is a method for reducing the space (memory) required for representing a set by allowing a small error probability. In this paper we consider a Sliding Bloom Filter: a data structure that, given a stream of elements, supports membership queries of the set of the last n elements (a sliding window), while allowing a small error probability and a slackness parameter. The problem of sliding Bloom filters has appeared in the literature in several communities, but this work is the first theoretical investigation of it. We formally define the data structure and its relevant parameters and analyze the time and memory requirements needed to achieve them. We give a low space construction that runs in time per update with high probability (that is, for all sequences with high probability all operations take constant time) and provide an almost matching lower bound on the space that shows that our construction has the best possible space consumption up to an additive lower order term.

关键词： Data structures Bloom filter streaming algorithms Lower bounds Hash tables

来源：评论

学校读者我要写书评

暂无评论

ProbMinHash - A Class of Locality-Sensitive Hash algorithms for the (Probability) Jaccard Similarity

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第7期34卷 3491-3506页

作者： Ertl, Otmar Dynatrace Res A-4020 Linz Austria

The probability Jaccard similarity was recently proposed as a natural generalization of the Jaccard similarity to measure the proximity of sets whose elements are associated with relative frequencies or probabilities. In combination with a hash algorithm that maps those weighted sets to compact signatures which allow fast estimation of pairwise similarities, it constitutes a valuable method for big data applications such as near-duplicate detection, nearest neighbor search, or clustering. This paper introduces a class of one-pass locality-sensitive hash algorithms that are orders of magnitude faster than the original approach. The performance gain is achieved by calculating signature components not independently, but collectively. Four different algorithms are proposed based on this idea. Two of them are statistically equivalent to the original approach and can be used as drop-in replacements. The other two may even improve the estimation error by introducing statistical dependence between signature components. Moreover, the presented techniques can be specialized for the conventional Jaccard similarity, resulting in highly efficient algorithms that outperform traditional minwise hashing and that are able to compete with the state of the art.

关键词： Clustering algorithms Device-to-device communication Estimation error Indexes Measurement Time complexity Minwise hashing Jaccard similarity locality-sensitive hashing streaming algorithms probabilistic data structures

来源：评论

学校读者我要写书评

暂无评论

An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024年第7期35卷 9428-9442页

作者： Wang, Chenhao Yi, Qianxin Liao, Xiuwu Wang, Yao Xi An Jiao Tong Univ Ctr Intelligent Decis Making & Machine Learning Sch Management Xian 710049 Peoples R China

Frequent Directions, as a deterministic matrix sketching technique, has been proposed for tackling low-rank approximation problems. This method has a high degree of accuracy and practicality, but experiences a lot of computational cost for large-scale data. Several recent works on the randomized version of Frequent Directions greatly improve the computational efficiency, but unfortunately sacrifice some precision. To remedy such issue, this paper aims to find a more accurate projection subspace to further improve the efficiency and effectiveness of the existing Frequent Directions techniques. Specifically, by utilizing the power of Block Krylov Iteration and random projection technique, this paper presents a fast and accurate Frequent Directions algorithm named as r-BKIFD. The rigorous theoretical analysis shows that the proposed r-BKIFD has a comparable error bound with original Frequent Directions, and the approximation error can be arbitrarily small when the number of iterations is chosen appropriately. Extensive experimental results on both synthetic and real data further demonstrate the superiority of r-BKIFD over several popular Frequent Directions algorithms, both in terms of computational efficiency and accuracy.

关键词： Block Krylov iteration frequent directions (FDs) low-rank approximation randomized sketching streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Periodicity in Data Streams with Wildcards

引用

THEORY OF COMPUTING SYSTEMS 2020年第1期64卷 177-197页

作者： Ergun, Funda Grigorescu, Elena Azer, Erfan Sadeqi Zhou, Samson Indiana Univ Sch Informat & Comp Bloomington IN 47405 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We investigate the problem of detecting periodic trends within a string S of length n, arriving in the streaming model, containing at most k wildcard characters, where k = o(n). A wildcard character is a special character that can be assigned any other character. We say that S has wildcard-period p if there exists an assignment to each of the wildcard characters so that in the resulting stream the prefix of length n - p equals the suffix of length n - p. We present a two-pass streaming algorithm that computes wildcard-periods of S using O(k3 polylog n) bits of space, while we also show that this problem cannot be solved in sublinear space in one pass. We also give a one-pass randomized streaming algorithm that computes all wildcard-periods p of S withp < n2 and no wildcard characters appearing in the last p symbols of S, using O(k3 log9 n) space.

关键词： streaming algorithms Periodicity Wildcards Randomized algorithms String algorithms

来源：评论

学校读者我要写书评

暂无评论

On scalable attack detection in the network

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2007年第1期15卷 14-25页

作者： Kompella, Ramana Rao Singh, Sumeet Varghese, George Univ Calif San Diego Dept Comp Sci La Jolla CA 92093 USA

Current intrusion detection and prevention systems seek to detect a wide class of network intrusions (e.g., DoS attacks, worms, port scans) at network vantage points. Unfortunately, even today, many IDS systems we know of keep per-connection or per-flow state to detect malicious TCP flows. Thus, it is hardly surprising that these IDS systems have not scaled to multi-gigabit speeds. By contrast, both router lookups and fair queuing have scaled to high speeds using aggregation via prefix lookups or DiffServ. Thus, in this paper, we initiate research into the question as to whether one can detect attacks without keeping per-flow state. We will show that such aggregation, while making fast implementations possible, immediately causes two problems. First, aggregation can cause behavioral aliasing where, for example, good behaviors can aggregate to look like bad behaviors. Second, aggregated schemes are susceptible to spoofing by which the intruder sends attacks that have appropriate aggregate behaviors. We examine a wide variety of DoS and scanning attacks and show that several categories (bandwidth based, claim-and-hold, port-scanning) can be scalably detected. In addition to existing approaches for scalable attack detection, we propose a novel data structure called partial completion filters (PCFs) that can detect claim-and-hold attacks scalably in the network. We analyze PCFs both analytically and using experiments on real network traces,to demonstrate how we can tune PCFs to achieve extremely low false positive and false negative probabilities.

关键词： data structures denial of service network attacks routers scanning streaming algorithms Syn flooding

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：