概率后缀树在入侵检测中的应用研究

系统调用序列能够反映系统进程的行为特征。而系统调用序列中每个调用的出现都与它之前出现的若干个调用相关。因此可以利用概率后缀树（PST）对系统调用序列建模,反映系统调用基于上下文的概率特性。提出了系统调用序列异常度的定义。在进行序列的异常检测时,先利用正常系统调用序列训练PST模型,然后通过该模型,利用计算未知系统调用序列的异常度,根据给定的阈值判断该序列是否异常。实验表明这一度量对于正常进程与异常进程有着良好的区分效果。     

后缀树聚类算法在元搜索引擎中的应用

元搜索引擎结果覆盖面广,易于维护,实现简单,能够提供比较全面的结果给用户。后缀树聚类算法(STC)充分考虑了文本集合的语言学特征,并引入了短语特性,从而产生了较好的聚类效果。本文将后缀树聚类算法应用到元搜索引擎中,从而增强了结果的可浏览性,提高了搜索的精度。实验结果表明,STC算法在查准率和时间性能方面都高于传统的聚类算法。     

维吾尔文后缀树构造算法的设计与实现

为用后缀树聚类算法对维吾尔文网页进行聚类,通过分析可扩展后缀树和维吾尔文的特点设计了维吾尔文后缀树构造算法。实验结果证明该方法能够在线性的时间范围内构造维吾尔文后缀树,并用它来对维吾尔文网页进行聚类。     

后缀树的并行构造算法

后缀树是一种非常重要的数据结构,它在与字符串处理相关的各种领域里有着非常广泛的应用。构造后缀树是应用后缀树解决问题的前提和关键。虽然很多现有的后缀树构造算法都是线性时间和空间的,但是,当被索引的字符串的长度很长时,构造其后缀树所消耗的时间和空间仍将非常巨大,这极大地限制了后缀树的实际应用。而并行技术是解决这一问题的很好途径,因此人们提出了后缀树的并行构造算法。本文对后缀树的三种并行构造算法进行了综述,通过系统的比较和分析,总结出当前存在的问题,并指明了下一步的研究方向。     

后缀树的设计与构造

后缀树是处理字符串的一个优秀算法。利用图像化设计可使后缀树更加清晰。按照递推的思路,建立前i个字符对应的后缀树,通过插入第i+1个字符的方式,建立前i+1个字符对应的后缀树。由于字符串的任意子串都可以表示为某个后缀的前缀,因此可以设定当前节点为根节点。父节点取子节点中贡献最大的节点,同时,记录其对应的字符串。     

后缀树构造算法理论分析

后缀树的结构简单,但可以在线性的时间里解决许多复杂的问题,被大量的使用在字符串及树的模式匹配中.     

基于后缀树的带有通配符的模式匹配研究

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究 的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其 中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束。采用非线性数据结构—后缀树,设计了求 解模式所有解的完备算法PAS"I'。预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合 动态规划的思想,逐个匹配模式中字符,最终得到完备解。在基因序列上的实验表明,PAST比其他算法具有更好的 时间性能。     

基于广义后缀树的二分网络社区挖掘算法

近年来,二分网络的社区挖掘问题得到了极大的关注。提出了一种基于广义后缀树的二分网络社区挖掘算法。首先从二分网络的邻接矩阵中提取网络中每个节点的链接节点序列,然后构建广义后缀树。广义后缀树的每个节点表示二分网络的一个完全二分团,由此获取并调整完全二分团。通过引入二分团的紧密度得到初始的社区划分,最后再对孤立点进行处理以得到最终的社区划分。所提算法不仅能发现重叠社区,而且能得到一对多关系的社区。在人工数据集和真实数据集上的实验表明,所提算法能准确地识别二分网络中的社区个数,获得很好的划分效果。     

SuffIndex--一种基于后缀树的XML索引结构

