Collective Spatial Keyword Query Based on Time-Distance Constrained and Cost Aware

Li Song; Cao Wenqi; Hao Xiaohong; Zhang Liping; Hao Zhongxiao

doi:10.7544/issn1000-1239.202330815

Journal of Computer Research and Development > 2025 > 62(3): 808-819. > DOI: 10.7544/issn1000-1239.202330815 CSTR: 32373.14.issn1000-1239.202330815

Li Song, Cao Wenqi, Hao Xiaohong, Zhang Liping, Hao Zhongxiao. Collective Spatial Keyword Query Based on Time-Distance Constrained and Cost Aware[J]. Journal of Computer Research and Development, 2025, 62(3): 808-819. DOI: 10.7544/issn1000-1239.202330815

Citation:

PDF (1664 KB)

Collective Spatial Keyword Query Based on Time-Distance Constrained and Cost Aware

School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080

Funds: The work was supported by the National Natural Science Foundation of China (62072136), the Key Research and Development Project of Heilongjiang Province (JD2023SJ20), and the National Key Research and Development Program of China (2020YFB1710200).

More Information

Author Bio:
Li Song: born in 1977. PhD, professor. Member of CCF. His main research interests include spatial and spatio-temporal database, data mining, and information data security

Cao Wenqi: born in 1999. Master. Her main research interests include spatial database and data mining

Hao Xiaohong: born in 1969. Master，senior experimentalist master. Her main research interest includes spatial database

Zhang Liping: born in 1976. Master，associate professor. Her main research interests include spatial and spatio-temporal database, and information data security

Hao Zhongxiao: born in 1940. PhD, professor. His main research interests include relational database, null database, acyclic database, active database, and spatial database
Received Date: October 10, 2023
Revised Date: July 01, 2024
Accepted Date: August 08, 2024
Available Online: August 15, 2024

Graphical Abstract

Abstract

Abstract

Collective spatial keyword queries play an important role in the fields such as spatial databases, location services, intelligent recommendations, and group intelligence perception. The existing collective spatial keyword query methods do not consider the problem of requiring time-distance constrained and cost aware, and cannot meet the query needs of most users under time-distance constrained. Existing research results have significant limitations. To make up for the shortcomings of existing methods, collective spatial keyword query based on time-distance constrained and cost aware (called TDCCA-CoSKQ) is proposed. To address the issue of not being able to include both keyword information and time information in existing indexes, the TDCIR-Tree index is proposed, which combines inverted files and time attribute label files. TDCIR-Tree can reduce the cost of query calculation. TDCCA_PP algorithm is proposed to address the issue of subsequent screening of collections that meet query criteria for TDCCA-CoSKQ, including TDCCAPruning1, TDCCAPermutation, and TDCCAPruning2, and it can improve the efficiency of keyword queries. The TDC cost function and its corresponding sorting algorithm are proposed. The TDC cost function is composed of distance cost and time cost, which includes independent variable coefficients representing user preference α and β, and it can increase users’ freedom of choice. The problem of existing cost functions not meeting the collective spatial keyword query based on time-distance constrained and cost aware is effectively solved. Theoretical research and experiments have shown that the proposed method has good efficiency and accuracy.
- collective spatial keyword query,
- time-distance constrained,
- cost aware,
- inverted files,
- time attribute label files

FullText(HTML)

References (23)

References

