距离-关键字相似度约束的双色反k近邻查询方法

doi:10.11772/j.issn.1001-9081.2020091453

计算机应用 ›› 2021, Vol. 41 ›› Issue (6): 1686-1693.DOI: 10.11772/j.issn.1001-9081.2020091453

所属专题：数据科学与技术

距离-关键字相似度约束的双色反k近邻查询方法

张豪, 朱睿, 宋栿尧, 方鹏, 夏秀峰

沈阳航空航天大学计算机学院, 沈阳110136

收稿日期:2020-09-18 修回日期:2020-12-09 出版日期:2021-06-10 发布日期:2020-12-18
通讯作者: 张豪
作者简介:张豪(1996-),男,河北石家庄人,硕士研究生,主要研究方向:大数据;朱睿(1982-),男,辽宁沈阳人,副教授,博士,CCF会员,主要研究方向:大数据;宋栿尧(1995-),男,辽宁鞍山人,硕士研究生,主要研究方向:大数据;方鹏(1994-),男,甘肃平凉人,硕士研究生,主要研究方向:新媒体大数据;夏秀峰(1964-),男,山东胶南人,教授,博士,主要研究方向:数据库、数据仓库、数据挖掘。
基金资助:
国家自然科学基金资助项目（61702344）。

Bichromatic reverse k nearest neighbor query method based on distance-keyword similarity constraint

ZHANG Hao, ZHU Rui, SONG Fuyao, FANG Peng, XIA Xiufeng

College of Computer Science, Shenyang Aerospace University, Shenyang Liaoning 110136, China

Received:2020-09-18 Revised:2020-12-09 Online:2021-06-10 Published:2020-12-18
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61702344).

摘要/Abstract

摘要： 针对空间关键字双色反k近邻查询返回结果质量较低的问题，提出了基于距离-关键字相似度约束的双色反k近邻查询方法。首先，通过设置一个阈值将查询结果中质量较低的用户给过滤掉，从而避免了查询结果中出现空间距离相对较远的用户，保证了查询结果质量；然后，为支持该查询，提出了一种关键字多分辨率网格矩形树（KMG-Tree）索引来管理数据；最后，提出了基于Six-region算法的Six-region-optimize算法来提高查询处理效率。Six-region-optimize算法的查询效率相较baseline和Six-region算法分别平均提高了约85.71%和23.45%。基于真实时空数据进行实验测试和分析，实验结果验证了Six-region-optimize算法的有效性和高效性。

关键词: 关键字, 双色反k近邻查询, 空间距离, 相似度约束, 查询效率

Abstract: In order to solve the problem of low quality of results returned by spatial keyword bichromatic reverse k nearest neighbor query, a bichromatic reverse k nearest neighbor query method based on distance-keyword similarity constraint was proposed. Firstly, a threshold was set to filter out the low-quality users in the query results, so that the existence of users with relatively long spatial distance in the query results was avoided and the quality of the query results was ensured. Then, in order to support this query, an index of Keyword Multiresolution Grid rectangle-tree (KMG-tree) was proposed to manage the data. Finally, the Six-region-optimize algorithm based on Six-region algorithm was proposed to improve the query processing efficiency. The query efficiency of the Six-region-optimize algorithm was about 85.71% and 23.45% on average higher than those of the baseline and Six-region algorithms respectively. Experimental test and analysis were carried out based on real spatio-temporal data. The experimental results verify the effectiveness and high efficiency of the Six-region-optimize algorithm.

Key words: keyword, bichromatic reverse k nearest neighbor query, spatial distance, similarity constraint, query efficiency

中图分类号:

TP311

张豪, 朱睿, 宋栿尧, 方鹏, 夏秀峰. 距离-关键字相似度约束的双色反k近邻查询方法[J]. 计算机应用, 2021, 41(6): 1686-1693.

ZHANG Hao, ZHU Rui, SONG Fuyao, FANG Peng, XIA Xiufeng. Bichromatic reverse k nearest neighbor query method based on distance-keyword similarity constraint[J]. Journal of Computer Applications, 2021, 41(6): 1686-1693.

参考文献

