• 北大核心期刊(《中文核心期刊要目总览》2017版)
  • 中国科技核心期刊(中国科技论文统计源期刊)
  • JST 日本科学技术振兴机构数据库(日)收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

结合否定关键词的空间关键词查询

金海 郝晓丽 牛保宁

金海, 郝晓丽, 牛保宁. 结合否定关键词的空间关键词查询[J]. 微电子学与计算机, 2021, 38(9): 54-60.
引用本文: 金海, 郝晓丽, 牛保宁. 结合否定关键词的空间关键词查询[J]. 微电子学与计算机, 2021, 38(9): 54-60.
JIN Hai, HAO Xiaoli, NIU Baoning. Combination of negative keywords spatial keyword query[J]. Microelectronics & Computer, 2021, 38(9): 54-60.
Citation: JIN Hai, HAO Xiaoli, NIU Baoning. Combination of negative keywords spatial keyword query[J]. Microelectronics & Computer, 2021, 38(9): 54-60.

结合否定关键词的空间关键词查询

基金项目: 

山西省应用基础研究项目 201901D111100

山西省重点研发计划 201903D121132

详细信息
    作者简介:

    金海  男,(1996-),硕士研究生.研究方向为空间数据查询

    牛保宁  男,(1964-),博士,教授.研究方向为大数据管理与分析、数据库系统性能管理、区块链数据管理

    通讯作者:

    郝晓丽(通讯作者)  女,(1973-),博士,副教授.研究方向为视频图像处理、情感计算、数据挖掘等.E-mail: 951001341@qq.com

  • 中图分类号: TP311

Combination of negative keywords spatial keyword query

  • 摘要: 面向个性化约束的空间关键词查询是数据库查询领域的热点问题,其中快速性和匹配性是衡量此类查询优劣的核心问题.传统空间关键词范围查询无法匹配除地理位置和关键词信息以外的带有个性化约束条件下的查询,且大多数二维空间下的索引结构的构建更新速度和查询效率较低.针对上述问题,提出了一种带否定关键词约束(即用户不喜欢的关键词)的查询模式.采用Geohash字符串表示兴趣点对象,对字符串排序后构建B+树作为二叉树的叶节点,通过二叉树过滤带否定关键词的对象,构建了基于Geohash的混合索引结构BGIB-Tree.在此基础上,依靠Geohash编码的递归性,设计了前缀匹配搜索算法.以区域编码和对象编码前缀匹配为剪枝策略,快速找到满足空间约束的兴趣点,最后在倒排索引中双向搜索即可完成查询.通过与IR-Tree和BIR-Tree对比,在真实数据集上对BGIB-Tree的构建时间与相关参数对查询算法的影响做出验证,实验证明结果表明在索引构建时间上减少30%,算法查询效率提高29%.
  • 图  1  结合否定关键词的空间文本查询框架

    图  2  预处理数据的例子

    图  3  GB-Tree索引结构

    图  4  BGIB索引结构

    图  5  否定关键词约束对匹配性的影响

    图  6  索引构建性能对比

    图  7  查询框架的可扩展性

    图  8  否定关键词数量对查询时间的影响

    图  9  查询范围对查询时间的影响

    算法1 前缀匹配搜索算法
    Input: BGIB-Tree,查询范围R,包括查询的位置点Ql和查询距离约束Qd;需要的关键词Q.Kn;不需要的关键词Q.Kh.
    Output: 一组满足查询条件的对象集合C.
    Begin
    1 root = BGIB-Tree;
    2 cur = root;
    3 While cur≠leaf do;
    4   If Q.Kh⊇cur.否定关键词then;
    5     cur = cur.rightChild;
    6   Else cur = cur.leftChild;
    7 计算Ql及周围八区域编码为p位精度Geohash字符串;
    8 For遍历cur子树;
    9   找到最左边节点;
    10   Whilecur.next!= null do;
    11     If当前区域编码=cur前p位编码then;
    12       获取节点Timestamp;
    13       查询倒排索引取交集获得key值;
    14       Ifkey兴趣点满足距离约束;
    15       加入集合C;
    16     ReturnC;
    End
    下载: 导出CSV
    算法2 否定关键词快速剪枝
    Input: BGIB-Tree,否定关键词Q.Kh.
    Output: GIB-Tree根节点
    Begin
    1 root = BGIB-Tree;
    2 If root == null; Return null;
    3 Else if root!= null & & Q.Kh⊇ root.否定关键词;
    4 Returnroot;
    5 Else Node leftnode = this.find(Q.Kh, leftChild);
    6     Node rightnode = this.find(Q.Kh, rightChild);
    7 递归查询左右子树;
    End
    下载: 导出CSV

    表  1  数据集基本统计信息

    城市 兴趣点的数量 关键词的数量 平均兴趣点携带关键词数量
    Austin 183 795 371 109 2.019 15
    San Francisco 161 996 305 169 1.883 81
    下载: 导出CSV
  • [1] XU JJ, CHEN J, YIN L H. Multi-objective spatial keyword query with semantics: a distance-owner based approach[J]. Distributedand Parallel Databases, 2020, 38(3): 625-647. DOI:  10.1007/s10619-020-07283-1.
    [2] ZHU L, SONG J Y, YU W R, et al. Reverse spatial visual top-k query[J]. IEEE Access, 2020, 8(8): 21770-21787. DOI:  10.1109/ACCESS.2020.2968982.
    [3] LIU J L, DENG K, SUN H L, et al. Clue-based spatio-textual query[J]. the VLDB Endowment, 2017, 10(5): 529-540. DOI:  10.14778/3055540.3055546.
    [4] MENG X F, LI P, ZHANG X Y. A personalized and approximated spatial keyword query approach[J]. IEEE Access, 2020(8): 44889-44902. DOI:  10.1109/ACCESS.2020.2977996.
    [5] AIZAWA K, MOTOMURA K, KIMURA S, et al. Constant time neighbor finding in quadtrees: An experimental result[C]//2018 3rd International Symposium on Communications, Control and Signal Processing. Saint Julian's, Malta: IEEE, 2008.
    [6] LI Z S, LEE K C K, ZHENG B H, et al. IR-Tree: an efficient index for geographic document search[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(4): 585-599. DOI:  10.1109/TKDE.2010.149.
    [7] 屠川川. 带排斥关键字的空间关键字查询[J]. 微型电脑应用, 2015, 31(4): 19-22. DOI:  10.3969/j.issn.1007-757X.2015.04.006.

    TU C C. Exclusive spatial keyword query[J]. Microcomputer Applications, 2015, 31(4): 19-22. DOI:  10.3969/j.issn.1007-757X.2015.04.006.
    [8] YANG M, MA K, YU X H. An efficient index structure for distributed k-nearest neighbours query processing[J]. Soft Computing, 2020, 24(8): 5539-5550. DOI:  10.1007/s00500-018-3548-4.
    [9] PARK K. A hierarchical binary quadtree index for spatial queries[J]. Wireless Networks, 2019, 25(4): 1913-1929. DOI:  10.1007/s11276-018-1661-z.
  • 加载中
图(9) / 表(3)
计量
  • 文章访问数:  35
  • HTML全文浏览量:  20
  • PDF下载量:  3
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-12-01
  • 修回日期:  2021-01-02
  • 刊出日期:  2021-09-05

目录

    /

    返回文章
    返回