针对大规模动态图流三角形计数的边哈希分布式抽样算法

三角形计数是大图分析的一个经典问题,近年的研究工作主要集中在针对静态流式图的三角形数量估计上,相关流式图抽样算法只能处理边的插入操作,无法处理边的删除操作;而现有的动态流式图抽样算法估计准确性又偏低.针对上述问题,提出了基于边哈希分配的分布式抽样(edge hashing assignmentbased distributed sampling,EHADS)算法,它是一个用于估计动态流式图中三角形数量的分布式流算法,可以快速准确地估计动态流式图中的全局三角形数量以及每个顶点的局部三角形数量.EHADS算法只对输入的图流进行1次处理,并在多台机器上对边进行抽样.与先进的单机流算法相比,EHADS算法具有2点优势:1)在相同样本容量的情况下,EHADS算法以更短的运行时间获得了更小的估计误差,估计全局三角形数量的误差平均降低了31.79%,估计局部三角形数量的误差平均降低了23.35%;2)EHADS算法能够提供流式图中三角形数量的无偏估计,并且严格的数学证明显示该无偏估计具有更小的方差.

基于双特征的短波红外星图识别算法

在短波红外波段进行昼夜测星有望实现近地空间全天时自动导航,其中,星图识别算法是实现全天时导航的关键技术之一。传统的三角形算法在导航星数增多的情况下,由于其匹配特征维度低,在识别时容易出现冗余匹配、误匹配的情况。针对这一问题,提出了一种基于双特征的短波红外星图识别算法,该算法选取三角形的面积与外切圆半径双高维特征作为匹配特征,通过构建面积特征的K矢量索引,应用K矢量查找法降低匹配识别的计算复杂度。此外,还提出一种优化的观测三角形的选择策略,减少了匹配过程中的计算量,提高算法的识别速度。实验表明,星点位置噪声低于2像素时,算法的平均识别率优于95%;伪星数未超过50%时,平均识别率可达87.6%;并通过实际观星试验验证了所提算法的可行性,与改进的三角形算法相比,该算法在识别速度、识别率以及抗噪声能力等方面都有明显优势。

基于离散监督哈希算法的非结构化网络数据库在线检索方法

受非结构化网络数据关联性弱、数据收敛特性差的影响,对相关数据库进行检索时,检索精度难以得到保障,为此,提出基于离散监督哈希算法的非结构化网络数据库在线检索方法研究。首先,基于离散监督哈希算法将非结构化网络数据样本的显式语义标签利用相应的二进制码进行表示,并借助拉格朗日乘子对其进行离散化处理,使得哈希函数对于学习非结构化网络数据显式语义关联快速收敛。然后,按照相同的方式对所有数据及查询请求进行编码。最后,将与查询请求哈希编码匹配程度最高的数据作为优先检索输出结果。在测试结果中,设计检索方法在图像查询文本指令,以及文本查询图像指令下的检索平均精度均值始终稳定在较高水平,且检索时间最高仅为7 s,具有实用性。

Hash算法在数据库安全中的应用

介绍了Hash算法在数据库加密系统中的应用,包括在用户身份验证中的应用,在数据库完整性认证中的应用,以及在密文检索中的应用。

三角形星图识别算法的改进

三角形识别算法是采用星敏感器为导航部件所广泛运用的星图识别算法。但由于三角形特征维数较低,容易造成冗余匹配和错误识别。为了提高三角形识别算法的识别成功率,对三角形识别算法的识别过程做了改进。先将满足三边判决门限的导航星对记录到匹配数组,然后对导航星出现的次数进行计数;利用三角形三边之间两两相交的相关性,将导航星出现次数<2的星对作为整体剔除,最后在余下的导航星对中寻找与观测三角形同构的三角形。识别过程中,以星对角距和相对星等差为识别特征,并对识别特征构造了散列函数,从而减少了识别过程中特征量比较的次数,提高了识别速度,增加了识别成功率。同时,也减小了内部导航星库的存储容量。

快速全天自主星图识别

为了克服三角形识别算法中三角形因特征维数较低带来的冗余匹配问题,对该算法进行了改进。在利用标记法进行三角形识别的基础上,引入三角形以外的第四颗星,并以其为顶点,与三角形构成假想的四面体,顶点与底面三角形3个点的角距既可作为识别特征量,也可用于检验识别的结果是否正确。识别算法以星对角距作为主要识别特征,增加星等差为辅助识别特征,减少了对冗余数据的存储,使导航特征库的容量仅有0.4 Mb。在识别过程中,利用散列查找法对识别特征构造散列函数,减少了对导航特征库遍历比较的次数和时间开销,加快了识别过程,平均识别时间为0.43 ms。仿真实验结果表明,该识别算法在较大位置和星等误差时具有较短的识别时间和较高的识别率。

基于多视场星敏感器的三角形星图识别方法