[1]	Chen Gang, Zhao Jingwen, Gao Yunjun, et al. Time-aware Boolean spatial keyword queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(11): 2601−2614 doi: 10.1109/TKDE.2017.2742956
[2]	Polychronis V, Michael V, Antonio C, et al. GPU-based algorithms for processing the K nearest-neighbor query on spatial data using partitioning and concurrent kernel execution[J]. International Journal of Parallel Programming, 2023, 51(6): 275−308 doi: 10.1007/s10766-023-00755-8
[3]	Zhong Ying, Li Jianmin, Zhu Shunzhi. Continuous spatial keyword search with query result diversifications[J]. World Wide Web, 2023, 26(4): 1−14
[4]	潘晓,于启迪,马昂,等. 支持OR语义的高效受限Top-k空间关键字查询技术[J]. 软件学报,2020,31(10):3197−3215 Pan Xiao, Yu Qidi, Ma Ang, et al. Efficient algorithm of Top-k spatial keyword search with OR semantics[J]. Journal of Software, 2020, 31(10): 3197−3215 (in Chinese)
[5]	刘俊岭,刘柏何,邹鑫源,等. 面向空间兴趣区域的路线查询[J]. 计算机研究与发展,2022,59(11):2569−2580 Liu Junling, Liu Baihe, Zou Xinyuan, et al. Spatial region of interests oriented route query[J]. Journal of Computer Research and Development, 2022, 59(11): 2569−2580 (in Chinese)
[6]	Zhu Huaijie, Liu Wei, Yin Jian, et al. Towards keyword-based geo-social group query services[J]. IEEE Transactions on Services Computing, 2023, 16(1): 670−683
[7]	Chang Xueqin, Luo Chengyang, Yu Hanlin, et al. Answering non-answer questions on reverse Top-k geo-social keyword queries[J]. Journal of Computer Science and Technology, 2022, 37(6): 1320−1336 doi: 10.1007/s11390-022-2414-0
[8]	Jia Lianyin, Tang Haotian, Zhao Bingxin, et al. An efficient association rule mining-based spatial keyword index[J]. International Journal of Data Warehousing and Mining, 2023, 19(2): 1−19
[9]	Tong Qiuyun, Miao Yinbin, Li Hongwei, et al. Privacy-preserving ranked spatial keyword query in mobile cloud-assisted fog computing[J]. IEEE Transactions on Mobile Computing, 2023, 22(6): 3604−3618 doi: 10.1109/TMC.2021.3134711
[10]	Zhang Liping, Li Jing, Li Song. Research on time-aware group query method with exclusion keywords[J]. ISPRS International Journal of Geo-Information, 2023, 12(10): 1−20
[11]	Zhang Liping, Li Jing, Li Song. Research on approximate spatial keyword group queries based on differential privacy and exclusion preferences in road networks[J]. ISPRS International Journal of Geo-Information, 2023, 12(12): 480−503 doi: 10.3390/ijgi12120480
[12]	Cao Xin, Cong Gao, Christian S, et al. Collective spatial keyword querying[C]//Proc of the 11th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2011: 373−384
[13]	He Peijun, Xu Hao, Zhao Xiang, et al. Scalable collective spatial keyword query[C]//Proc of the 13th IEEE Int Conf on Data Engineering Workshops. New York: IEEE, 2015: 182−189
[14]	Su Danni,Zhou Xu,Yang Zhibang,et al. Top-k collective spatial keyword queries[J]. IEEE Access,2019,7:180779−180792
[15]	Yang Zhibang,Zeng Yifu,Du Jiayi,et al. Efficient index-independent approaches for the collective spatial keyword queries[J]. Neurocomputing,2021,439:96−105
[16]	Chan H, Long Cheng, Wong R. Inherent-cost aware collective spatial keyword queries[C]//Proc of the 15th Int Symp on Spatial and Temporal Databases. Berlin: Springer, 2017: 357−375
[17]	Zhang Pengfei,Lin Huaizhong,Yao Bin,et al. Level-aware collective spatial keyword queries[J]. Information Sciences,2017,378:194−214
[18]	Chan H, Long Cheng, Wong R. On generalizing collective spatial keyword queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(9): 1712−1726 doi: 10.1109/TKDE.2018.2800746
[19]	Jin Xiongnan, Shin S, Jo E, et al. Collective keyword query on a spatial knowledge base[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 31(11): 2051−2062 doi: 10.1109/TKDE.2018.2873376
[20]	Chan H, Liu Shengxin, Long Cheng, et al. Cost-aware and distance-constrained collective spatial keyword query[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(2): 1324−1336
[21]	Chen Zijun, Zhao Tingting, Liu Wenyuan. Time-aware collective spatial keyword query[J]. Computer Science and Information Systems, 2021, 18(3): 1077−1100 doi: 10.2298/CSIS200131034C
[22]	Feng Zhe,Jin Changlong,Kim H,et al. Time-aware approximate collective keyword search in traffic networks[J]. Knowledge-Based Systems,2021,229:107367
[23]	Wu D, Yiu M Y, Cong G, et al. Joint top-k spatial keyword query processing[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(10): 1889−1903 doi: 10.1109/TKDE.2011.172

[1]	Du Yuyue, Sun Ya’nan, Liu Wei. Petri Nets Based Recognition of Model Deviation Domains and Model Repair[J]. Journal of Computer Research and Development, 2016, 53(8): 1766-1780. DOI: 10.7544/issn1000-1239.2016.20160099
[2]	Zhu Jun, Guo Changguo, Wu Quanyuan. A Web Services Interaction Behavior-Environment Model Based on Generalized Stochastic Petri Nets[J]. Journal of Computer Research and Development, 2012, 49(11): 2450-2463.
[3]	Sun Cong, Tang Liyong, Chen Zhong, Ma Jianfeng. Secure Information Flow in Java by Optimized Reachability Analysis of Weighted Pushdown System[J]. Journal of Computer Research and Development, 2012, 49(5): 901-912.
[4]	Zhou Hang, Huang Zhiqiu, Zhu Yi, Xia Liang, Liu Linyuan. Real-Time Systems Contact Checking and Resolution Based on Time Petri Net[J]. Journal of Computer Research and Development, 2012, 49(2): 413-420.
[5]	Men Peng and Duan Zhenhua. Extension of Model Checking Tool of Colored Petri Nets and Its Applications in Web Service Composition[J]. Journal of Computer Research and Development, 2009, 46(8): 1294-1303.
[6]	Zhao Mingfeng, Song Wen, Yang Yixian. Confusion Detection Based on Petri-Net[J]. Journal of Computer Research and Development, 2008, 45(10): 1631-1637.
[7]	Cui Huanqing and Wu Zhehui. Structural Properties of Parallel Program's Petri Net Model[J]. Journal of Computer Research and Development, 2007, 44(12): 2130-2135.
[8]	Tang Da, Li Ye. Model Analysis of Supply Chain System Based on Color Stochastic Petri Net[J]. Journal of Computer Research and Development, 2007, 44(10): 1782-1789.
[9]	Lao Songyang, Huang Guanglian, Alan F. Smeaton, Gareth J. F. Jones, Hyowon Lee. A Query Description Model of Soccer Video Based on BSU Composite Petri-Net[J]. Journal of Computer Research and Development, 2006, 43(1): 159-168.
[10]	Li Botao and Luo Junzhou. Modeling and Analysis of Non-Repudiation Protocols by Using Petri Nets[J]. Journal of Computer Research and Development, 2005, 42(9): 1571-1577.

Cited By

Cited by

Periodical cited type(22)

1.	黄蔚亮，李锦煊，余志文，蔡亚永，刘元. 确定性网络：架构、关键技术和应用. 重庆邮电大学学报(自然科学版). 2025(01): 1-16 .
2.	姜旭艳，全巍，付文文，张小亮，孙志刚. OpenPlanner：一个开源的时间敏感网络流量规划器. 计算机研究与发展. 2025(05): 1307-1329 . 本站查看
3.	齐玉玲，黄涛，张军贤，贾焱鑫，徐龙，熊伟，朱海龙，彭开来. 基于时间敏感网络的列车通信网络研究及应用. 城市轨道交通研究. 2024(05): 184-189 .
4.	何倩，郭雅楠，赵宝康，潘琪，王勇. 无等待与时隙映射复用结合的时间触发流调度方法. 通信学报. 2024(08): 192-204 .
5.	郭若彤，许方敏，张恒升，赵成林. 基于循环排队转发的时间触发流量路由与调度优化方法. 微电子学与计算机. 2024(10): 55-63 .
6.	薛强，吴梦，杨世标，屠礼彪，李伟，廖江. 嵌入式人工智能技术在IP网络的创新应用. 邮电设计技术. 2024(10): 66-72 .
7.	张浩，郭偶凡，周飞飞，马涛，何迎利，姚苏滨. 基于分段帧复制和消除的时间敏感网络动态冗余机制研究. 计算机科学. 2024(S2): 750-756 .
8.	罗峰，周杰，王子通，张晓先，孙志鹏. 基于多域冗余的车载时间敏感网络时间同步增强方法. 系统工程与电子技术. 2024(12): 4259-4268 .
9.	王雪荣，唐政治，李银川，齐美玉，朱建波，张亮. 基于优化决策树的时延敏感流智能感知调度. 电信科学. 2023(04): 120-132 .
10.	陆以勤，谢文静，王海瀚，陈卓星，程喆，潘伟锵，覃健诚. 面向时间敏感网络的安全感知调度方法. 华南理工大学学报(自然科学版). 2023(05): 1-12 .
11.	朱渊，胡馨予，吴思远，黄蓉. 基于OMNeT++的5G-TSN调度算法综述. 西安邮电大学学报. 2023(01): 9-18 .
12.	王家兴，杨思锦，庄雷，宋玉，阳鑫宇. 时间敏感网络中多目标在线混合流量调度算法. 计算机科学. 2023(07): 286-292 .
13.	李维，梁巍，周策. 基于ACO算法的SDN网络流量调度优化研究. 自动化与仪器仪表. 2023(07): 42-46 .
14.	吴昭祥，李文凯，袁亚洲，刘志新. 时间敏感网络中基于抢占式通道模型的资源调度算法研究. 移动通信. 2023(08): 67-73+97 .
15.	刘美鹭，刘留，王凯，韩紫杰. 真空管高速飞行列车通信业务建模. 移动通信. 2023(08): 98-106 .
16.	彭紫梅，寿国础，郭梦杰，刘雅琼，胡怡红. 时间敏感网络中的冗余机制研究综述. 电信科学. 2023(08): 29-42 .
17.	胡文学，孙雷，王健全，朱渊，毕紫航. 基于网络演算的时间敏感网络时延上界分析模型研究. 自动化学报. 2023(11): 2297-2310 .
18.	王新蕾，周敏，张涛. 时间敏感网络流量调度算法研究综述. 电讯技术. 2023(11): 1830-1838 .
19.	段晓东，刘鹏，陆璐，孙滔，李志强. 确定性网络技术综述. 电信科学. 2023(11): 1-12 .
20.	陆以勤，熊欣，王猛，覃健诚，潘伟锵. TSN中基于链路负载均衡的AVB流量带宽分配方法. 华南理工大学学报(自然科学版). 2023(11): 1-9 .
21.	周阳，陈鸿龙，张雷. 时间敏感网络中的动态路由与调度联合优化算法. 物联网学报. 2023(04): 52-62 .
22.	裴金川，胡宇翔，田乐，胡涛，李子勇. 联合路由规划的时间敏感网络流量调度方法. 通信学报. 2022(12): 54-65 .