检索结果-南通市图书馆

Rhombus Sketch:自适应和准确的流数据Sketch

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

吉林大学学报（工学版） 2022年第4期52卷 874-884页

作者：魏晓辉苗艳微王兴旺吉林大学计算机科学与技术学院长春130012 吉林大学符号计算与知识工程教育部重点实验室长春130012

记录数据出现的次数(频数估计)是流数据管理的一类重要任务。在该类任务的解决方案中,Sketch是内存使用效率较高的数据结构之一。目前的多层Sketch方案,通常使用相同长度的计数器记录数据能够到达的最高层级。然而,数据频数的高度偏斜... 详细信息

记录数据出现的次数(频数估计)是流数据管理的一类重要任务。在该类任务的解决方案中,Sketch是内存使用效率较高的数据结构之一。目前的多层Sketch方案,通常使用相同长度的计数器记录数据能够到达的最高层级。然而,数据频数的高度偏斜会导致部分计数器的高位内存被浪费。另一方面,由于数据分布是不断变化的,静态的Sketch数据结构会造成内存分配不合理的问题。为了解决上述问题,本文提出一种弹性层级结构Rhombus Sketch,能够按需将计数器分配给数据,并通过估计数据的分布动态调整内存分配。实验结果表明,相比于其他典型Sketch方法,特别是在内存紧张的情况下,Rhombus Sketch的准确性有明显的提高。

关键词：计算机应用数据流近似算法弹性 Sketch

维普期刊数据库

Sketch simplification guided by complex agglomeration

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2019年第5期62卷 145-160页

作者： Yue LIU Xuemei LI Pengbo BO Xifeng GAO School of Computer Science and Technology Shandong University School of Computer Science and Technology Harbin Institute of Technology School of Software Shandong University Courant Institute of Mathematical Sciences New York University

We propose a novel method for vector Sketch simplification based on the simplification of the geometric structure that is extracted from the input vector graph, which can be referred to as a base complex.Unlike the sets of strokes, which are treated in the existing approaches, a base complex is considered to be a collection of various geometric primitives. Guided by the shape similarity metrics that are defined for the base complex, an agglomeration procedure is proposed to simplify the base complex by iteratively merging a pair of geometric primitives that exhibit the minimum cost into a new one. This simplified base complex is finally converted into a simplified vector graph. Our algorithm is computationally efficient and is able to retain a large amount of useful shape information from the original vector graph, thereby achieving a tradeoff between efficiency and geometric fidelity. Furthermore, the level of simplification of the input vector graph can be easily controlled using a single threshold in our method. We make comparisons with some existing methods using the datasets that have been provided in the corresponding studies as well as using different styles of Sketches drawn by artists. Thus, our experiments demonstrate the computational efficiency of our method and its capability for producing the desirable results.

关键词： Sketch simplification base complex iterative merging

基于Sketch的持续流检测及压缩算法研究

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

基于Sketch的持续流检测及压缩算法研究

作者：单源超广西大学

学位级别：硕士

Sketch是一类利用概要数据结构记录海量数据信息的算法,具有低内存开销和高精度的优点,基于Sketch的测量方法已经成为网络流量测量领域的主流研究方向。持续流检测(Persistent Flow Detection)是一种网络流量测量任务,它关注于那些在多... 详细信息

