公开(公告)号：US07539153B1

公开(公告)日：2009-05-26

申请号：US12241513

申请日：2008-09-30

申请人： Jun Liang ,  Shijun Shen ,  Meng Li ,  Juan Zhang ,  Rui Hu ,  Jun Gong

发明人： Jun Liang ,  Shijun Shen ,  Meng Li ,  Juan Zhang ,  Rui Hu ,  Jun Gong

IPC分类号： G01R31/08

CPC分类号： H04L45/00 ,  H04L45/7457

摘要： The present invention discloses a method and apparatus for longest prefix matching. The method includes (A) reading a current-level trie node (TNODE) in the trie, (B) determining whether an offset field of the TNODE indicates that a matched prefix exists in an upper level node and, if so, adding the offset field of the TNODE to a pointer that points to a leaf array in the upper level node, updating a current best match pointer with the computation result and executing block (C), otherwise, executing block (C), (C) determining whether the TNODE has a child node according to a child bitmap, when it is determined that a branch flag of the TNODE matches a corresponding bit of a search keyword, and (D) when it is determined that the TNODE has no child node, reading the internal bitmap of the TNODE, computing a longest matched prefix in the TNODE according to the internal bitmap and a pointer that points to a leaf array in the TNODE, updating the current best match pointer with the computation result, and computing an address of a leaf node (LNODE) associated with the current best match pointer.

摘要翻译： 本发明公开了一种用于最长前缀匹配的方法和装置。 该方法包括：（A）读取该特技中的当前级别的特里节点（TNODE），（B）确定TNODE的偏移字段是否表示在上层节点中存在匹配的前缀，如果是， 将TNODE的字段指向指向上级节点中的叶阵列的指针，用计算结果和执行块（C）更新当前最佳匹配指针，否则执行块（C），（C）确定是否 当确定TNODE的分支标志与搜索关键字的相应位匹配时，TNODE具有根据子位图的子节点，以及（D）当确定TNODE没有子节点时，读取内部 TNODE的位图，根据内部位图计算TNODE中最长的匹配前缀，以及指向TNODE中的叶阵列的指针，使用计算结果更新当前最佳匹配指针，并计算叶节点的地址 （LNODE） nt最佳匹配指针。

公开(公告)号：US08325721B2

公开(公告)日：2012-12-04

申请号：US12511558

申请日：2009-07-29

申请人： Jun Gong ,  Chong Zhan ,  Hongfei Chen ,  Rui Hu ,  Jian Zhang ,  Hunghsiang Jonathan Chao ,  Hao Su ,  Xiaozhong Wang ,  Tuanhui Sun

发明人： Jun Gong ,  Chong Zhan ,  Hongfei Chen ,  Rui Hu ,  Jian Zhang ,  Hunghsiang Jonathan Chao ,  Hao Su ,  Xiaozhong Wang ,  Tuanhui Sun

IPC分类号： H04L12/28 ,  H04L12/56

CPC分类号： G06F17/30628 ,  H04L45/00 ,  H04L45/54 ,  H04L45/745

摘要： A method for selecting a hash function, a method for storing and searching a routing table and devices thereof are provided. The method for selecting a hash function includes: hashing data to be hashed by using a current alternative hash function; decoding a hash result; accumulating decoded results until no carry occurs during the accumulation; and selecting a current alternative hash function with no carry generated as a formal hash function. The method for storing a routing table includes: dividing the routing table into a next-level node pointer portion and a prefix portion for being stored; and selecting a hash function by using the above method for selecting a hash function. The method for searching a routing table includes: directly searching an IP address to be searched according to a directly stored length of a next-level node pointer portion for storing the routing table; and reading a prefix node according to a searched result. Thus, hash collision can be avoided, and memory resources occupied by the routing table can be effectively reduced.

