CN107431660B - 检索装置、检索方法及记录介质 - Google Patents

检索装置、检索方法及记录介质 Download PDF

Info

Publication number
CN107431660B
CN107431660B CN201680014265.4A CN201680014265A CN107431660B CN 107431660 B CN107431660 B CN 107431660B CN 201680014265 A CN201680014265 A CN 201680014265A CN 107431660 B CN107431660 B CN 107431660B
Authority
CN
China
Prior art keywords
leaf
node
bit
internal node
vector
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.)
Active
Application number
CN201680014265.4A
Other languages
English (en)
Chinese (zh)
Other versions
CN107431660A (zh
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.)
Entiti Tecmo Business Co ltd
Original Assignee
NTT Communications Corp
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 NTT Communications Corp filed Critical NTT Communications Corp
Publication of CN107431660A publication Critical patent/CN107431660A/zh
Application granted granted Critical
Publication of CN107431660B publication Critical patent/CN107431660B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2246—Trees, e.g. B+trees
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/25—Routing or path finding in a switch fabric
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9027—Trees
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30036—Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30036—Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
    • G06F9/30038—Instructions to perform operations on packed data, e.g. vector, tile or matrix operations using a mask

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • Mathematical Physics (AREA)
  • Data Mining & Analysis (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
CN201680014265.4A 2015-03-11 2016-01-29 检索装置、检索方法及记录介质 Active CN107431660B (zh)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
JP2015-048657 2015-03-11
JP2015048657A JP5960863B1 (ja) 2015-03-11 2015-03-11 検索装置、検索方法、プログラム、及び記録媒体
PCT/JP2016/052664 WO2016143405A1 (ja) 2015-03-11 2016-01-29 検索装置、検索方法、プログラム、及び記録媒体

Publications (2)

Publication Number Publication Date
CN107431660A CN107431660A (zh) 2017-12-01
CN107431660B true CN107431660B (zh) 2020-08-18

Family

ID=56550536

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201680014265.4A Active CN107431660B (zh) 2015-03-11 2016-01-29 检索装置、检索方法及记录介质

Country Status (7)

Country Link
US (1) US11762826B2 (de)
EP (1) EP3270551B1 (de)
JP (1) JP5960863B1 (de)
CN (1) CN107431660B (de)
AU (1) AU2016230539B2 (de)
ES (1) ES2830746T3 (de)
WO (1) WO2016143405A1 (de)

Families Citing this family (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10464500B2 (en) 2017-05-29 2019-11-05 Aamp Of Florida, Inc. Aftermarket head unit interface and protocol converter cartridge
CN111373389B (zh) * 2017-11-20 2023-11-17 华为技术有限公司 数据存储系统以及用于提供数据存储系统的方法
CN108008728B (zh) * 2017-12-12 2020-01-17 深圳市银星智能科技股份有限公司 清洁机器人以及基于清洁机器人的最短路径规划方法
JP2020004132A (ja) * 2018-06-28 2020-01-09 エヌ・ティ・ティ・コミュニケーションズ株式会社 検索装置、検索方法、プログラム、及び記録媒体
JP7088868B2 (ja) * 2019-03-22 2022-06-21 エヌ・ティ・ティ・コミュニケーションズ株式会社 通信装置、通信方法及びプログラム
US11288244B2 (en) * 2019-06-10 2022-03-29 Akamai Technologies, Inc. Tree deduplication
US11652791B2 (en) * 2019-08-07 2023-05-16 Cisco Technology, Inc. Consolidated routing table for extranet virtual networks
KR20220128791A (ko) 2021-03-15 2022-09-22 삼성전자주식회사 비휘발성 메모리를 포함하는 전자 장치 및 그것의 비휘발성 메모리 관리 방법
US11683039B1 (en) 2021-03-31 2023-06-20 DreamBig Semiconductor Inc. TCAM-based not logic
CN115328366B (zh) * 2022-08-11 2023-09-19 北京智慧星光信息技术有限公司 基于全路径计算的千万级树形节点搜索展示方法和系统
US12177180B2 (en) 2023-05-23 2024-12-24 Centripetal Networks, Llc Methods and systems for efficient cybersecurity policy enforcement on network communications

Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6522632B1 (en) * 1998-05-06 2003-02-18 Avici Systems Apparatus and method for efficient prefix search
WO2004040400A2 (en) * 2002-09-16 2004-05-13 North Carolina State University Methods and systems for fast binary network address lookups using parent node information stored in routing tables entries
US7523218B1 (en) * 2002-04-30 2009-04-21 University Of Florida Research Foundation, Inc. O(log n) dynamic router tables for prefixes and ranges
US7539153B1 (en) * 2008-05-05 2009-05-26 Huawei Technologies Co., Ltd. Method and apparatus for longest prefix matching based on a trie
CN101484895A (zh) * 2006-07-07 2009-07-15 新叶股份有限公司 比特序列检索装置、检索方法以及程序
US7831626B1 (en) * 2006-11-27 2010-11-09 Netlogic Microsystems, Inc. Integrated search engine devices having a plurality of multi-way trees of search keys therein that share a common root node
CN101911068A (zh) * 2008-01-17 2010-12-08 新叶股份有限公司 比特序列检索装置、检索方法以及程序
CN102739551A (zh) * 2012-07-17 2012-10-17 中山大学 多存储器流水路由体系结构
CN102741841A (zh) * 2009-11-30 2012-10-17 新叶股份有限公司 比特序列检索装置、检索方法以及程序
CN104052669A (zh) * 2013-03-12 2014-09-17 西普联特公司 用于处理交替配置的最长前缀匹配表的装置和方法

Family Cites Families (21)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
IL100987A (en) * 1991-02-27 1995-10-31 Digital Equipment Corp Method and apparatus for compiling code
US5664172A (en) * 1994-07-19 1997-09-02 Oracle Corporation Range-based query optimizer
IL134835A0 (en) * 1997-09-15 2001-05-20 Effnet Group Ab Method and system for fast routing lookups
US6266706B1 (en) 1997-09-15 2001-07-24 Effnet Group Ab Fast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagrams
JP3547625B2 (ja) 1998-09-03 2004-07-28 三菱電機株式会社 データ検索装置およびデータ検索方法
US6829695B1 (en) * 1999-09-03 2004-12-07 Nexql, L.L.C. Enhanced boolean processor with parallel input
US6675163B1 (en) * 2000-04-06 2004-01-06 International Business Machines Corporation Full match (FM) search algorithm implementation for a network processor
US20030208488A1 (en) * 2000-09-20 2003-11-06 North Dakota State University System and method for organizing, compressing and structuring data for data mining readiness
US6931418B1 (en) * 2001-03-26 2005-08-16 Steven M. Barnes Method and system for partial-order analysis of multi-dimensional data
US6985483B2 (en) * 2001-07-31 2006-01-10 North Carolina State University Methods and systems for fast packet forwarding
US7444318B2 (en) * 2002-07-03 2008-10-28 University Of Florida Research Foundation, Inc. Prefix partitioning methods for dynamic router tables
US8886677B1 (en) * 2004-07-23 2014-11-11 Netlogic Microsystems, Inc. Integrated search engine devices that support LPM search operations using span prefix masks that encode key prefix length
JP4973101B2 (ja) * 2006-09-29 2012-07-11 日本電気株式会社 自動合成装置
US8086641B1 (en) * 2006-11-27 2011-12-27 Netlogic Microsystems, Inc. Integrated search engine devices that utilize SPM-linked bit maps to reduce handle memory duplication and methods of operating same
KR101127267B1 (ko) * 2007-05-01 2012-07-10 인터내셔널 비지네스 머신즈 코포레이션 유사 스트링 정합을 위한 방법 및 시스템
US9438413B2 (en) * 2010-01-08 2016-09-06 Novell, Inc. Generating and merging keys for grouping and differentiating volumes of files
US8522348B2 (en) * 2009-07-29 2013-08-27 Northwestern University Matching with a large vulnerability signature ruleset for high performance network defense
US8669977B2 (en) * 2009-10-01 2014-03-11 Intel Corporation Hierarchical mesh quantization that facilitates efficient ray tracing
US20140188885A1 (en) * 2012-12-27 2014-07-03 Broadcom Corporation Utilization and Power Efficient Hashing
EP2973039B1 (de) * 2013-03-15 2020-09-16 Factual Inc. Vorrichtung, systeme und verfahren zur gruppierung von datensätzen
US9842132B2 (en) * 2015-10-23 2017-12-12 International Business Machines Corporation Bloom filter index for device discovery

Patent Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6522632B1 (en) * 1998-05-06 2003-02-18 Avici Systems Apparatus and method for efficient prefix search
US7523218B1 (en) * 2002-04-30 2009-04-21 University Of Florida Research Foundation, Inc. O(log n) dynamic router tables for prefixes and ranges
WO2004040400A2 (en) * 2002-09-16 2004-05-13 North Carolina State University Methods and systems for fast binary network address lookups using parent node information stored in routing tables entries
CN101484895A (zh) * 2006-07-07 2009-07-15 新叶股份有限公司 比特序列检索装置、检索方法以及程序
US7831626B1 (en) * 2006-11-27 2010-11-09 Netlogic Microsystems, Inc. Integrated search engine devices having a plurality of multi-way trees of search keys therein that share a common root node
CN101911068A (zh) * 2008-01-17 2010-12-08 新叶股份有限公司 比特序列检索装置、检索方法以及程序
US7539153B1 (en) * 2008-05-05 2009-05-26 Huawei Technologies Co., Ltd. Method and apparatus for longest prefix matching based on a trie
CN102741841A (zh) * 2009-11-30 2012-10-17 新叶股份有限公司 比特序列检索装置、检索方法以及程序
CN102739551A (zh) * 2012-07-17 2012-10-17 中山大学 多存储器流水路由体系结构
CN104052669A (zh) * 2013-03-12 2014-09-17 西普联特公司 用于处理交替配置的最长前缀匹配表的装置和方法

Also Published As

Publication number Publication date
WO2016143405A1 (ja) 2016-09-15
JP2016170526A (ja) 2016-09-23
EP3270551A4 (de) 2018-07-18
ES2830746T3 (es) 2021-06-04
JP5960863B1 (ja) 2016-08-02
CN107431660A (zh) 2017-12-01
EP3270551A1 (de) 2018-01-17
EP3270551B1 (de) 2020-10-14
US11762826B2 (en) 2023-09-19
AU2016230539A1 (en) 2017-10-05
US20180039662A1 (en) 2018-02-08
AU2016230539B2 (en) 2018-08-16

Similar Documents

Publication Publication Date Title
CN107431660B (zh) 检索装置、检索方法及记录介质
CN104904167B (zh) 通信网络中对于分组处理的高性能基于哈希的查找
US8880507B2 (en) Longest prefix match using binary search tree
KR100962653B1 (ko) 블룸 필터 및 복수 해싱 구조를 사용한 ｉｐ 주소 검색방법 및 장치
KR101028470B1 (ko) Ｉｐ주소 검색을 위한 장치 및 방법
KR100586461B1 (ko) 파이프라인 이진 트리를 이용한 ｉｐ 어드레스 검색 방법,하드웨어 구조 및 기록매체
CN105141525B (zh) IPv6路由查找方法及装置
CN107967219A (zh) 一种基于tcam的大规模字符串高速查找方法
EP1335538A2 (de) Verfahren und System für eine Addressermittlung bei Datenkommunikation
US20170142013A1 (en) Search apparatus, search configuration method, and search method
US20160241473A1 (en) Apparatus and Method for Processing Alternately Configured Longest Prefix Match Tables
JP2009219012A (ja) 固定長データの検索方法
CN100496019C (zh) IPv6路由表快速查找和更新的方法
CN104780101A (zh) 内容中心网络转发平面fib表结构及其检索方法
CN118282943A (zh) 一种查找路由表项的方法及装置
CN105227468A (zh) 一种查找装置、查找方法和配置方法
Lim et al. Binary searches on multiple small trees for IP address lookup
JP6205463B2 (ja) 検索装置、検索方法、プログラム、及び記録媒体
Bahrambeigy et al. Bloom-Bird: A scalable open source router based on Bloom filter
CN107204926B (zh) 预处理cache的路由快速查找方法
CN112565089B (zh) 一种路由信息的处理方法及装置
Pao et al. Bit-shuffled trie: IP lookup with multi-level index tables
JP2018196075A (ja) 検索装置、検索プログラム、及び検索方法
JP2020004132A (ja) 検索装置、検索方法、プログラム、及び記録媒体
CN116582486A (zh) 一种针对可变长地址的路由查找方法及装置

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CP03 Change of name, title or address
CP03 Change of name, title or address

Address after: Tokyo, Japan

Patentee after: Entiti Tecmo Business Co.,Ltd.

Country or region after: Japan

Address before: Tokyo, Japan

Patentee before: NTT COMMUNICATIONS Corp.

Country or region before: Japan