针对形如∥element1／dement2／…／elementm0的查询,提出了一种基于后缀树(suffix tree)的XML索引结构SuffIndex．SuffIndex的构造通过只对OEM数据树遍历一次以及在SurfIndex中引入后缀链(SuffIink)的方法,从而达到较低的构造代价．SuffIndex中所有结点利用Hash表保存到其所有子结点的指针,最终使查询∥element1/element2／…／elementm的处理代价为O(m)．     

基于通用后缀树模型的垃圾邮件过滤方法

采用通用后缀树模型(GSTM)，利用邮件内容的上下文信息，进行每个文本位置的不定长多元统计，从而获得被测邮件与不同训练集的相似程度，确定邮件所属的类别。理论分析和实验表明，在相同语料上，该方法的精确度和召回率均达到或超过了基于向量空间模型的邮件过滤方法；对于长度为N的邮件，过滤时间为O(N)；长度为N的新邮件加入训练集，训练时间为O(N)，满足了训练集的动态增长；该方法不需进行分词处理，完全独立于语种，适用于多语种邮件同时存在的情况。     

Distributed Suffix Tree Overlay for Peer-to-Peer Search

Establishing an appropriate semantic overlay on peer-to-peer (P2P) networks to obtain both semantic ability and scalability is a challenge. Current DHT-based P2P networks are limited in their ability to support a semantic search. This paper proposes the distributed suffix tree (DST) overlay as the intermediate layer between the DHT overlay and the semantic overlay to support the search of a keyword sequence. Its time cost is sublinear with the length of the keyword sequence. Analysis and experiments show that the DST-based search is fast, load-balanced, and useful in realizing an accurate content search on P2P networks.     

一个P2P搜索引擎的架构和实现

P2P搜索技术是P2P研究中的一个重要的领域。本文介绍了一个基于P2P结构化覆盖网络的分布式搜索引擎的架构和实现。该搜索引擎采用了三层架构,良好的层次架构减少了搜索引擎核心算法与P2P覆盖网络协议和具体应用间的依赖,使得搜索引擎可以移植到不同的P2P结构化覆盖网络之上。由于P2P搜索过程中会消耗大量的网络带宽,所以该搜索引擎使用了一些优化算法,它们不仅减少搜索过程带来的带宽消耗,而且保证了系统的可伸缩性。     

用于对等全文检索的安全覆盖网

对等全文检索充分利用对等节点的资源实现检索,其关键是控制检索请求传播的节点范围。结合全文检索的安全要求提出安全覆盖网(Secure Overlay Network, SON),按安全级支配关系将对等节点组成网络。SON中节点发起的检索请求只能向下传递到安全级受其支配的节点,涉及节点是整个覆盖网中节点的子集,检索结果也是符合安全要求的。给出了SON的定义并分析了其性质,介绍了基于SON的对等全文检索原理和算法并分析了其安全性。实验表明,基于安全覆盖网的对等全文检索具有良好的检索效率。     

一种新的P2P节点路由优化算法RGAAC

大部分P2P覆盖网络系统中采用随机选择邻居节点的方法路由,这种方法路由跳数高,效率较低.提出一种基于平均连通聚类的P2P节点路由算法RGAAC.算法根据节点通信历史信息作为节点之间距离的量度,将原始节点的拓扑结构重新划分为k个逻辑域,每个域中产生一个中心节点用来保存该域内的路由信息,使得网络节点在决定下一步跳转时,优先选择距离较近的节点.实验表明RGAAC可以减少节点路由跳数,提高路由效率.     

面向系统吞吐率最大化的P2P自适应覆盖网络

P2P系统的本质任务在于提高资源利用率和系统吞吐量,满足更多用户的数据请求。在无结构P2P中,通常分配高权重节点以较多连接,使之收到并命中更多查询,以提高搜索成功率。但高搜索成功率本身却未必能够提高系统吞吐量,因为受带宽因素影响,高权重节点的负载较重,造成服务可用性降低。提出了一种覆盖网络优化方案,即根据带宽负载和存储权重自适应性调整节点连接度,优化覆盖网络结构,提高系统吞吐量。模拟实验数据表明,基于带宽和搜索成功率的覆盖网络优化方案可以以很小代价提高系统吞吐量,当文件体积较小时提高比例可高达22%。     