[1] LU J,LU Y,CONG G. Reverse spatial and textual k nearest neighbor search[C]//Proceedings of the 2011 ACM IGMOD International Conference on Management of Data. New York:ACM,2011:349-360.
[2] ZHAO P,FANG H,SHENG V S,et al. Monochromatic and bichromatic ranked reverse boolean spatial keyword nearest neighbors search[J]. World Wide Web,2017,20(1):39-59.
[3] XIA S,ZHANG Z,LI W,et al. GBNRS:a novel rough set algorithm for fast adaptive attribute reduction in classification[J]. IEEE Transactions on Knowledge and Data Engineering, 2020(Early Access):1-1.
[4] XIA S,PENG D,MENG D,et al. A fast adaptive k-means with no bounds[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2020(Early Access):1-1.
[5] XIA S,WANG G,CHEN Z,et al. Complete random forest based class noise filtering learning for improving the generalizability of classifiers[J]. IEEE Transactions on Knowledge and Data Engineering,2019,31(11):2063-2078.
[6] STANOI I, AGRAWAL D, ABBADI A E. Reverse nearest neighbor queries for dynamic databases[C]//Proceedings of the 2000 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. New York:ACM,2000:44-53.
[7] TAO Y,PAPADIAS D,LIAN X. Reverse kNN search in arbitrary dimensionality[C]//Proceedings of the 2004 30th International Conference on Very Large Data Base. Amsterdam:Elsevier, 2004:744-755.
[8] TAO Y,PAPADIAS D,LIAN X,et al. Multidimensional reverse kNN search[J]. The VLDB Journal,2007,16(3):293-316.
[9] CHEEMA M A,LIN X,ZHANG Y,et al. Lazy updates:an efficient technique to continuously monitoring reverse kNN[J]. Proceedings of the VLDB Endowment,2009,2(1):1138-1149.
[10] CHEEMA M A,SHEN Z,LIN X,et al. A unified framework for efficiently processing ranking related queries[C]//Proceedings of the 2014 17th International Conference on Extending Database Technology. Berlin:Springer,2014:427-438.
[11] CHEEMA M A,ZHANG W,LIN X,et al. Efficiently processing snapshot and continuous reverse k nearest neighbors queries[J]. The VLDB Journal,2012,21(5):703-728.
[12] LEE K C K,ZHENG B,LEE W C. Ranked reverse nearest neighbor search[J]. IEEE Transactions on Knowledge and Data Engineering. 2008,20(7):894-910.
[13] YIU M L,PAPADIAS D,MAMOUIS N,et al. Reverse nearest neighbors in large graphs[J]. IEEE Transactions on Knowledge and Data Engineering,2006,18(4):540-553.
[14] 李佳佳, 李雨现, 夏秀峰, 等. 面向时间依赖路网的连续k近邻查询[J]. 计算机科学与探索, 2019, 13(5):788-799.(LI J J,LI Y X,XIA X F,et al. Continuous k-neighbor query for time dependent road network[J]. Journal of Frontiers of Computer Science and Technology,2019,13(5):788-799.)
[15] HIDAYAT A, YANG S, CHEEMA M A, et al. Reverse approximate nearest neighbor queries[J]. IEEE Transactions on Knowledge and Data Engineering,2018,30(2):339-352.

距离-关键字相似度约束的双色反k近邻查询方法

Bichromatic reverse k nearest neighbor query method based on distance-keyword similarity constraint

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

[1]	马兰, 王京杰, 陈焕. 基于内容挖掘的广域信息管理系统业务数据安全[J]. 计算机应用, 2019, 39(2): 488-493.
[2]	杨宏宇, 王玥. 云存储环境下的多关键字密文搜索方法[J]. 计算机应用, 2018, 38(2): 343-347.
[3]	原豪杰, 孙桂玲, 许依, 郑博文. 基于补集零空间与最近空间距离的人脸识别[J]. 计算机应用, 2017, 37(5): 1475-1480.
[4]	李阳, 李青, 张霞. 基于离散序列报文的协议格式特征自动提取算法[J]. 计算机应用, 2017, 37(4): 954-959.
[5]	姚全珠余训滨. 基于最小相关实体子树的XML关键字查询算法[J]. 计算机应用, 2012, 32(04): 1090-1093.
[6]	严华云关佶红. 基于Bloom滤波器的对等网多关键字检索[J]. 计算机应用, 2010, 30(9): 2335-2338.
[7]	郑弘晖郭红. 基于有效最低公共祖先的XML关键字查询算法[J]. 计算机应用, 2010, 30(3): 825-830.
[8]	曾婧娜余丹李先军马世龙. 基于语义的组件组合方法研究[J]. 计算机应用, 2010, 30(2): 406-410.
[9]	黎军熊海灵. 综合文档语义与用户查询语义的XML关键字检索[J]. 计算机应用, 2010, 30(11): 2945-2948.
[10]	祝青阳王东. 利用关系表构建XML文档解析的树模型[J]. 计算机应用, 2009, 29(06): 1719-1721.
[11]	梁银4 张虹. 一种多路空间距离连接查询处理方法[J]. 计算机应用, 2008, 28(1): 155-158.
[12]	向浩翔宁洪 . WMMS中查询检索部件的设计与实现[J]. 计算机应用, 2006, 26(11): 2682-2684.
[13]	宋江春，沈钧毅，宋擒豹. 一个基于关联规则的多层文档聚类算法[J]. 计算机应用, 2005, 25(07): 1570-1572.