[go: up one dir, main page]

CN101478608A - 基于二维散列的海量数据的快速操作方法 - Google Patents

基于二维散列的海量数据的快速操作方法 Download PDF

Info

Publication number
CN101478608A
CN101478608A CNA2009100281061A CN200910028106A CN101478608A CN 101478608 A CN101478608 A CN 101478608A CN A2009100281061 A CNA2009100281061 A CN A2009100281061A CN 200910028106 A CN200910028106 A CN 200910028106A CN 101478608 A CN101478608 A CN 101478608A
Authority
CN
China
Prior art keywords
hash
index
data
index key
dimensional
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CNA2009100281061A
Other languages
English (en)
Inventor
孙力斌
陈旻
刘国祥
梁斌
张家荣
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
LINKAGE SYSTEM INTEGRATION CO Ltd
Original Assignee
LINKAGE SYSTEM INTEGRATION CO Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by LINKAGE SYSTEM INTEGRATION CO Ltd filed Critical LINKAGE SYSTEM INTEGRATION CO Ltd
Priority to CNA2009100281061A priority Critical patent/CN101478608A/zh
Publication of CN101478608A publication Critical patent/CN101478608A/zh
Priority to US12/644,965 priority patent/US20100179954A1/en
Pending legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/088—Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/14—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using a plurality of keys or algorithms

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

基于二维散列的海量数据的快速操作方法，首先是利用散列算法，将具体的数据记录集序列，在索引关键字和索引序列地址之间形成特定的映射关系，构造一维散列队列存储数据；当索引关键字和索引序列地址之间形成特定的映射关系不能唯一定位一条数据记录时，则根据索引关键字是否相同构造一个二维的散列链表，挂在第一层散列队列的各个节点下，作为之前构造的一维散列队列各节点的扩充；当需要按照索引关键字对数据集进行操作时，通过相同的散列算法，从一维散列队列，反向映射获取数据集中索引关键字所对应的数据记录地址；如果发现一维散列队列节点下还有二维散列链表，则根据查询关键字的取值纵向遍历此二维散列链表，查找符合条件的数据记录地址。

Description

