公开(公告)号：US12056133B2

公开(公告)日：2024-08-06

申请号：US17555316

申请日：2021-12-17

申请人： Baidu USA, LLC

发明人： Shulong Tan ,  Weijie Zhao ,  Ping Li

IPC分类号： G06F16/2457 ,  G06F16/901

CPC分类号： G06F16/24578 ,  G06F16/9024

摘要： Presented are systems and methods that construct BipartitE Graph INdices (BEGIN) embodiments for fast neural ranking. BEGIN embodiments comprise two types of nodes: sampled queries and base or searching objects. In one or more embodiments, edges connecting these nodes are constructed by using a neural network ranking measure. These embodiments extend traditional search-on-graph methods and lend themselves to fast neural ranking. Experimental results demonstrate the effectiveness and efficiency of such embodiments.

公开(公告)号：US12050646B2

公开(公告)日：2024-07-30

申请号：US17408146

申请日：2021-08-20

申请人： Baidu USA, LLC

发明人： Shulong Tan ,  Zhaozhuo Xu ,  Weijie Zhao ,  Zhixin Zhou ,  Ping Li

IPC分类号： G06F16/901 ,  G06F16/22

CPC分类号： G06F16/9024 ,  G06F16/2272

摘要： Incremental proximity graph maintenance (IPGM) systems and methods for online ANN search support both online vertex deletion and insertion of vertices on proximity graphs. In various embodiments, updating a proximity graph comprises receiving a workload that represents a set of vertices in the proximity graph, each vertex being associated with a type of operation such as a query, insertion, or deletion. For a query or an insertion, a search may be executed on the graph to obtain a set of top-K vertices for each vertex. In the case of a deletion, a vertex may be deleted from the proximity graph, and a local or global reconnection update method may be used to reconstruct at least a portion of the proximity graph.

公开(公告)号：US11914669B2

公开(公告)日：2024-02-27

申请号：US17095548

申请日：2020-11-11

申请人： Baidu USA, LLC

发明人： Weijie Zhao ,  Shulong Tan ,  Ping Li

IPC分类号： G06F17/10 ,  G06F9/30 ,  G06F9/38 ,  G06F9/48 ,  G06F18/2323 ,  G06F18/2413

CPC分类号： G06F17/10 ,  G06F9/3009 ,  G06F9/3887 ,  G06F9/4881 ,  G06F18/2323 ,  G06F18/24147

摘要： Approximate nearest neighbor (ANN) searching is a fundamental problem in computer science with numerous applications in area such as machine learning and data mining. For typical graph-based ANN methods, the searching method is executed iteratively, and the execution dependency prohibits graphics processor unit (GPU)/GPU-type processor adaptations. Presented herein are embodiments of a novel framework that decouples the searching on graph methodology into stages, in order to parallel the performance-crucial distance computation. Furthermore, in one or more embodiments, to obtain better parallelism on GPU-type components, also disclosed are novel ANN-specific optimization methods that eliminate dynamic memory allocations and trade computations for less memory consumption. Embodiments were empirically compared against other methods, and the results confirm the effectiveness.

公开(公告)号：US12056189B2

公开(公告)日：2024-08-06

申请号：US17676066

申请日：2022-02-18

申请人： Baidu USA, LLC

发明人： Shulong Tan ,  Zhaozhuo Xu ,  Weijie Zhao ,  Hongliang Fei ,  Zhixin Zhou ,  Ping Li

IPC分类号： G06F16/901 ,  G06F16/22 ,  G06F17/16

CPC分类号： G06F16/9024 ,  G06F16/2237 ,  G06F17/16

摘要： Efficient inner product search is important for many data ranking services, such as recommendation and Information Retrieval. Efficient retrieval via inner product dramatically influences the performance of such data searching and retrieval systems. To resolve deficiencies of prior approaches, embodiments of a new index graph construction approach, referred to generally as Norm Adjusted Proximity Graph (NAPG), for approximate Maximum Inner Product Search (MIPS) are presented. With adjusting factors estimated on sampled data, NAPG embodiments select more meaningful data points to connect with when constructing a graph-based index for inner product search. Extensive experiments verify that the improved graph-based index pushes the state-of-the-art of inner product search forward greatly, in the trade-off between search efficiency and effectiveness.