Sketch是一类利用概要数据结构记录海量数据信息的算法,具有低内存开销和高精度的优点,基于Sketch的测量方法已经成为网络流量测量领域的主流研究方向。持续流检测(Persistent Flow Detection)是一种网络流量测量任务,它关注于那些在多个时间窗内持续存在的异常流量,这些异常流量很有可能是一些潜在的网络攻击。Sketch压缩是一种数据处理方法,它将Sketch在测量任务中获取的流量信息进行压缩,用于减少在分布式测量系统中上传信息的通信开销。然而,现有研究在持续流检测和Sketch压缩两个工作中存在以下问题:现有Sketch算法在小内存场景下对持续流的测量并不精准;现有Sketch压缩算法很难同时保证压缩精度和快速压缩。针对以上两点问题,本文对基于Sketch的持续流检测及压缩算法展开了研究,主要贡献如下:(1)通过分析现有研究和验证性实验,本文发现现有算法中“不公平的”更新策略会导致持续流检测精度降低,并提出了一种新的基于Sketch的持续流检测算法Fair-Replacing,设计了全新的数据结构和更新策略。Fair-Replacing通过使用布隆过滤器(Bloom filter)和标志位对网络数据包进行过滤和控制,以保证当前时间窗内到达的流都有一次“公平的”机会来记录流键,从而提升检测精度。本文对算法的时空复杂度和误差边界进行了理论分析,并在多个测量场景下进行仿真实验。实验结果表明,FairReplacing比现有算法在检测精度上平均提升了21.46%。(2)通过分析现有Sketch压缩算法的问题,本文提出了基于先验知识的Sketch压缩算法Fast-Mapping。Fast-Mapping通过Sketch历史桶值的分布对压缩数据进行映射,将更相似的桶值聚合在一起,从而完成低误差的压缩。本文对算法在压缩过程中的时间复杂度和压缩误差进行了理论分析,并在多个压缩场景下进行仿真实验。实验结果表明,Fast-Mapping相比其他算法,平均降低了7.34倍的压缩误差,减少了3.45倍的压缩时间。综上所述,本文提出的Fair-Replacing、Fast-Mapping对基于Sketch的持续流检测及压缩工作具有一定的参考价值。

关键词：网络流量测量 Sketch 持续流检测 Sketch压缩

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于双阶段Sketch的长流检测算法研究

基于双阶段Sketch的长流检测算法研究

作者：李潮晨大连海事大学

学位级别：硕士

长流检测对于负载均衡,流量工程和入侵检测等方面具有重要意义。网络流量呈现重尾分布,即大多数流包含较少数量的报文,而很小一部分流包含大量报文。从网络流量中检测出长流可以更好的了解网络行为,对网络管理有重要帮助。为了匹配高速... 详细信息

长流检测对于负载均衡,流量工程和入侵检测等方面具有重要意义。网络流量呈现重尾分布,即大多数流包含较少数量的报文,而很小一部分流包含大量报文。从网络流量中检测出长流可以更好的了解网络行为,对网络管理有重要帮助。为了匹配高速网络中的数据传输效率,在读写速度快的SRAM进行长流检测是很有必要的。Sketch是一种概率性的数据结构,可以使用较小的内存来存储和查询给定的多项集中任何一个项的频率,可以很好地用于长流检测,但是现存的Sketch通常使用许多具有相同大小的计数器来记录流中的报文的数量,因此这些计数器必须足够大,以容纳最大流,由于网络中大多数流都是非长流,只有很少一部分是长流,因此许多计数器中记录了很小的值,这样会造成一部分的空间浪费。本文提出了一种基于双阶段Sketch的长流检测算法(Algorithm for Detecting Elephant Flows through Two-Stage Sketch,TSS)。TSS算法的结构由两部分组成:一部分为light part,另一部分为heavy part。TSS算法的核心思想是将长流和非长流进行动态存储,使得非长流存储在light part中,而长流由light part与heavy part共同存储,从而优化内存效率。为了评价TSS算法在长流检测方面的性能,首先针对算法的误差范围进行理论分析,然后使用三个在不同网络环境下收集的真实Trace进行了大量实验,并且与其他三种算法进行了比较。从理论分析以及实验结果表明,TSS在长流检测方面具有更好的性能。

关键词：长流 Sketch 概率估计双阶段

面向大流检测的UA-Sketch及滑动窗口算法研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向大流检测的UA-Sketch及滑动窗口算法研究

作者：李琳广西大学

学位级别：硕士

大流检测(Heavy flow detection)是网络测量的一项重要任务。在大规模网络中,由于内存有限和链路容量较低,准确检测大流具有挑战性。Sketch是一种基于概率的数据结构,能够使用更小的内存资源来准确地存储流信息。相比于传统网络测量算法... 详细信息