基于二维散列的海量数据的快速操作方法
一、技术领域
本发明涉及一种电信运营支撑系统的方法，尤其是海量数据的快速操作方法。
二、背景技术
随着电信行业用户和业务量的巨增，对千万级话单数据的快速处理成为电信运营系统的难点和重点。目前的系统应用需要对存在于计算机系统物理内存中的海量数据频繁进行查询、更新、删除操作，这些数据上的索引算法的效率，显然已经成为影响系统运行速度的关键。
而现有的单向散列函数指的是根据输入消息(任何字节串，如文本字符串、Word文档、JPG文件等)输出固定长度数值的算法，输出数值也称为“散列值”或“消息摘要”，其长度取决于所采用的算法，通常在128～256位之间。单向散列函数旨在创建用于验证消息完整性的简短摘要。在诸如TPC/IP等通信协议中，常采用检验和或CRC(循环冗余校验)来验证消息的完整性。
三、发明内容
本发明目的是，针对电信运营系统有数据量大，要求系统响应快速、稳定并具有自维护性等特点，提出一种面向电信运营系统的方法，即基于二维散列的海量数据的快速操作方法；本发明目的还在于解决下列问题：
●极高效的数据查找——当其管理的数据按照查找关键字得到足够的均匀散列时，甚至可以直接定址，返回查找关键字所对应的记录集；数据记录变更无须重构索引；可无限制动态扩充所管理的数据记录量。采用此发明算法组织的数据索引结构，可以使得对百万数据记录集合的内存数据表的查找效率达到微秒级别，在技术上极大的满足了电信运营系统的要求。
本发明的技术方案是，基于二维散列的海量数据的快速操作方法，首先是利用散列算法，将具体的数据记录集序列，在索引关键字和索引序列地址之间形成特定的映射关系，构造一维散列队列存储数据；当索引关键字和索引序列地址之间形成特定的映射关系不能唯一定位一条数据记录时，则根据索引关键字是否相同构造一个二维的散列链表，挂在第一层散列队列的各个节点下，作为之前构造的一维散列队列各节点的扩充，区分索引字段值相同与不同；
当需要按照索引关键字对数据集进行操作时，通过相同的散列算法，从一维散列队列，反向映射获取数据集中索引关键字所对应的数据记录地址，实现快速定位的目的；如果发现一维散列队列节点下还有二维散列链表，则根据查询关键字的取值纵向遍历此二维散列链表，查找符合条件的数据记录地址；
创建索引接口：根据索引关键字计算出散列队列下标值，实现索引关键字和索引序列地址之间形成特定的映射关系转换；当不能够保证每条数据记录的索引关键字与通过散列算法后得到的散列队列下标值是一一对应时，延伸出一个二维的散列链表，挂在第一层散列队列的各个节点下，区分索引字段值相同与不同，而横向、纵向扩展，来解决冲突；通过上述映射关系，既能得到数据集上的一个快速索引结构；
查询接口：当需要按照索引关键字对数据集进行操作时，系统首先找到已经创建好的数据集索引入口，通过相同的散列算法，计算出下标值，从一维散列队列，反向映射获取数据集中索引关键字所对应的数据记录地址，实现快速定位的目的；如果发现一维散列队列节点下还有二维散列链表，则根据查询关键字的取值纵向遍历此二维散列链表，查找符合条件的数据记录地址；最后，将符合条件的结果集返回。
此发明主要分成散列算法、二维散列算法两个部分：
●散列算法
根据索引关键字计算出散列队列下标值，实现索引关键字和索引序列地址之间形成特定的映射关系转换。
●二维散列算法
不能够保证每条数据记录的索引关键字与通过散列算法后得到的散列队列下标值是一一对应的，因此极有可能出现对于不同的元素，通过散列算法后得到却计算出了相同的散列队列下标值即索引字段值；又或者有非唯一索引存在，这样就产生了“冲突”。因而设计出一个二维的散列链表，挂在第一层散列队列的各个节点下，区分索引字段值相同与不同，而横向、纵向扩展，来解决冲突。即具有两个索引散列链表的计算；
本发明的有益效果：该发明已经在内存数据管理产品中得到成功应用，并作为我国核心电信运营系统产品关键业务数据管理中心的主要构成技术方案，部署在计费账务后台业务处理系统中，综合处理速度得到了50％~80％的提升。
四、附图说明
图1.二维散列索引逻辑结构图
五、具体实施方式
本发明目前内嵌于内存数据管理的索引管理模块中，也可独立封装，做为第三方插件提供于其他模块适配。其在索引管理模块中应用的标准的软件模型如图1所示。
●创建索引接口
使用本发明技术，根据索引关键字计算出散列队列下标值，实现索引关键字和索引序列地址之间形成特定的映射关系转换；当不能够保证每条数据记录的索引关键字与通过散列算法后得到的散列队列下标值是一一对应时，延伸出一个二维的散列链表，挂在第一层散列队列的各个节点下，区分索引字段值相同与不同，而横向、纵向扩展，来解决冲突。
系统维护上述映射关系，既能得到数据集上的一个快速索引结构。
●查询接口
当需要按照索引关键字对数据集进行操作时，系统首先找到已经创建好的数据集索引入口，通过相同的散列算法，计算出下标值，从一维散列队列，反向映射获取数据集中索引关键字所对应的数据记录地址，实现快速定位的目的；如果发现一维散列队列节点下还有二维散列链表，则根据查询关键字的取值纵向遍历此二维散列链表，查找符合条件的数据记录地址。最后，将符合条件的结果集返回。

Claims (1)