摘要翻译： 提供了一种用于选择散列函数的方法，用于存储和搜索路由表的方法及其装置。 用于选择散列函数的方法包括：通过使用当前替代散列函数来散列要散列的数据; 解码哈希结果; 累积解码结果，直到在累积期间不发生进位; 并且选择当前的替代散列函数，而不产生作为形式散列函数的进位。 存储路由表的方法包括：将路由表划分为下一级节点指针部分和用于存储的前缀部分; 以及通过使用上述用于选择散列函数的方法来选择散列函数。 搜索路由表的方法包括：根据用于存储路由表的下一级节点指针部分的直接存储长度直接搜索要搜索的IP地址; 并根据搜索结果读取前缀节点。 因此，可以避免哈希冲突，并且可以有效地减少路由表占用的存储器资源。

公开(公告)号：US20100058027A1

公开(公告)日：2010-03-04

申请号：US12511558

申请日：2009-07-29

申请人： Jun Gong ,  Chong Zhan ,  Hongfei Chen ,  Rui Hu ,  Jian Zhang ,  Hunghsiang Jonathan Chao ,  Hao Su ,  Xiaozhong Wang ,  Tuanhui Sun

发明人： Jun Gong ,  Chong Zhan ,  Hongfei Chen ,  Rui Hu ,  Jian Zhang ,  Hunghsiang Jonathan Chao ,  Hao Su ,  Xiaozhong Wang ,  Tuanhui Sun

IPC分类号： G06F12/08

CPC分类号： G06F17/30628 ,  H04L45/00 ,  H04L45/54 ,  H04L45/745

摘要： A method for selecting a hash function, a method for storing and searching a routing table and devices thereof are provided. The method for selecting a hash function includes: hashing data to be hashed by using a current alternative hash function; decoding a hash result; accumulating decoded results until no carry occurs during the accumulation; and selecting a current alternative hash function with no carry generated as a formal hash function. The method for storing a routing table includes: dividing the routing table into a next-level node pointer portion and a prefix portion for being stored; and selecting a hash function by using the above method for selecting a hash function. The method for searching a routing table includes: directly searching an IP address to be searched according to a directly stored length of a next-level node pointer portion for storing the routing table; and reading a prefix node according to a searched result. Thus, hash collision can be avoided, and memory resources occupied by the routing table can be effectively reduced.

摘要翻译： 提供了一种用于选择散列函数的方法，用于存储和搜索路由表的方法及其装置。 用于选择散列函数的方法包括：通过使用当前替代散列函数来散列要散列的数据; 解码哈希结果; 累积解码结果，直到在累积期间不发生进位; 并且选择当前的替代散列函数，而不产生作为形式散列函数的进位。 存储路由表的方法包括：将路由表划分为下一级节点指针部分和用于存储的前缀部分; 以及通过使用上述用于选择散列函数的方法来选择散列函数。 搜索路由表的方法包括：根据用于存储路由表的下一级节点指针部分的直接存储长度直接搜索要搜索的IP地址; 并根据搜索结果读取前缀节点。 因此，可以避免哈希冲突，并且可以有效地减少路由表占用的存储器资源。

公开(公告)号：US09390134B2

公开(公告)日：2016-07-12

申请号：US13339043

申请日：2011-12-28

申请人： Rui Hu ,  Jian Chen

发明人： Rui Hu ,  Jian Chen

IPC分类号： G06F17/30

CPC分类号： G06F17/30516 ,  G06F17/30867

摘要： A regular expression matching method and system, and a searching device are provided. First, the searching device performs string filtering on a data stream to be matched, in which if keywords in the data stream and preset character words have at least one same character, the searching device indicates that the data stream passes through the string filtering. Then the searching device performs regular expression filtering on the data stream passing through the string filtering. In a string filtering process through the method, system, and device, when Hash mapping positions of the keywords of the data stream are a subset of the Hash mapping positions of the character words, it indicates that the data stream passes through the string filtering, and it is not required to store the keywords and further compare the keywords with the character words, thereby saving the storage space and improving performance.

摘要翻译： 提供了正则表达式匹配方法和系统，以及搜索装置。 首先，搜索装置对要匹配的数据流执行字符串过滤，其中如果数据流中的关键字和预设字符字具有至少一个相同的字符，则搜索装置指示数据流通过字符串过滤。 然后，搜索设备对通过字符串过滤的数据流执行正则表达式过滤。 在通过方法，系统和设备的字符串过滤过程中，当数据流的关键字的哈希映射位置是字符字的哈希映射位置的子集时，表示数据流通过字符串过滤， 并且不需要存储关键词并进一步将关键词与字符词进行比较，从而节省存储空间并提高性能。