为解决现有基于单星敏感器的星图识别中由于成像视角小,星图恒星数量不足而造成的星图识别率偏低的问题,提高星图识别的准确度和精确度,提出了一种基于多视场星敏感器的改进三角形星图识别方法;该方法通过将相同位置相同时间不同姿态角获得的多幅星图基于星图自身径向特征拼接成一幅多视角、不失真的星图,利用拼接后的星图进行星图识别,同时采用分块方式存储星对角距以及利用哈希查找提高星图识别效率;实验随机识别500幅星图,仿真结果表明,与传统的单视场星图匹配算法相比,该方法具有更高的星图识别率和匹配精度,当星图恒星数量达到30以上时,平均识别率能基本达到97%,且识别速度提高了11倍左右。

一种改进的快速星图识别算法

为解决传统算法在星图噪声加大、星等接近的情况下识别率和识别速度降低的问题,提出一种改进的星图识别算法;从三方面进行改进:首先采用重叠正交网格方法对星表进行均匀化,以减小导航星库容量;其次在匹配时采用哈希查找的搜索方式,以提高匹配速度;最后在识别匹配中加入星等判断环节,当星等噪声大、相对星等小时不采用星等信息,只采用角距进行匹配,同时引入了校验环节以降低冗余和误匹配;仿真实验表明,改进的算法对位置和星等误差比传统的星图识别算法具有更好的鲁棒性,且实时性得到了很大的提高。

一种P2P网络中的隐蔽搜索模型

随着peer-to-peer(P2P)网络应用的不断发展,网络中的隐私保护问题引起了广泛的关注.当前研究主要集中在匿名通信机制的实现,而这些匿名技术通常需要复杂的系统结构,增加了开发维护代价以及网络管理的难度,同时也增大了传输延迟.针对P2P网络,尤其是无搜索服务器的P2P网络中用户搜索内容隐私保护的问题,提出了基于单向函数和Soundex算法的隐蔽搜索模型.该模型能够保护用户的搜索内容、抵抗窃听、重放、身份冒充等攻击,并且支持精确搜索和模糊搜索.分析表明隐蔽搜索模型具有较高的安全性和搜索有效性.

DHSWM:一种改进的WM多模式匹配算法

针对WM算法的查找效率随着模式集规模的增大而降低的问题,提出一种改进算法。在预处理阶段,改变原有Hash表中的链表结构,采用双哈希法将模式串存放在Hash1表中指定的区间,Hash表中存放该存储区间的起始位置与区间长度;Prefix表用于判断模式集中是否存在与当前匹配窗口中文本前缀相同的模式;当Shift表中出现移动值为0时,根据后缀出现在模式串其他位置的信息计算匹配窗口可滑动的最大距离并存于Shift1表中。在查找阶段,采用双哈希法在Hash1表的某一区间中查找模式串,避免在大规模模式集情况下查找过长的模式链表,扩大匹配操作后匹配窗口滑动的距离,减少冗余的匹配操作,缩短查找时间。研究结果表明:在模式集规模较大时,改进后的算法显著地提高了匹配速度;当模式串数目超过5 000条时,改进算法的查找时间要比WM算法缩短40%～47%。

井下人员定位系统读卡器存储算法分析与测试

从查找时间与存储容量2个方面分析了适用于井下人员定位系统读卡器的3种存储算法,即链式存储算法、哈希表存储算法和哈希二叉树存储算法,给出了该3种不同存储算法的使用效率与应用场合。测试结果表明,链式存储算法查找时间呈线性增长,哈希表存储算法明显优越于链式存储算法,如果测试数据增多,其优越性会更明显;当数据量较大时,哈希搜索二叉树存储算法又明显优于哈希表存储算法,当人数达到行业所要求的8 000人以上时,选择哈希搜索二叉树存储算法更为合理。

基于灰度分类的图像搜索引擎

图像搜索是下一代搜索引擎迫切需要解决的课题,在对图像搜索引擎的主要功能和关键技术进行了分析和讨论的基础上,详细剖析了图像搜索引擎设计中任务分析、解决方案、感受哈希算法、实现等关键过程,并实现了一个基于灰度值分类的图像搜索引擎。实际试验表明,本图像搜索引擎的搜索速度较快、性能稳定,具有较好的搜索效果。

面向802.11ac的安全加速引擎Gbps VLSI架构设计与实现

针对IEEE 802.11i协议中多种安全协议实现进行研究,结合以IEEE 802.11ac协议为代表的下一代无线局域网(WLAN)系统对高吞吐率的需求,提出了一种支持WEP/TKIP/CCMP协议的多模、高速安全加速引擎的大规模集成电路(VLSI)架构。提出了基于哈希算法的密钥信息查找算法,缩小了查找时钟延迟。基于复合域的运算方式实现高级加密标准(AES)算法,提出双AES运算核的并行架构实现计数器与密码分组链接(CCM)模式,提升运算吞吐率的同时也降低了引擎的响应延迟。经过FPGA实现和ASIC流片验证表明,该安全加速引擎具备可重构性,处理延迟仅为33个时钟周期,在322 MHz工作频率下运算吞吐率可达3.747 Gbit/s。

