CN109271390B - 一种基于神经网络的索引数据结构及其数据检索方法 - Google Patents

Abstract

本发明公开了一种基于神经网络的索引数据结构，包括数据映射单元和动态索引单元；数据映射单元是基于神经网络模型的数据映射单元，采集命名数据网络中的名称数据作为样本，计算其累积分布函数值作为标签，训练得到神经网络模型，用于把名称数据映射到改进型位图bitmap数据结构中的相应位置；动态索引单元是基于改进型位图bitmap数据结构的动态索引单元，将传统位图平均分成若干桶，并将桶内每个槽的大小扩展，得到可动态标号的改进型位图bitmap数据结构，用于存储名称数据所对应的地址偏移量。本发明针对命名数据网转发平面特点，可以在保证检索速度和误判概率的条件下，提升存储效率，实现快速数据插入及检索操作。

Description

一种基于神经网络的索引数据结构及其数据检索方法

技术领域

本发明属于高性能路由器索引数据结构设计领域，特别针对命名数据网(NamedData Networking)转发平面中索引内容的高效存储和快速检索问题。

背景技术

超高清视频、人工智能、云计算等创新应用、技术和计算模式的不断涌现，加速了互联网由“通信信道”向“数据处理平台”的角色转变。现有基于设备地址的IP互联网体系结构在信息共享、移动性、安全性、可扩展性等方面存在的弊端已成为阻碍互联网发展的重大难题。因此，一种新型未来互联网架构，命名数据网，于2010年被提出，得到了国内外学术界的广泛关注。

命名数据网以数据名称代替IP地址，使用完全面向数据内容的通信模式。其优势在于通过在路由节点中部署缓冲存储器，实现真正意义上的数据内容共享，极大地降低网络负载，有效提高网络数据传输速率。正因此，其被认为是未来互联网架构领域最有前景的发展方向之一。

然而，命名数据网也面临着一系列亟待解决的问题与挑战，特别是转发平面中索引内容的高效存储和快速检索问题。其中，索引数据结构是提高转发平面性能的关键，但目前主要研究成果都各有优缺点。例如，基于字典树的数据结构查找速度较慢；基于布隆滤波器的数据结构无法直接索引数据；而基于哈希表的数据结构需要极大的存储空间。因此，当前的研究成果都无法同时满足命名数据网转发平面对检索速度和存储空间的需求，急需提出新的研究思路，设计综合性能优秀的索引数据结构及其数据检索算法以解决这一难题。

发明内容

针对上述问题，本发明提供了一种基于神经网络的索引数据结构及其数据检索方法。本发明针对命名数据网转发平面特点，可以在保证检索速度和误判概率的条件下，提升存储效率，实现快速数据插入及检索操作。

为了解决上述的技术问题，本发明提出一种基于神经网络的索引数据结构，包括数据映射单元和动态索引单元；所述数据映射单元是基于神经网络模型的数据映射单元，采集命名数据网络中的名称数据作为样本，计算其累积分布函数值作为标签，根据样本和标签训练反向传播神经网络，得到神经网络模型，用于把要检索的名称数据映射到改进型位图bitmap数据结构中的相应位置；所述动态索引单元是基于改进型位图bitmap数据结构的动态索引单元，将传统位图bitmap数据结构平均分成若干桶，并将桶内每个槽的大小扩展，得到可动态标号的改进型位图bitmap数据结构，记为D-bitmap，用于存储要检索的名称数据所对应的地址偏移量。

本发明中同时提出了一种上述基于神经网络的索引数据结构的数据检索方法，主要包括在索引数据结构中插入数据，以及对插入数据之后的索引数据结构进行数据检索；具体步骤如下：

步骤一、在所述索引数据结构中插入名称数据，每插入一个名称数据，包括以下步骤：

步骤1-1：输入名称数据：将待插入的名称数据输入到上述的索引数据结构中；

步骤1-2：数据映射单元的神经网络计算：将该名称数据定长处理后输入上述的神经网络模型运算，得到一个范围在0、1之间的实数值；

步骤1-3：数据映射单元的位置映射计算：将神经网络计算结果乘D-bitmap的槽总数，得出该名称数据映射到D-bitmap上的位置，即D-bitmap的槽序号；

步骤1-4：动态索引单元的桶序号计算：用槽序号除以每个桶的槽数量，并向下取整，得出该位置所在的桶序号；

步骤1-5：动态索引单元的最大标号查找：由步骤1-4得到的桶序号，遍历该桶内所有槽，查找现有的最大标号；