公开(公告)号：US08606780B2

公开(公告)日：2013-12-10

申请号：US13179258

申请日：2011-07-08

申请人： Rui Hu ,  Xin-Jing Wang ,  Juan Xu ,  Xiao Kong

发明人： Rui Hu ,  Xin-Jing Wang ,  Juan Xu ,  Xiao Kong

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30265

摘要： Search queries for images are received from users. An original order of responsive images to the query is determined. Duplicate images and words associated with the duplicate images are identified for each of the responsive images. Common words associated with the duplicate images are identified. The responsive images are annotated with the common words and an annotated order is determined. A re-ranked order is determined based on the original order and the annotated order. Responsive images are presented to the user in the re-ranked order.

摘要翻译： 从用户那里收到图像的搜索查询。 确定响应图像到查询的原始顺序。 针对每个响应图像识别与重复图像相关联的重复图像和词。 识别与重复图像相关联的常用词。 响应图像用公共字注释，并且确定注释顺序。 根据原始订单和注释顺序确定重新排序的订单。 以重新排序的顺序将响应性图像呈现给用户。

公开(公告)号：US20140037198A1

公开(公告)日：2014-02-06

申请号：US13567309

申请日：2012-08-06

申请人： Diane Larlus-Larrondo ,  Rui Hu ,  Craig Saunders ,  Gabriela Csurka

发明人： Diane Larlus-Larrondo ,  Rui Hu ,  Craig Saunders ,  Gabriela Csurka

IPC分类号： G06K9/34 ,  G06K9/62

CPC分类号： G06K9/00 ,  G06T7/11 ,  G06T7/162 ,  G06T7/194 ,  G06T2207/20076

摘要： An image segmentation method includes generating a hierarchy of regions by unsupervised segmentation of an input image. Each region is described with a respective region feature vector representative of the region. Hierarchical structures are identified, each including a parent region and its respective child regions in the hierarchy. Each hierarchical structure is described with a respective hierarchical feature vector that is based on the region feature vectors of the respective parent and child regions. The hierarchical structures are classified according to a set of predefined classes with a hierarchical classifier component that is trained with hierarchical feature vectors of hierarchical structures of training images. The training images have semantic regions labeled according to the set of predefined classes. The input image is segmented into a plurality of semantic regions based on the classification of the hierarchical structures and optionally also on classification of the individual regions.

摘要翻译： 图像分割方法包括通过输入图像的无监督分割来生成区域的层级。 用表示该区域的相应区域特征向量来描述每个区域。 识别分层结构，每个结构包括层次结构中的父区域及其各自的子区域。 使用基于相应父子区域和子区域的区域特征向量的相应分层特征向量来描述每个分层结构。 层次结构根据一组具有层次分类器组件的预定义类别进行分类，该层级分类器组件用训练图像的层次结构的分层特征向量进行训练。 训练图像具有根据预定义类的集合标记的语义区域。 基于层次结构的分类，并且还可以根据各个区域的分类，将输入图像分割成多个语义区域。

公开(公告)号：US20120102055A1

公开(公告)日：2012-04-26

申请号：US13339043

申请日：2011-12-28

申请人： Rui Hu ,  Jian Chen

发明人： Rui Hu ,  Jian Chen

IPC分类号： G06F17/30

CPC分类号： G06F17/30516 ,  G06F17/30867

摘要： A regular expression matching method and system, and a searching device are provided. First, the searching device performs string filtering on a data stream to be matched, in which if keywords in the data stream and preset character words have at least one same character, the searching device indicates that the data stream passes through the string filtering. Then the searching device performs regular expression filtering on the data stream passing through the string filtering. In a string filtering process through the method, system, and device, when Hash mapping positions of the keywords of the data stream are a subset of the Hash mapping positions of the character words, it indicates that the data stream passes through the string filtering, and it is not required to store the keywords and further compare the keywords with the character words, thereby saving the storage space and improving performance.