熵选择多重二进制编码

为了解决查询高维浮点型数据的近邻点需要计算代价昂贵的欧式距离,内存占用率较高的问题,将高维浮点型数据通过哈希映射函数映射为低维二进制编码,并保证同一样本点在两种空间内的归一化距离满足相似性。从而在实现近邻检索任务时,可使用代价较低的汉明距离替换欧式距离,达到降低检索复杂度的目的。为保证由哈希函数生成的二进制编码具有较优的近邻检索性能,本文首先基于查找机制得到数据集适应空间分布特性的二进制标签,然后利用SVM算法得到二进制标签的分类平面,并选择其中具有最大熵值的平面函数作为最终的哈希映射函数。为了进一步提高近邻检索性能,在训练阶段,初始化多种不同的编码中心点用以生成多重二进制标签,并得到与此相应的多重哈希函数和多重二进制编码。在检索过程中,建立了基于多重二进制编码的近邻检索体系,返回具有较小平均汉明距离的样本点作为最终检索结果。实验结果表明:与其他现存优秀算法相比,本文算法可以快速、有效地将浮点型数据转化为二进制编码,而且基于这些二进制编码的近邻检索性能较优。

满足度量性质的归一化树编辑距离

利用树大小和树编辑距离的简单函数提出了一种归一化树编辑距离,在权重函数具有度量性质且所有插入和删除操作的权重都相等时,不仅能完全满足三角不等式,而且是一种取值在[0,1]的度量.这种距离可以由树编辑距离直接计算得到,其计算时间复杂度与树编辑距离相同.通过手写数字识别实验说明,AESA算法利用该距离获得的识别率为91.6%,比其他2种归一化树编辑距离分别高0.2%和0.8%.

认知无线网络中集中式信道搜索策略的研究

认知无线网络中,认知用户利用授权用户暂时不用的信道传输数据,认知用户对空闲信道的搜索策略成为了认知无线网络效率提高的关键问题之一。将哈希算法应用于认知无线网络的信道搜索过程中,给出了一种面向认知用户的集中式信道搜索策略HSS(Hash-SU-Search)。建立了带有两类顾客的离散时间排队模型,给出了系统的信道利用率及平均搜索次数等性能指标的表达式。通过数值实验,将HSS信道搜索策略与传统的顺序信道搜索策略进行了比较,验证了HSS的有效性。

哈希编码和Kalman滤波的目标跟踪算法

针对现有的目标跟踪算法过于复杂、计算量大和遮挡无法跟踪等缺点,提出了基于哈希编码和Kalman滤波的目标跟踪改进算法.采用哈希算法对图像感兴趣的区域进行编码,将二维图像变为一维数字摘要,大大地减少了匹配运算量;采用Kalman滤波算法进行目标搜索,并预测目标在下一帧图像中的位置,再以预测位置为起点进行搜索,从而缩小了搜索范围,加快了跟踪速度.通过对多组视频中的目标进行跟踪实验,结果说明所提出的改进算法在背景复杂、目标快速运动、完全遮挡的环境下具有较强的抗干扰能力,跟踪效果较好,跟踪速率高达12帧/s.

关于对图像哈希算法的研究与应用

传统的基于文本的检索方式无法精确地搜索图片,因此基于图像内容的检索技术应运而生.它利用图像哈希算法提取图像特征,通过量化压缩等方法产生一个标明图像指纹的哈希序列,对比哈希序列即可判定两张图像的相似度.主要从图像哈希算法的定义、原理、特点、应用等方面进行研究,并着重介绍和对比a Hash算法及p Hash算法.

MD4自动搜索差分路径算法

简单介绍了MD4差分分析所用到的基本理论知识,并对自动搜索差分路径算法做了详细说明。深入研究自动搜索差分路径算法,分析出各部分之间的复杂关系,并对原算法进行了改进。最后证明改进算法产生的新差分路径比原算法产生的差分路径更有效。

高维特征下快速近邻法的定位点选择及在手写汉字识别中的应用

在采用最近邻法进行模式识别时,减小搜索的计算量是一个重要的问题,对于在线识别尤为重要,解决的途径之一是采用快速搜索近邻法。快速近邻法在将样本集分级后,若采用样本均值作为子集圆心,则求取所得的样本子集半径将大于其实际半径。该文介绍了一种高维特征情况下的样本子集圆心的求取方法,根据该方法求得的样本子集圆心与样本均值存在一定的距离,且求得的样本子集半径较小。将这两个圆心以及子集中特征累加值最大和最小的样本作为定位点,应用于基于三角不等式的搜索算法的样本排除规则,大大减少了搜索的计算量。在手写汉字识别实验中,基于该方法的快速近邻法识别速度更快。