1、基于二维散列的海量数据的快速操作方法，首先是利用散列算法，将具体的数据记录集序列，在索引关键字和索引序列地址之间形成特定的映射关系，构造一维散列队列存储数据；当索引关键字和索引序列地址之间形成特定的映射关系不能唯一定位一条数据记录时，则根据索引关键字是否相同构造一个二维的散列链表，挂在第一层散列队列的各个节点下，作为之前构造的一维散列队列各节点的扩充，区分索引字段值相同与不同；
其特征是当需要按照索引关键字对数据集进行操作时，通过相同的散列算法，从一维散列队列，反向映射获取数据集中索引关键字所对应的数据记录地址，实现快速定位的目的；如果发现一维散列队列节点下还有二维散列链表，则根据查询关键字的取值纵向遍历此二维散列链表，查找符合条件的数据记录地址；
创建索引接口：根据索引关键字计算出散列队列下标值，实现索引关键字和索引序列地址之间形成特定的映射关系转换；当不能够保证每条数据记录的索引关键字与通过散列算法后得到的散列队列下标值是一一对应时，延伸出一个二维的散列链表，挂在第一层散列队列的各个节点下，区分索引字段值相同与不同，而横向、纵向扩展，来解决冲突；通过上述映射关系，既能得到数据集上的一个快速索引结构；
查询接口：当需要按照索引关键字对数据集进行操作时，系统首先找到已经创建好的数据集索引入口，通过相同的散列算法，计算出下标值，从一维散列队列，反向映射获取数据集中索引关键字所对应的数据记录地址，实现快速定位的目的；如果发现一维散列队列节点下还有二维散列链表，则根据查询关键字的取值纵向遍历此二维散列链表，查找符合条件的数据记录地址；最后，将符合条件的结果集返回。
CNA2009100281061A 2009-01-09 2009-01-09 基于二维散列的海量数据的快速操作方法 Pending CN101478608A (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
CNA2009100281061A CN101478608A (zh) 2009-01-09 2009-01-09 基于二维散列的海量数据的快速操作方法
US12/644,965 US20100179954A1 (en) 2009-01-09 2009-12-22 Quick Mass Data Manipulation Method Based on Two-Dimension Hash

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CNA2009100281061A CN101478608A (zh) 2009-01-09 2009-01-09 基于二维散列的海量数据的快速操作方法

Publications (1)

Publication Number Publication Date
CN101478608A true CN101478608A (zh) 2009-07-08

Family

ID=40839236

Family Applications (1)

Application Number Title Priority Date Filing Date
CNA2009100281061A Pending CN101478608A (zh) 2009-01-09 2009-01-09 基于二维散列的海量数据的快速操作方法

Country Status (2)

Country Link
US (1) US20100179954A1 (zh)
CN (1) CN101478608A (zh)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102129473A (zh) * 2011-04-19 2011-07-20 北京神州数码思特奇信息技术股份有限公司 一种静态数据检索方法
CN102054000B (zh) * 2009-10-28 2012-07-25 中国移动通信集团公司 数据查询方法、装置及系统
CN105027595A (zh) * 2013-03-08 2015-11-04 高通股份有限公司 用于发现邻域知悉网络中的设备的系统和方法
CN107291628A (zh) * 2017-07-04 2017-10-24 北京京东尚科信息技术有限公司 访问数据存储设备的方法和装置
CN108984115A (zh) * 2018-06-14 2018-12-11 北京理工大学 数据并行写入、读取方法、装置及系统

Families Citing this family (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102737127B (zh) * 2012-06-20 2015-04-08 厦门大学 一种海量数据存储方法
US9146677B2 (en) * 2013-01-28 2015-09-29 Applied Micro Circuits Corporation Systems and methods for queue request ordering without stalling requests in aliasing conditions by using a hash indexed based table
CN110175258B (zh) * 2016-02-05 2024-01-23 大连大学 建立基于位置敏感哈希索引的移动感知数据查询方法
US11113114B2 (en) * 2019-04-09 2021-09-07 Cisco Technology, Inc. Distributed object placement, replication, and retrieval for cloud-scale storage and data delivery
CN110688380B (zh) * 2019-09-24 2023-02-03 无锡科技职业学院 适用于存储空间受限的设备的通讯录防重构建方法
CN111651406B (zh) * 2020-05-21 2023-07-25 杭州明讯软件技术有限公司 一种自动化载波调度系统文件读取方法及装置
CN112256698B (zh) * 2020-10-16 2023-09-05 美林数据技术股份有限公司 一种基于多哈希函数的表关系自动关联方法
CN112671611B (zh) * 2020-12-23 2023-01-31 清华大学 基于sketch的大流检测方法和装置
CN113377774B (zh) * 2021-06-09 2025-03-07 北京金山云网络技术有限公司 数据查询方法、装置和电子设备
CN113434518B (zh) * 2021-08-26 2021-12-03 西安热工研究院有限公司 时序数据库查询方法、系统、设备及存储介质
CN117807277B (zh) * 2024-03-01 2024-05-17 中国人民解放军国防科技大学 一种高阶动态图数据存储方法、装置、设备及存储介质

Family Cites Families (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA2161376C (en) * 1994-10-27 2005-01-11 Toshiaki Minami Reversible multi-color thermal recording medium
US6092002A (en) * 1996-11-13 2000-07-18 Kimberly-Clark Worldwide, Inc. Variable tension process and apparatus for continuously moving layers
JP3876106B2 (ja) * 1999-03-25 2007-01-31 三菱製紙株式会社 可逆性二色感熱記録材料及び記録方法
US6710221B1 (en) * 1999-06-15 2004-03-23 Kimberly-Clark Worldwide, Inc. Absorbent articles incorporating color change graphics
US7373425B2 (en) * 2000-08-22 2008-05-13 Conexant Systems, Inc. High-speed MAC address search engine
US6931418B1 (en) * 2001-03-26 2005-08-16 Steven M. Barnes Method and system for partial-order analysis of multi-dimensional data
US7200270B2 (en) * 2001-12-13 2007-04-03 Kabushiki Kaisha Toshiba Pattern recognition apparatus and method using distributed model representation of partial images
US7809510B2 (en) * 2002-02-27 2010-10-05 Ip Genesis, Inc. Positional hashing method for performing DNA sequence similarity search
JP3880872B2 (ja) * 2002-03-04 2007-02-14 日本製紙株式会社 多色感熱記録体
AU2003900520A0 (en) * 2003-02-06 2003-02-20 Email Analysis Pty Ltd Information classification and retrieval using concept lattices
US7200604B2 (en) * 2004-02-17 2007-04-03 Hewlett-Packard Development Company, L.P. Data de-duplication
ES2368062T3 (es) * 2004-04-30 2011-11-14 The Procter & Gamble Company Artículo absorbente que cambia de color.
CN101262895B (zh) * 2005-09-13 2012-06-20 Sca卫生产品股份公司 卫生用吸收性制品
US20070156106A1 (en) * 2006-01-03 2007-07-05 Thomas James Klofta Disposable absorbent articles having temperature sensors
MX2009009571A (es) * 2007-03-09 2009-09-21 Procter & Gamble Articulo absorbente que tiene un indicador de preparacion para el entrenamiento en el uso del retrete.
US20090058892A1 (en) * 2007-08-31 2009-03-05 Ncr Corporation Direct thermal and inkjet dual-sided printing
US8775475B2 (en) * 2007-11-09 2014-07-08 Ebay Inc. Transaction data representations using an adjacency matrix
TWI361404B (en) * 2008-02-18 2012-04-01 Ind Tech Res Inst Storage and search method for flag event on two-dimensional space
US8229916B2 (en) * 2008-10-09 2012-07-24 International Business Machines Corporation Method for massively parallel multi-core text indexing

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102054000B (zh) * 2009-10-28 2012-07-25 中国移动通信集团公司 数据查询方法、装置及系统
CN102129473A (zh) * 2011-04-19 2011-07-20 北京神州数码思特奇信息技术股份有限公司 一种静态数据检索方法
CN102129473B (zh) * 2011-04-19 2016-09-14 北京思特奇信息技术股份有限公司 一种静态数据检索方法
CN105027595A (zh) * 2013-03-08 2015-11-04 高通股份有限公司 用于发现邻域知悉网络中的设备的系统和方法
CN105027595B (zh) * 2013-03-08 2019-04-23 高通股份有限公司 用于发现邻域知悉网络中的设备的系统和方法
CN107291628A (zh) * 2017-07-04 2017-10-24 北京京东尚科信息技术有限公司 访问数据存储设备的方法和装置
CN107291628B (zh) * 2017-07-04 2020-09-01 北京京东尚科信息技术有限公司 访问数据存储设备的方法和装置
CN108984115A (zh) * 2018-06-14 2018-12-11 北京理工大学 数据并行写入、读取方法、装置及系统
CN108984115B (zh) * 2018-06-14 2020-07-28 北京理工大学 数据并行写入、读取方法、装置及系统

Also Published As

Publication number Publication date
US20100179954A1 (en) 2010-07-15

Similar Documents

Publication Publication Date Title
CN101478608A (zh) 基于二维散列的海量数据的快速操作方法
CN104731864B (zh) 一种海量非结构化数据的数据存储方法
CN104536959B (zh) 一种Hadoop存取海量小文件的优化方法
CN103902632B (zh) 键值存储系统中构建文件系统的方法、装置及电子设备
CN103514250B (zh) 一种全局重复数据删除的方法和系统及存储装置
CN102831222B (zh) 一种基于重复数据删除的差量压缩方法
CN102662992B (zh) 一种海量小文件的存储、访问方法及装置
CN105069111B (zh) 云存储中基于相似性的数据块级数据去重方法
CN103544261B (zh) 一种海量结构化日志数据全局索引管理方法及装置
EP3037988A1 (en) Configuration method and device for hash database
CN101464901B (zh) 一种对象存储设备中的对象查找方法
WO2014015488A1 (zh) 一种数据存储、数据查询的方法及装置
CN103577123A (zh) 一种基于hdfs的小文件优化存储方法
WO2010099715A1 (zh) 数据操作方法、系统、客户端和数据服务器
CN103970875B (zh) 一种并行重复数据删除方法和系统
CN103838770A (zh) 一种数据逻辑分区的方法和系统
CN104077423A (zh) 一种基于一致性散列的结构化数据存储、查询和迁移方法
CN103198150B (zh) 一种大数据索引方法及系统
CN101442731A (zh) 一种话单剔重方法和装置
Xiao et al. Using parallel bloom filters for multiattribute representation on network services
CN104054071A (zh) 访问存储设备的方法和存储设备
CN104572862A (zh) 一种海量数据存储访问方法及系统
CN106570113A (zh) 一种海量矢量切片数据云存储方法及系统
CN103106147A (zh) 内存分配方法及系统
CN103744882B (zh) 一种基于键值对的目录片段表示方法及装置

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C12 Rejection of a patent application after its publication
RJ01 Rejection of invention patent application after publication

Open date: 20090708