步骤1-6：动态索引单元的槽内标号记录：判断步骤1-5查找到的现有最大标号是否达到最大值，如果还未标记到最大值，则该位置槽内记录现有最大标号加一的标号，否则，从删除队列中取最早删除的标号作为该位置槽内的标号；

步骤1-7：为该名称数据申请存储单元：根据动态索引单元中的桶序号对应的基地址与槽内标号代表的地址偏移量，在数据存储空间中为该名称数据申请存储单元；

步骤1-8：名称数据插入操作结束；

步骤二、在索引数据结构中对一个名称数据进行检索，包括以下步骤：

步骤2-1：输入名称数据：将待插入的名称数据输入到上述的索引数据结构中；

步骤2-2：数据映射单元的神经网络计算：将该名称数据定长处理后输入上述的神经网络模型运算，得到一个范围在0、1之间的实数值；

步骤2-3：数据映射单元的位置映射计算：将神经网络计算结果乘D-bitmap的槽总数，得出该名称数据映射到D-bitmap上的位置，即D-bitmap的槽序号；

步骤2-4：动态索引单元的数据存在性判断：判断该位置处的标号是否为0，如果标号不为0，则该名称数据存在于该索引数据结构中，并继续执行步骤2-5，完成检索；否则，该名称数据不存在于该索引数据结构中，即表明不存在检索结果，执行步骤2-7；

步骤2-5：动态索引单元的桶序号计算：用槽序号除以每个桶的槽数量，并向下取整，得出该位置所在的桶序号；

步骤2-6：输出检索结果：输出该位置所在的桶序号和槽内标号，即数据存储单元基地址和该名称数据在数据存储空间中相对于基地址的地址偏移量；

步骤2-7：名称数据检索操作结束。

与现有技术相比，本发明的有益效果是：

将本发明的基于神经网络的索引数据结构及其数据检索方法在一台配置为IntelXeon E5-1650v2 3.50GHz、DDR3 24GB SDRAM的计算机上进行部署实现。其中，训练用的名称数据在实际环境中可通过命名数据网络的转发平面采集，而实验室环境下，我们利用常见英文单词和顶级域名构造一亿条格式类似的名称数据，经过训练得到可实现均匀映射的神经网络模型。性能测试上，考虑到命名数据网络转发平面处理的数据量在百万级别，我们取相同分布规律的一百万条名称数据测试该索引数据结构及其数据检索方法的性能。实验结果表明，本发明的存储消耗远远小于哈希索引的存储消耗，同时检索速度与哈希索引相当，也能够满足当前互联网络误判率低于1％的通信需求。由此表明，本发明中设计的基于神经网络的索引数据结构及其数据检索方法，可以在保证检索速度和误判概率的条件下，提升存储效率，具有良好的性能。

附图说明

图1为本发明基于神经网络的索引数据结构的原理图；

图2为本发明基于神经网络的索引数据结构中数据映射单元运行具体步骤的示意图；

图3为本发明数据检索方法中关于数据插入操作的流程框图；

图4为本发明数据检索方法中关于数据检索操作的流程框图。

具体实施方式

下面结合附图和具体实施例对本发明技术方案作进一步详细描述，所描述的具体实施例仅对本发明进行解释说明，并不用以限制本发明。

如图1所示，本发明提出的一种基于神经网络的索引数据结构，包括数据映射单元和动态索引单元；具体说明如下：

所述数据映射单元是基于神经网络模型的数据映射单元，采集命名数据网络中的名称数据作为样本，计算其累积分布函数值作为标签，根据样本和标签训练反向传播神经网络(Back Propagation Neural Network，BPNN)，得到神经网络模型，用于把要检索的名称数据映射到改进型位图bitmap数据结构中的相应位置。其中，命名数据网络中的名称数据的采集在命名数据网络实际部署中的转发平面实现，通过记录一定时间内转发平面处理的所有名称数据，得到足够数量的样本数据。计算其累积分布函数值作为标签的原因在于，服从任意分布的数据经过累积分布函数变换后值的分布服从0、1之间的均匀分布。因此，将采集的名称数据作为样本，计算其累积分布函数值作为标签，即可实现数据的均匀映射，从而优化存储单元利用效率。

该数据映射单元运行具体步骤如图2所示。在训练阶段，作为样本的名称数据和作为标签的累积分布函数值共同构成训练数据集，利用该训练数据集训练反向传播神经网络BPNN，拟合训练数据集的累积分布函数，得到隐藏层和输出层的权重和偏置等相关参数，形成可实现均匀映射的神经网络模型。训练完成后的实际预测阶段，输入一个名称数据，经过神经网络模型运算得到的值乘映射尺寸，得到该名称数据的映射位置。