大流检测(Heavy flow detection)是网络测量的一项重要任务。在大规模网络中,由于内存有限和链路容量较低,准确检测大流具有挑战性。Sketch是一种基于概率的数据结构,能够使用更小的内存资源来准确地存储流信息。相比于传统网络测量算法,基于Sketch的网络测量算法(简称为Sketch算法)能在有限资源开销下实现精准的每包测量,其主要分为插入和查询两部分,不同算法在插入流的数据包时会有不同的流替换策略。在高速网络中,现有Sketch算法在内存受限时检测大流存在检测准确性和处理速度低的问题。因此本文提出基于连续到达包数的检测大流算法UASketch(Uninterrupted Arrival Sketch)和支持滑动窗口的大流检测算法Moving-Sketch。本文贡献如下:(1)现有Sketch算法都是使用流大小决策流替换策略,在小流数量远多于大流的网络场景下,大流在记录的流大小值还很小时被频繁错误替换,大流的流大小被低估,导致大流检测准确性降低。本文通过一系列模拟仿真实验揭示了这一问题,并发现连续到达的数据包数量(Uninterrupted Arrival packet count,简称为UA值)能够为Sketch算法检测大流提供有利依据。本文基于此提出一种基于UA值的检测大流算法UA-Sketch,该算法能够在保证数据包检测速度的同时,提高大流检测的准确性。本文对算法在基于轨迹驱动的仿真和OVS(Open v Switch)环境下进行了实验,实验结果表明,即使在较低的内存环境下,UA-Sketch与MV-Sketch和Elastic Sketch相比有更高的大流检测准确性,在F1 Score中平均提高了3.5倍。(2)现有Sketch算法在引用滑动窗口模型对近期的大流进行检测时,存在过期数据未能及时删除的问题,这导致大流检测的准确性较低。本文提出了一种支持滑动窗口的大流检测算法Moving-Sketch,其使用流键和周期作哈希键值和以概率决策流替换操作,能够有效提高滑动窗口内大流检测的准确性。本文不仅分析了Moving-Sketch的空间复杂度,时间复杂度和大流检测误差,而且通过基于轨迹驱动的仿真实验表明,MovingSketch的平均相对误差(Average Relative Error,ARE)比Sliding Sketch平均降低了93.3%。本文的研究工作对网络测量领域的算法研究与实际应用有一定的参考价值。

关键词： Sketch 网络测量大流检测连续到达滑动窗口

基于内存高效Sketch的超级主机识别与网络主机信任评估

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于内存高效Sketch的超级主机识别与网络主机信任评估

作者：韩慧西安电子科技大学

学位级别：硕士

飞速发展的互联网带给人们便利的同时也带来了许多安全威胁和挑战。网络流量测量通过收集和分析网络流量的统计特征可以准确地分析网络的安全性。主机基数估计是网络流量测量中的一项重要任务,可以用来识别超级主机。超级主机指主机基... 详细信息

飞速发展的互联网带给人们便利的同时也带来了许多安全威胁和挑战。网络流量测量通过收集和分析网络流量的统计特征可以准确地分析网络的安全性。主机基数估计是网络流量测量中的一项重要任务,可以用来识别超级主机。超级主机指主机基数表现异常的主机,例如,超级传播者(超级接收者)是具有较高目的基数(源基数)的主机,超级变化者在相邻测量周期的基数变化较大。因此,准确的主机基数估计可以对网络进行可信测量,帮助构建可信网络。如果主机基数出现异常,则说明该主机的可信任度较低。Sketch是一种基于哈希的概率数据结构,可以在消耗较少内存资源的情况下进行准确的主机基数估计,已被广泛用于超级主机识别。但不断扩大的网络规模和日益提升的链路速率导致基于Sketch的超级主机识别存在效率和精度的问题,例如真实网络环境中分布不均衡的主机基数导致Sketch内存使用的严重浪费,存储海量网络流量数据使超级主机溯源不高效。为了解决以上问题,本文提出一种新型内存高效的可逆Sketch,名为Extended Sketch+。该Sketch使用可扩展的计数器记录主机基数,确保监控低基数主机时使用较小计数器,在监控高基数主机时使用可以扩展基数估计上限的动态计数器。因此,Extended Sketch+可以同时提供较高的内存使用和准确的主机基数估计。此外,Extended Sketch+支持合并操作,允许分布式地部署测量节点以实现大规模网络范围内的超级主机识别。基于Extended Sketch+,本文提出了准确快速的超级主机识别方法,并且Extended Sketch+可以快速溯源超级主机。基于上述工作,本文还提出了一个基于Extended Sketch+的网络主机信任评估方法,实现对主机可信任度的准确评估。本文在真实的网络流量数据集上对提出的方案进行了测试以及性能的评估。实验结果表明,Extended Sketch+在准确率和效率方面优于现有相关工作,基于Extended Sketch+的网络主机信任评估可以提供准确的主机信任评估。