摘要翻译： 提供了正则表达式匹配方法和系统，以及搜索装置。 首先，搜索装置对要匹配的数据流执行字符串过滤，其中如果数据流中的关键字和预设字符字具有至少一个相同的字符，则搜索装置指示数据流通过字符串过滤。 然后，搜索设备对通过字符串过滤的数据流执行正则表达式过滤。 在通过方法，系统和设备的字符串过滤过程中，当数据流的关键字的哈希映射位置是字符字的哈希映射位置的子集时，表示数据流通过字符串过滤， 并且不需要存储关键词并进一步将关键词与字符词进行比较，从而节省存储空间并提高性能。

公开(公告)号：US08873812B2

公开(公告)日：2014-10-28

申请号：US13567309

申请日：2012-08-06

申请人： Diane Larlus-Larrondo ,  Rui Hu ,  Craig Saunders ,  Gabriela Csurka

发明人： Diane Larlus-Larrondo ,  Rui Hu ,  Craig Saunders ,  Gabriela Csurka

IPC分类号： G06K9/00

CPC分类号： G06K9/00 ,  G06T7/11 ,  G06T7/162 ,  G06T7/194 ,  G06T2207/20076

摘要： An image segmentation method includes generating a hierarchy of regions by unsupervised segmentation of an input image. Each region is described with a respective region feature vector representative of the region. Hierarchical structures are identified, each including a parent region and its respective child regions in the hierarchy. Each hierarchical structure is described with a respective hierarchical feature vector that is based on the region feature vectors of the respective parent and child regions. The hierarchical structures are classified according to a set of predefined classes with a hierarchical classifier component that is trained with hierarchical feature vectors of hierarchical structures of training images. The training images have semantic regions labeled according to the set of predefined classes. The input image is segmented into a plurality of semantic regions based on the classification of the hierarchical structures and optionally also on classification of the individual regions.

摘要翻译： 图像分割方法包括通过输入图像的无监督分割来生成区域的层级。 用表示该区域的相应区域特征向量描述每个区域。 识别分层结构，每个结构包括层次结构中的父区域及其各自的子区域。 使用基于相应父子区域和子区域的区域特征向量的相应分层特征向量来描述每个分层结构。 层次结构根据一组具有层次分类器组件的预定义类别进行分类，该层级分类器组件用训练图像的层次结构的分层特征向量进行训练。 训练图像具有根据预定义类的集合标记的语义区域。 基于层次结构的分类，并且还可以根据各个区域的分类，将输入图像分割成多个语义区域。

公开(公告)号：US08433140B2

公开(公告)日：2013-04-30

申请号：US12822873

申请日：2010-06-24

申请人： Qifa Ke ,  Ming Liu ,  Yi Li ,  Rui Hu ,  Yanfeng Sun

发明人： Qifa Ke ,  Ming Liu ,  Yi Li ,  Rui Hu ,  Yanfeng Sun

IPC分类号： G06K9/62 ,  G06K9/00

CPC分类号： G06F17/30265 ,  G06K9/6202

摘要： Methods and computer-readable media for propagating content category information to images stored in a database are described. A seed image that is associated with a known content category is received. A content-based image retrieval is conducted using the seed image as a search query image. A number of search result images are identified. The content category is propagated to the search result images. Metadata associated with the search result images is aggregated and analyzed to identify domains that should also be associated with the content category. Additional images that are associated with the domain are identified and the content category propagated thereto. The process is iterated using the additional images as search query images for the content-based image retrieval.

摘要翻译： 描述用于将内容分类信息传播到存储在数据库中的图像的方法和计算机可读介质。 接收与已知内容类别相关联的种子图像。 使用种子图像作为搜索查询图像进行基于内容的图像检索。 识别出多个搜索结果图像。 内容类别被传播到搜索结果图像。 与搜索结果图像相关联的元数据被聚合和分析，以识别也应该与内容类别相关联的域。 识别与域相关联的附加图像，并将内容类别传播到其上。 使用附加图像作为用于基于内容的图像检索的搜索查询图像来迭代该过程。