所述动态索引单元是基于改进型位图bitmap数据结构的动态索引单元，将传统位图bitmap数据结构平均分成若干桶，并将桶内每个槽的大小扩展，得到可动态标号的改进型位图bitmap数据结构，记为D-bitmap，用于存储要检索的名称数据所对应的地址偏移量。对传统位图bitmap数据结构改进的具体方法为，将尺寸为m个槽的位图bitmap平均划分为n个桶，每个桶含有m/n个槽，对应一个固定基地址的数据存储空间。每个槽的大小由原来的1比特扩展成j比特，用于记录地址偏移量。这样改进后的D-bitmap在数据插入过程中动态标号，每个槽中的标号代表名称数据进入所在桶的顺序，也即名称数据在所在存储空间的地址偏移量。根据桶对应的基地址与槽内标号代表的地址偏移量为名称数据申请存储单元，由此实现数据存储单元的地址动态分配。

针对上述基于神经网络的索引数据结构的数据检索方法，包括在索引数据结构中插入数据，以及对插入数据之后的索引数据结构进行数据检索；具体步骤如下：

步骤一、在所述索引数据结构中插入名称数据，每插入一个名称数据，如图3所示，包括以下步骤：

步骤1-1：输入名称数据：将待插入的名称数据输入到上述的索引数据结构中；

步骤1-2：数据映射单元的神经网络计算：将该名称数据定长处理后输入上述的神经网络模型运算，得到一个范围在0、1之间的实数值；

步骤1-3：数据映射单元的位置映射计算：将神经网络计算结果乘D-bitmap的槽总数，得出该名称数据映射到D-bitmap上的位置，即D-bitmap的槽序号；

步骤1-4：动态索引单元的桶序号计算：用槽序号除以每个桶的槽数量，并向下取整，得出该位置所在的桶序号；

步骤1-5：动态索引单元的最大标号查找：由步骤1-4得到的桶序号，遍历该桶内所有槽，查找现有的最大标号；

步骤1-6：动态索引单元的槽内标号记录：判断步骤1-5查找到的现有最大标号是否达到最大值，如果还未标记到最大值，则该位置槽内记录现有最大标号加一的标号，否则，从删除队列中取最早删除的标号作为该位置槽内的标号；

步骤1-7：为该名称数据申请存储单元：根据动态索引单元中的桶序号对应的基地址与槽内标号代表的地址偏移量，在数据存储空间中为该名称数据申请存储单元；

步骤1-8：名称数据插入操作结束；

本发明中，名称数据插入到索引数据结构的一个实例如图1所示。在该索引数据结构中，数据映射单元即训练完成的神经网络模型，动态索引单元即改进型位图数据结构D-bitmap。槽个数设置为32，每16个槽划分为一个桶，因此该D-bitmap一共被划分为2个桶，对应2个固定基地址的数据存储空间。当前该索引数据结构已插入两个名称数据。当第三个名称数据/ndn/name/3rd插入时，在数据映射单元进行神经网络计算和位置映射计算，得到该名称数据在D-bitmap中的映射位置为第6个槽。进入动态索引单元，计算出该位置的桶序号为1。查找第1个桶中现有的最大标号，查找结果为1，还未达到最大值，因此在第6个槽内标记现有最大标号加一的标号，为2，也即该名称数据在数据存储单元中相对于第1个基地址的地址偏移量。

步骤二、在索引数据结构中对一个名称数据进行检索，如图4所示，包括以下步骤：

步骤2-1：输入名称数据：将待插入的名称数据输入到上述的索引数据结构中；

步骤2-2：数据映射单元的神经网络计算：将该名称数据定长处理后输入上述的神经网络模型运算，得到一个范围在0、1之间的实数值；

步骤2-3：数据映射单元的位置映射计算：将神经网络计算结果乘D-bitmap的槽总数，得出该名称数据映射到D-bitmap上的位置，即D-bitmap的槽序号；

步骤2-4：动态索引单元的数据存在性判断：判断该位置处的标号是否为0，如果标号不为0，则该名称数据存在于该索引数据结构中，并继续执行步骤2-5，完成检索；否则，该名称数据不存在于该索引数据结构中，即表明不存在检索结果，执行步骤2-7；

步骤2-5：动态索引单元的桶序号计算：用槽序号除以每个桶的槽数量，并向下取整，得出该位置所在的桶序号；

步骤2-6：输出检索结果：输出该位置所在的桶序号和槽内标号，即数据存储单元基地址和该名称数据在数据存储空间中相对于基地址的地址偏移量；

步骤2-7：名称数据检索操作结束。