关键词：网络流量测量 Sketch 内存高效超级主机识别网络主机信任评估

Context-Aware Animation Data Description and Interaction Method Based on Sketch

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Journal of Beijing Institute of Technology 2019年第1期28卷 8-16页

作者： Fang Liu Zhaoxu Sun Cuixia Ma Hongan Wang Institute of Software Chinese Academy of Sciences

In this paper,an interactive method is proposed to describe computer animation data and accelerate the process of animation generation.First,a semantic model and a resource description framework(RDF)are utilized to analyze and describe the relationships between animation data.Second,a novel context model which is able to keep the context-awareness was proposed to facilitate data organization and storage.In our context model,all the main animation elements in a scene are operated as a whole.Then Sketch is utilized as the main interactive method to describe the relationships between animation data,edit the context model and make some other user operations.Finally,a context-aware computer animation data description system based on Sketch is generated and it also works well in animation generation process.

关键词： animation data description Sketch interactive animation context-aware

维普期刊数据库

基于Sketch Token的异源雷达影像匹配适应性分析

在线全文

学校读者我要写书评

暂无评论

同济大学学报（自然科学版） 2015年第12期43卷 1888-1894页

作者：叶勤陈宏敏张绍明同济大学测绘与地理信息学院上海200092

将异源影像间的共性信息提取与描述作为研究重点,提出了一种基于Sketch Token中层特征的异源影像适配性评估方法.该算法利用监督学习策略获取异源雷达影像之间共性特征的先验知识,据此训练Sketch Token特征分类器,并将其作为影像间共性... 详细信息

将异源影像间的共性信息提取与描述作为研究重点,提出了一种基于Sketch Token中层特征的异源影像适配性评估方法.该算法利用监督学习策略获取异源雷达影像之间共性特征的先验知识,据此训练Sketch Token特征分类器,并将其作为影像间共性特征的描述子对基准图进行特征提取.利用提取结果的各项统计量训练支持向量机分类器,并以此评估异源影像对中基准图的适配性.利用星载SAR(synthetic aperture radar)影像作为基准图、机载实孔径雷达影像作为实时图进行适配性评估试验,试验结果表明了该算法的有效性.

关键词：异源影像 Sketch Token 中层特征共性信息适配性分析

维普期刊数据库

Retrieving Aerial Scene Images with Learned Deep Image-SketchFeatures

在线全文

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2017年第4期32卷 726-737页

作者： Tian-Bi Jiang Gui-Song Xia Qi-Kai Lu Wei-Ming Shen State Key Laboratory of Information Engineering in Surveying Mapping and Remote Sensing Wuhan University Wuhan 430079 China School of Electronic Information Wuhan University Wuhan 430072 China

This paper investigates the problem of retrieving aerial scene images by using semantic Sketches, since the state-of-the-art retrieval systems turn out to be invalid when there is no exemplar query aerial image available. However, due to the complex surface structures and huge variations of resolutions of aerial images, it is very challenging to retrieve aerial images with Sketches and few studies have been devoted to this task. In this article, for the first time to our knowledge, we propose a framework to bridge the gap between Sketches and aerial images. First, an aerial Sketch-image database is collected, and the images and Sketches it contains are augmented to various levels of details. We then train a multi-scale deep model by the new dataset. The fully-connected layers of the network in each scale are finally connected and used as cross-domain features, and the Euclidean distance is used to measure the cross-domain similarity between aerial images and Sketches. Experiments on several commonly used aerial image datasets demonstrate the superiority of the proposed method compared with the traditional approaches.

关键词： Sketch aerial image retrieval multi scale deep cross-domain model