基于二元组的简单正则表达式的快速检索算法

在大型数据集群网络中,业务逻辑节点和数据库节点分布在不同的地理位置,导致在该网络中创建或检索用户数据将经历较大的网络延迟.如何快速找到用户数据的地理位置节点（服务器识别号）将是减少网络延迟的关键.介绍一种动态索引算法,基于简单正则表达,建立用户数据和服务器组之间的映射关系,并引入动态多叉树,实现动态更改映射关系.引入一元组数据节点和二元组数据节点的概念,应用于多叉树,通过分析一元组多叉树和二元组多叉树的时间效率和空间效率,证明二元组多叉树随着树深的增长,检索时间复杂度保持更好的线性特性.通过一些性能测试的实验数据的比较,得出二元组方案的综合性能更优的结论.最后,简要地介绍该算法的应用领域.

Fast searching algorithm based on 2-tuple data pair for mini regular expression

In the large-size data cluster network, service logic nodes and database nodes located in different geographical sites, which cause the creating or querying subscriber data, will experience a big network delay. So how to quickly find the server ID list for the subscriber data will be a key factor to reduce the network delay. In order to resolve this issue, a “dy- namic indexing”algorithm is proposed in this paper. The core algorithm is based on two technologies： 1 ） a mini regular ex- pression which can realize the complicated mappings between subscriber data and server list, and 2） the dynamical M-tree on which user can change the mapping rules dynamically. This paper introduces the concepts of 1-tuple data and 2-tuple data pair for this M-tree respectively. After analyzing key factors for this algorithm, including its time efficiency and space efficiency, this paper makes a conclusion that compared with the 1-tuple M-tree, the searching time complication is keeping better linear for the 2-tuple M-tree when the tree depth is continuously growing. Some performance testing data for them is also provided to consolidate this conclusion. At the end of this paper, some considerations are provided for the applications of this algorithm.