基于DHT的P2P搜索定位技术研究*

在P2P系统中,如何高效准确地对资源进行定位是衡量其性能的一个关键。通过对目前基于DHT的几个典型P2P系统搜索定位算法的介绍,分析了基于DHT搜索定位技术的优点和存在的问题,并对P2P发展进行了展望。     

一种有效的无结构对等网络搜索算法

点对点（Peer-to-Peer）网络已发展成为当今最为流行的资源共享系统之一。其中的资源搜索是一个关键性问题。传统的方法借助本地所掌握的网络信息,利用某种搜索算法来定位资源。但是这些方法只遵循很少的搜索规则,因此不能取得理想的搜索性能。文章提出一种更为高效的预搜索忽略优化算法来搜索P2P网络。它分为两个阶段：第一个阶段进行预搜索并获取网络拓扑结构和资源的信息,第二个阶段通过已获取的信息对网络结构进行逻辑上的优化,进而更高效地搜索P2P网络。     

SSW: A Small-World-Based Overlay for Peer-to-Peer Search

Peer-to-peer (P2P) systems have become a popular platform for sharing and exchanging voluminous information among thousands or even millions of users. The massive amount of information shared in such systems mandates efficient semantic-based search instead of key-based search. The majority of existing proposals can only support simple key-based search rather than semantic-based search. This paper presents the design of an overlay network, namely, semantic small world (SSW), that facilitates efficient semantic-based search in P2P systems. SSW achieves the efficiency based on four ideas: 1) semantic clustering, where peers with similar semantics organize into peer clusters, 2) dimension reduction, where to address the high maintenance overhead associated with capturing high-dimensional data semantics in the overlay, peer clusters are adaptively mapped to a one-dimensional naming space, 3) small world network, where peer clusters form into a one-dimensional small world network, which is search efficient with low maintenance overhead, and 4) efficient search algorithms, where peers perform efficient semantic-based search, including approximate point query and range query in the proposed overlay. Extensive experiments using both synthetic data and real data demonstrate that SSW is superior to the state of the art on various aspects, including scalability, maintenance overhead, adaptivity to distribution of data and locality of interest, resilience to peer failures, load balancing, and efficiency in support of various types of queries on data objects with high dimensions.     

改进的基于概率的非结构化对等网搜索算法

资源发现是P2P应用所面临的最核心问题之一.无结构P2P主要采用了查询消息泛洪和信息索引机制,会造成严重的网络带宽负担以及巨大的索引维护开销.提出了一种无结构P2P环境下一种改进的概率自适应的、动态缓存和索引算法EAPS,EAPS算法依据用户结点和用户结点的邻居节点命中查询的历史信息赋予结点相应权值作为查询消息路由的依据,引导查询快速接近目标资源,同时能够解决由搭便车结点所带来的网络带宽消耗.自适应缓存机制和索引机制的引入使搜索性能大为加强.最后的实验表明,附带自适应缓存和索引的EAPS,以其高搜索成功率、很短的时间响应,能够显著地提高资源发现性能.     

一个基于元数据的对等信息系统模型

现有的基于DHT的P2P系统使用唯一标识来定位资源,实现了从资源标识到资源位置的一种映射。在这类系统中,用户必须准确知道资源的标识才能访问该资源,它们本质上并不具有搜索能力;同时由于网络中资源的多样性和资源本身的复杂性,仅仅使用一个标识很难准确完整地描述一个资源,经常需要多个属性才可以。因此,文章在DHT的基础上,设计了一个基于元数据的对等信息系统MPIS,它能够根据资源的多个属性来定位所需资源,并且具有很强的搜索能力。