公开(公告)号：CN104391908B

公开(公告)日：2019-03-05

申请号：CN201410655506.6

申请日：2014-11-17

Applicant: 南京邮电大学

Inventor： 韩京宇 ,  陈可佳 ,  曾建辉

IPC: G06F16/901

Abstract: 本发明公开了一种图上基于局部敏感哈希的多关键字索引方法，属于图数据(graph data)管理技术领域，该方法是双层索引来支持图上的多关键字查询。若干图根据顶点关键字在n‑gram空间聚类后，根据聚簇结构构建上层的位图和下层的局部敏感哈希表：上层的位图根据关键字包含的粗粒度的n‑gram(n个连续字母构成的字符串)实现图到类簇的映射；下层的每个类簇对应一个局部敏感哈希表，哈希表的桶中包含细粒度的n‑gram对应的候选图。该索引具有如下优势：(1)查询I/O和关键字个数独立，显著减少多关键字查询的I/O次数，加快查询速度；(2)不同粒度的n‑gram相结合，有效避免索引对拼写错误敏感，提高了概率返回期望的结果。

公开(公告)号：CN104391908A

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

申请号：CN201410655506.6

申请日：2014-11-17

Applicant: 南京邮电大学

Inventor： 韩京宇 ,  陈可佳 ,  曾建辉

IPC: G06F17/30

CPC classification number: G06F17/30958

Abstract: 本发明公开了一种图上基于局部敏感哈希的多关键字索引方法，属于图数据(graph data)管理技术领域，该方法是双层索引来支持图上的多关键字查询。若干图根据顶点关键字在n-gram空间聚类后，根据聚簇结构构建上层的位图和下层的局部敏感哈希表：上层的位图根据关键字包含的粗粒度的n-gram(n个连续字母构成的字符串)实现图到类簇的映射；下层的每个类簇对应一个局部敏感哈希表，哈希表的桶中包含细粒度的n-gram对应的候选图。该索引具有如下优势：(1)查询I/O和关键字个数独立，显著减少多关键字查询的I/O次数，加快查询速度；(2)不同粒度的n-gram相结合，有效避免索引对拼写错误敏感，提高了概率返回期望的结果。