实施例：将本发明的基于神经网络的索引数据结构及其数据检索方法在一台配置为Intel Xeon E5-1650v2 3.50GHz、DDR3 24GB SDRAM的计算机上进行部署实现。其中，训练用的名称数据在实际环境中可通过命名数据网络的转发平面采集，而实验室环境下，我们利用常见英文单词和顶级域名构造一亿条格式类似的名称数据，经过训练得到可实现均匀映射的神经网络模型。性能测试上，考虑到命名数据网络转发平面处理的数据量在百万级别，我们取相同分布规律的一百万条名称数据测试该索引数据结构及其数据检索方法的性能。实验结果表明，本发明的存储消耗远远小于哈希索引的存储消耗，同时检索速度与哈希索引相当，也能够满足当前互联网络误判率低于1％的通信需求。由此表明，本发明中设计的基于神经网络的索引数据结构及其数据检索方法，可以在保证检索速度和误判概率的条件下，提升存储效率，具有良好的性能。

尽管上面结合附图对本发明进行了描述，但是本发明并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离本发明宗旨的情况下，还可以做出很多变形，这些均属于本发明的保护之内。

Claims (1)

1.一种基于神经网络的索引数据结构的数据检索方法，所采用的索引数据结构包括数据映射单元和动态索引单元；所述数据映射单元是基于神经网络模型的数据映射单元，采集命名数据网络中的名称数据作为样本，计算其累积分布函数值作为标签，根据样本和标签训练反向传播神经网络，得到神经网络模型，用于把要检索的名称数据映射到改进型位图bitmap数据结构中的相应位置；所述动态索引单元是基于改进型位图bitmap数据结构的动态索引单元，将传统位图bitmap数据结构平均分成若干桶，并将桶内每个槽的大小扩展，得到可动态标号的改进型位图bitmap数据结构，记为D-bitmap，用于存储要检索的名称数据所对应的地址偏移量；

其特征在于，该数据检索方法包括在索引数据结构中插入数据，以及对插入数据之后的索引数据结构进行数据检索；具体步骤如下：

步骤一、在所述索引数据结构中插入名称数据，每插入一个名称数据，包括以下步骤：

步骤1-1：输入名称数据：将待插入的名称数据输入到上述的索引数据结构中；

步骤1-2：数据映射单元的神经网络计算：将该名称数据定长处理后输入上述的神经网络模型运算，得到一个范围在0、1之间的实数值；

步骤1-3：数据映射单元的位置映射计算：将神经网络计算结果乘D-bitmap的槽总数，得出该名称数据映射到D-bitmap上的位置，即D-bitmap的槽序号；

步骤1-4：动态索引单元的桶序号计算：用槽序号除以每个桶的槽数量，并向下取整，得出该位置所在的桶序号；

步骤1-5：动态索引单元的最大标号查找：由步骤1-4得到的桶序号，遍历该桶内所有槽，查找现有的最大标号；

步骤1-6：动态索引单元的槽内标号记录：判断步骤1-5查找到的现有最大标号是否达到最大值，如果还未标记到最大值，则该位置槽内记录现有最大标号加一的标号，否则，从删除队列中取最早删除的标号作为该位置槽内的标号；

步骤1-7：为该名称数据申请存储单元：根据动态索引单元中的桶序号对应的基地址与槽内标号代表的地址偏移量，在数据存储空间中为该名称数据申请存储单元；

步骤1-8：名称数据插入操作结束；

步骤二、在索引数据结构中对一个名称数据进行检索，包括以下步骤：

步骤2-1：输入名称数据：将待插入的名称数据输入到上述的索引数据结构中；

步骤2-2：数据映射单元的神经网络计算：将该名称数据定长处理后输入上述的神经网络模型运算，得到一个范围在0、1之间的实数值；

步骤2-3：数据映射单元的位置映射计算：将神经网络计算结果乘D-bitmap的槽总数，得出该名称数据映射到D-bitmap上的位置，即D-bitmap的槽序号；

步骤2-4：动态索引单元的数据存在性判断：判断该位置处的标号是否为0，如果标号不为0，则该名称数据存在于该索引数据结构中，并继续执行步骤2-5，完成检索；否则，该名称数据不存在于该索引数据结构中，即表明不存在检索结果，执行步骤2-7；

步骤2-5：动态索引单元的桶序号计算：用槽序号除以每个桶的槽数量，并向下取整，得出该位置所在的桶序号；

步骤2-6：输出检索结果：输出该位置所在的桶序号和槽内标号，即数据存储单元基地址和该名称数据在数据存储空间中相对于基地址的地址偏移量；

步骤2-7：名称数据检索操作结束。

Images