Loading...
ISSN 1000-1239 CN 11-1777/TP

Table of Content

01 February 2022, Volume 59 Issue 2
Spatial Data Intelligence: Concept, Technology and Challenges
Song Xuan, Gao Yunjun, Li Yong, Guan Qingfeng, Meng Xiaofeng
2022, 59(2):  255-263.  doi:10.7544/issn1000-1239.20220108
Asbtract ( 890 )   HTML ( 23)   PDF (690KB) ( 615 )  
Related Articles | Metrics
As the volume of spatial data continues to grow, the value contained in spatial data is enormous. Traditional technologies of data sensing, data storage, data processing, and data analysis have been unable to fully extract the value of massive spatial data. Therefore, spatial data intelligence, a multidisciplinary field focusing on the research and application of massive spatial data, is playing an increasingly important role. This paper introduces the concept of spatial data intelligence, the technical challenges faced in the field of spatial data intelligence and the key technologies of spatial data intelligence. Typical application scenarios of spatial data intelligence in social life are also introduced. Finally, the future trends of the research of spatial data intelligence are discussed in the paper.
Spatial Occupancy-Based Dominant Co-Location Patterns Mining
Fang Yuan, Wang Lizhen, Wang Xiaoxuan, Yang Peizhong
2022, 59(2):  264-281.  doi:10.7544/issn1000-1239.20210913
Asbtract ( 214 )   HTML ( 3)   PDF (4254KB) ( 179 )  
Related Articles | Metrics
Traditional spatial co-location pattern mining aims to discover the subset of spatial feature set whose instances are prevalently located together in geographic neighborhoods. Most previous studies take the prevalence of patterns as an interestingness measure. However, It may well be that users are not only interested in identifying the prevalence of a feature set, but also its completeness, namely the portion of co-location instances that a pattern occupies in their neighborhood. Combining the prevalence and completeness of co-location patterns, we can provide users with a set of higher quality co-location patterns called dominant spatial co-location patterns (DSCPs). In this paper, we introduce an occupancy measure into the spatial co-location pattern mining task to measure the completeness of co-location patterns. Then we formulate the problem of DSCPs mining by considering both the completeness and prevalence. Thirdly, we present a basic algorithm for discovering DSCPs. In order to reduce the high computational cost, a series of pruning strategies are given to improve the algorithm efficiency. Finally, the experiments are conducted both on synthetic and real-world data sets, and the efficiency and effectiveness of the proposed algorithms are evaluated. The running time on synthetic data sets shows our pruning strategies are efficient. The mining results in two real-world applications demonstrate that DSCPs are reasonable and acceptable.
Spatial-Temporal Graph Neural Network for Traffic Flow Prediction Based on Information Enhanced Transmission
Ni Qingjian, Peng Wenqiang, Zhang Zhizheng, Zhai Yuqing
2022, 59(2):  282-293.  doi:10.7544/issn1000-1239.20210901
Asbtract ( 425 )   HTML ( 7)   PDF (1313KB) ( 389 )  
Related Articles | Metrics
Traffic problems not only affect people’s travel, but also bring environmental pollution and safety problems. Accurate traffic flow prediction is the key to build an intelligent transportation system to prevent and alleviate traffic problems. Most of the current methods do not take into account the dynamic spatial-temporal correlation, periodicity, linear and nonlinear characteristics of traffic flow. In this paper, an information enhanced transmission spatial-temporal graph neural network is proposed, which mainly contains a multi-feature attention module, an information enhanced transmission module, a temporal attention module, and a linear-nonlinear fusion module. The multi-feature attention module captures the intrinsic connection between multiple traffic features and takes into account the periodicity of traffic flow. The information enhanced transmission module makes full use of the information in the traffic network, enhancing the information transmission capability of the traffic network and mining the complex dynamic spatial dependencies. The temporal attention module adaptively extracts the dependencies between different time intervals. Furthermore, the linear-nonlinear fusion module considers both linear and nonlinear data features. A large number of comparative experiments are conducted on real-world datasets, and the experimental results demonstrate that the method proposed in this paper has more obvious advantages in terms of traffic flow prediction performance compared with the state-of-the-art baselines.
Location-Aware Joint Influence Maximizaton in Geo-Social Networks Using Multi-Target Combinational Optimization
Jin Pengfei, Chang Xueqin, Fang Ziquan, Li Miao
2022, 59(2):  294-309.  doi:10.7544/issn1000-1239.20210891
Asbtract ( 165 )   HTML ( 3)   PDF (4256KB) ( 155 )  
Related Articles | Metrics
Influence maximization aims to identify a number of influential nodes (seeds) in social networks, in order to trigger a largest information dissemination. Most of the existing studies equal the importance of users in social networks. In location-based advertising, the targets for promotion are spatial objects with geographical tags. Due to users’ mobility limitations in the world, the spatial object can only attract potential users in its local range. Hence, to fully improve the market potential, merchants often have multiple targets at the same time (e.g., managers of chain stores prefer to jointly promote several chains), where both the content of promotion targets as well as the seeds will actually affect the marketing performance. In view of this, this paper focuses on the joint optimization towards both merchant locations and seed selection policies, to best facilitate the location-aware joint influence promotion (LA-JIP) in geo-social networks. We first analyze the complexity of this problem, claim its difference from the conventional influence maximization problem. To efficiently and accurately solve this problem, we extend the reverse influence sampling (reverse influence sampling, RIS) techniques by considering users’ weights, and derive tightened upper and lower bounds to evaluate the solution with theoretical guarantees. Based on the bounds, we further develop an iterative algorithm to find the suboptimal result optimized by several rounds with high confidence. Finally, extensive experiments on real datasets demonstrate the effectiveness of LA-JIP in location-aware influence promotion, and also validate the good performance of the proposed methods.
A Spatial Crowdsourcing Task Assignment Approach Based on Spatio-Temporal Location Prediction
Xu Tiancheng, Qiao Shaojie, Wu Jun, Han Nan, Yue Kun, Yi Yugen, Huang Faliang, Yuan Chang’an
2022, 59(2):  310-328.  doi:10.7544/issn1000-1239.20210875
Asbtract ( 268 )   HTML ( 8)   PDF (2947KB) ( 200 )  
Related Articles | Metrics
Space crowdsourcing technology has a varying type of application scenarios in the real physical world, which has been widely concerned by academia and industry. Task assignment is one of the important research issues in space crowdsourcing, that is, distributing workers to appropriate tasks. However, most existing task assignment methods assume that the location and time of crowdsourcing workers and space tasks are known, ignoring the dynamic change of crowdsourcing workers and space tasks in real crowdsourcing platforms. Due to the requirement of strong timeliness in space crowdsourcing platforms, in this situation, the designed assignment method can only get the local optimal results. A new problem of task assignment with maximum value and the minimum cost is proposed, which aims to distribute current and future workers and obtains the maximum assignment value by using the minimum traveling cost. To handle this problem, a trajectory based model is proposed to predict the distribution of tasks. In addition, a kernel density estimation based model is proposed to predict the distribution of workers. A task allocation algorithm based on location prediction is designed to calculate the relative optimal assignment strategy between crowdsourcing workers and spatial tasks. The proposed location prediction method uses graph convolution neural network and ConvLSTM model to predict, which is more accurate and stable than the traditional grid-based location distribution prediction approaches. The heuristic assignment algorithm based on location prediction can complete task allocation in a linear time by combining the predicted location information, which is consistent with the strong timeliness of the space crowdsourcing platform. Extensive experiments are conducted on real datasets to prove the effectiveness of the proposed methods. Compared with the grid-based prediction method, the accuracy of task/worker location prediction is increased by 15.7% and 18.8%, respectively.
Dynamic Ride-Hailing Route Planning Based on Deep Reinforcement Learning
Zheng Bolong, Ming Lingfeng, Hu Qi, Fang Yixiang, Zheng Kai, Li Guohui
2022, 59(2):  329-341.  doi:10.7544/issn1000-1239.20210905
Asbtract ( 721 )   HTML ( 17)   PDF (2081KB) ( 584 )  
Related Articles | Metrics
With the rapid development of the mobile Internet, many online ride-hailing platforms that use mobile apps to request taxis have emerged. Such online ride-hailing platforms have reduced significantly the amounts of the time that taxis are idle and that passengers spend on waiting, and improved traffic efficiency. As a key component, the taxi route planning problem aims at dispatching idle taxis to serve potential requests and improving the operating efficiency, which has received extensive attention in recent years. Existing studies mainly adopt value-based deep reinforcement learning methods such as DQN to solve this problem. However, due to the limitations of value-based methods, existing methods cannot be applied to high-dimensional or continuous action spaces. Therefore, an actor-critic with action sampling policy, called AS-AC, is proposed to learn an optimal fleet management strategy, which can perceive the distribution of supply and demand in the road network, and determine the final dispatch location according to the degree of mismatch between supply and demand. Extensive experiments on New York and Haikou taxi datasets offer insight into the performance of our model and show that it outperforms the comparison approaches.
Fast and Distributed Map-Matching Based on Contraction Hierarchies
Li Ruiyuan, Zhu Haowen, Wang Rubin, Chen Chao, Zheng Yu
2022, 59(2):  342-361.  doi:10.7544/issn1000-1239.20210904
Asbtract ( 350 )   HTML ( 8)   PDF (3130KB) ( 225 )  
Related Articles | Metrics
Map-Matching is a basic operation for trajectory data mining, which is very useful for many spatial intelligent applications. Hidden Markov model (i.e., HMM)-based map-matching is the most widely-used algorithm for its high accuracy. However, HMM-based map-matching is very time-consuming, so it can hardly be applied to real-time scenarios with massive trajectory data. In this paper a contraction hierarchy-based and distributed map-matching framework, i.e., CHMM, is proposed, which map-matches massive trajectories efficiently. Specifically, we first propose a simple but effective partitioning strategy to solve the issue of unbalanced trajectory data distribution. Then, we propose a contraction hierarchy-based many-to-many shortest path search method, which significantly improves the efficiency of HMM-based map-matching while keeps the results unchanged. Extensive experiments are conducted using real road network data and big trajectory data, verifying the powerful efficiency and scalability of CHMM. CHMM has been deployed to our product, supporting various real urban applications. We publish the core source code and provide an online demo system.
A Shortest Path Query Method over Temporal Graphs
Zhang Tianming, Xu Yiheng, Cai Xinwei, Fan Jing
2022, 59(2):  362-375.  doi:10.7544/issn1000-1239.20210893
Asbtract ( 247 )   HTML ( 2)   PDF (1242KB) ( 151 )  
Related Articles | Metrics
Shortest path query has been extensively studied for decades of years. However, most of existing works focus on shortest path query over general graphs, a paucity of studies aim at temporal graphs, where there are multi-edges between two nodes and each edge is associated with a temporal interval, recording the start time and the end time of an event. Shortest path query over temporal graphs has a plethora of applications in urban traffic route planning, social network analysis, and communication network mining, to name but a few. Traditional shortest path algorithms on general graphs are not suitable for temporal graphs because subpaths of a shortest temporal path are not guaranteed to be the optimal substructures. Hence, in this paper, we propose a Compressed Transformed Graph tree (CTG-tree) based query method, which consists of a preprocessing stage and an online query stage. In the preprocessing stage, we transform the temporal graph into a general graph, propose a lossless compression method to reduce the scale of the transformed graph, use hierarchical partitioning technique to divide the compressed directed graph into subgraphs, and then build a CTG-tree index based on the partitioned subgraphs. The nodes of CTG-tree maintain shortest paths between some vertices in the corresponding subgraphs,save shortest paths between boundaries in the subgraphs of children nodes, and record shortest paths between boundaries of the subgraphs corresponding to the children nodes and those corresponding to the current node. In the online query stage, based on the constructed CTG-tree index, we develop an efficient shortest temporal path query method. Using four real-life temporal graphs, we experimentally demonstrate that our proposed method has the best query performance compared with the state-of-the-art methods.
Cache-Based Shortest Path Query Algorithm for Time-Varying Road Networks
Huang Yang, Zhou Xu, Yang Zhibang, Yu Ting, Zhang Ji, Zeng Yuanyuan, Li Kenli
2022, 59(2):  376-389.  doi:10.7544/issn1000-1239.20210892
Asbtract ( 169 )   HTML ( 2)   PDF (2328KB) ( 124 )  
Related Articles | Metrics
As one of the fundamental operations in graph theory, the shortest path query has been extensively applied to the related applications based on road networks, including GPS navigation and personalized recommendation. In view of the high computational cost and slow query speed faced by the use of servers in the road network to query the shortest path online, the existing solutions usually utilize caching technology to optimize their performance. Considering that the edge weight of the road network has the characteristics of frequent changes, the existing related work failed to effectively realize the rapid update of cached data, then ignored the timeliness of the shortest path in the cache, which led to a decrease in the cache hit ratio. In view of this, we first propose a new cache storage structure that effectively balances the relationship between the overall query speed of the shortest path and the cache data update speed; Secondly, we propose a cache storage strategy that combines path sharing abilities and path diversity to optimize cache revenue and improve cache hit ratio; Finally, we propose a cache-based time-varying shortest path query (CTSPQ) algorithm based on the storage structure to improve the speed of querying the shortest path in the cache. A great deal of experiments on real data sets prove the effectiveness and scalability of the proposed techniques.
Location Privacy Attack Based on Deep Learning
Shen Zhengchen, Zhang Qianli, Zhang Chaofan, Tang Xiangyu, Wang Jilong
2022, 59(2):  390-402.  doi:10.7544/issn1000-1239.20200843
Asbtract ( 329 )   HTML ( 8)   PDF (1436KB) ( 244 )  
Related Articles | Metrics
With the continuous development of location services, location privacy protection has become a hotspot in privacy protection research. At present, a series of location privacy protection schemes have been proposed, most of which are based on spatial disturbance technology. However, the existing research on location privacy protection has two problems: First of all, most of the location privacy protection schemes do not consider the complicated correlation between the trajectory points of a single trajectory when performing spatial disturbances, and they usually underestimate the risk of cracking desensitization trajectories; Secondly, there is a lack of quantitative measurement of the risk of cracking the desensitization trajectory. Although differential privacy has made considerable efforts in this regard, the existence of complex relationships makes the model may not be able to objectively describe the degree of privacy protection. If the cracking risk of data after privacy protection cannot be quantified, a quantitative evaluation index cannot be established for the privacy protection scheme. Therefore, first of all, the location information with the association relationship is used to attack the desensitization trajectory. Specifically, the Markov attack algorithms using simple association relationships and the deep neural network attack algorithms using complex association relationships are designed in this paper. Secondly, the cracking risk of desensitization trajectory is quantified, and a quantitative evaluation scheme is established to evaluate the threat degree of attack algorithm to privacy protection scheme. Finally, these two kinds of attack algorithms are used to attack Geo-Indistinguishability privacy protection scheme, and the attack effect is evaluated. The results show that Geo-Indistinguishability privacy protection scheme can resist the attack of the Markov attack algorithm, but can not resist the attack of deep neural network attack algorithm.
SMT Port Side Channel Defending Method Based on Dynamic Resource Usage Strategy
Yue Xiaomeng, Yang Qiusong, Li Mingshu
2022, 59(2):  403-417.  doi:10.7544/issn1000-1239.20200537
Asbtract ( 90 )   HTML ( 1)   PDF (2042KB) ( 61 )  
Related Articles | Metrics
Simultaneous multi-threading (SMT) technology is one of the important micro-architecture optimization technologies to improve thread-level parallelism. SMT can realize two logical cores on one physical core and improve the overall performance of the processor. However, some timing channel security problems represented by sharing execution ports in SMT environment appeared. A port timing channel attack defending method is proposed based on dynamic resource usage strategy in SMT environment. Dynamic strategy adjustment algorithm is designed for different processing modes of data structure resources, and improved processor port binding and scheduling selection algorithm are adopted to protect the port side channel attack in SMT environment. Defending method used modular design has realized the port conflict matrix, branch filters and dynamic resource editor strategy. Respectively judgment model for port conflict, branch information filtering and SMT dynamic resource use strategy changes, the final modification strategy can be directly applied to the execution port binding and scheduling algorithm. The defending method in this paper can achieve the effect of close SMT technology and reduce the performance cost greatly. At the same time, its hardware cost is controllable. Therefore, the method proposed in this study has high application value.
Intrusion Detection System for Dual Route Deep Capsule Network
Yin Shenglin, Zhang Xinglan, Zuo Liyu
2022, 59(2):  418-429.  doi:10.7544/issn1000-1239.20200825
Asbtract ( 189 )   HTML ( 3)   PDF (1436KB) ( 127 )  
Related Articles | Metrics
The combination of deep learning and intrusion detection has become a hot topic in cyberspace security. In unstable network security situation, how to accurately detect abnormal traffic is an important task for intrusion detection. Each sample in the intrusion data contains multiple features, but not every feature can determine the final nature of the sample. Some features will even affect the judgment ability of the model. To solve this problem, an intrusion detection model based on residuals of a double routing deep capsule network is proposed. The model uses a deep capsule network to enhance the identification and extraction of features, which can extract higher dimensional data features. A hybrid attention mechanism is used to process the raw data so that the model focuses on features with high impact factors. The model captures the features based on vector representation and clusters the features in multiple directions by a dual routing algorithm. It adopts two strategies, namely residual connectivity and noise capsules, to stabilize the dynamic routing process to mitigate the interference of noisy features. Finally, experiments are conducted on the NSL-KDD dataset and CICIDS2017 dataset, and the results show that the accuracy is up to 90.31% and 99.23%, respectively.
A Perturbation Mechanism for Classified Transformation Satisfying Local Differential Privacy
Zhu Suxia, Wang Lei, Sun Guanglu
2022, 59(2):  430-439.  doi:10.7544/issn1000-1239.20200717
Asbtract ( 157 )   HTML ( 1)   PDF (1748KB) ( 76 )  
Related Articles | Metrics
As the state-of-the-art privacy protection technology, local differential privacy is widely used to compute the mean value of continuous numerical data. The perturbation mechanism will directly affect the accuracy of the mean value. In order to further improve the accuracy of mean value estimation, a perturbation mechanism for classified transformation satisfying differential privacy is proposed. In this mechanism, continuous numerical data is divided into transformation range, which is then segmented. What’s more, it transforms the segmentation into one-dimensional binary category data. After transformation, the mechanism of random response is used to perturb the data. More importantly, it extracts the value randomly as well as uniformly from the numerical segment identified by the perturbation data as the perturbed value. The experimental results of mean value estimation in both real data and synthetic data show that the mechanism proposed in the paper greatly improves the accuracy. In addition, this perturbation mechanism is used to build a mini-batch gradient descent algorithm satisfying local differential privacy and the linear regression learning task is completed successfully. The experimental results show that this method not only is superior to other existing mechanisms but also can obtain a smaller mean square error at the same time.
Cryptanalysis and Design of Anonymous Authentication Protocol for Value-Added Services in Internet of Vehicles
Yao Hailong, Yan Qiao
2022, 59(2):  440-451.  doi:10.7544/issn1000-1239.20200487
Asbtract ( 163 )   HTML ( 6)   PDF (967KB) ( 144 )  
Related Articles | Metrics
The Internet of vehicles (IoV) is an important part of a smart city. It can provide road safety, traffic management, autonomous driving, and Internet content distribution services. Among them, the content distribution service is an Internet value-added service for vehicles or their occupants. It faces more stringent security challenges than traditional Internet services. The key agreement protocol for the Internet of vehicles value-added service can initialize the session key for its secure communication, but most of the existing multi-server protocols have the shortcomings of anonymity and forward security. Recently, Vasudev et al. proposed a lightweight authentication protocol for value-added services in IoV using Hash functions. Cryptanalysis shows that in addition to the vulnerability of anonymity and forward security, the protocol also has fatal flaws such as the loss of the master key of the system due to the loss of the smart card. In order to overcome these flaws, elliptic curve cryptography (ECC) and Hash function are used to design an authenticated key agreement protocol suitable for the value-added services in IoV. Security analysis shows that the proposal can satisfy the authenticated key agreement security in the random oracle model, has strong anonymity and forward security, and can resist known Internet attacks. Performance analysis shows that the security of the proposed protocol is better than similar protocols, and the communication overhead on the user side is reduced by at least 34%.
Multi-Floor Location Method Based on Crowdsourcing
Luo Juan, Zhang Cuijun, Wang Chun
2022, 59(2):  452-462.  doi:10.7544/issn1000-1239.20200669
Asbtract ( 211 )   HTML ( 5)   PDF (3105KB) ( 72 )  
Related Articles | Metrics
The widespread deployment of wireless infrastructure makes the fingerprint location method based on WiFi become one of the most universal location methods. However, the time-consuming and labor-intensive fingerprint database construction hinders the development of RSSI(received signal strength indication) fingerprint localization. In this paper, we propose a low-cost and high-efficiency multi-floor fingerprint database construction method based on crowdsourcing aiming at the difficulty of fingerprint construction. Firstly, the indoor floor plan is transformed into indoor semantic map. Secondly, the data of IMU(inertial measurement unit) in the smartphone of crowdsourcing users are collected, and the sensor data are classified into corresponding floors by KF(Kalman filter) fusion algorithm. A segmented trajectory acquisition method is proposed, according to the sensor data, the relative trajectory and RSSI value sequence of the user are acquired. Finally, HMM(hidden Markov model) and TM-Viterbi(track matching Viterbi) algorithm is used to match the trajectory with the main path of indoor semantic map, thus providing the floor label and physical location label for RSSI value sequence. The HMM map matching algorithm of MCSLoc does not need the user’s initial location. The experimental results show that MCSLoc can quickly obtain the absolute initial position of the trajectory, construct multi-floor fingerprint database effectively, and improve the efficiency of multi floor location.
Wi-Do: Highly Robust Human Motion Perception Model Under WiFi Signal
Hao Zhanjun, Qiao Zhiqiang, Dang Xiaochao, Zhang Daiyang, Duan Yu
2022, 59(2):  463-477.  doi:10.7544/issn1000-1239.20200671
Asbtract ( 225 )   HTML ( 5)   PDF (4819KB) ( 125 )  
Related Articles | Metrics
Human-computer interaction is an important way for the Internet of Things to become intelligent, and human motion recognition has become the core technology for the realization of intelligent environments. Due to its good user experience, high universal performance, and low deployment cost, WiFi-based human motion recognition technology stands out from many interactive technologies and has shown great performance in the fields of smart security, sports health, and elderly active detection. In the existing WiFi motion recognition work, the motion recognition feature changes due to the change of the direction. In order to ensure the recognition accuracy, the motion recognition direction needs to be fixed. This directional dependence has caused a great obstacle to the wider interactive application of WiFi-based motion recognition technology. To overcome this limitation, a direction-independent motion recognition solution, Wi-Do, is proposed. It is a highly robust human motion perception model under WiFi signals. In this work, the antenna diversity is used to eliminate the random phase shift; the Doppler shift and the fast Fourier transform value are used as the recognition features; and the bidirectional GRU of attention mechanism is introduced to classify and recognize the motion. This model integrates spatial features into the time model, which improves the robustness and accuracy of wireless signal recognition of human actions. The results of the experiment in a typical indoor environment show superior performance and 93% accuracy, verifying that the method is significantly better than the previous method.
Multi-Source Heterogeneous Data Fusion Based on Federated Learning
Mo Huiling, Zheng Haifeng, Gao Min, Feng Xinxin
2022, 59(2):  478-487.  doi:10.7544/issn1000-1239.20200668
Asbtract ( 994 )   HTML ( 26)   PDF (1729KB) ( 509 )  
Related Articles | Metrics
With the rapid development of technology, the number of network edge devices with the capability of computation and memory is increasing, and the volume of the generated data is growing exponentially, which makes it difficult for a centralized processing model with cloud computing as the core to efficiently process data generated by edge devices. Not only will the network delay increase, but the data is likely to be leaked on the upload link, and data security cannot be guaranteed. In addition, due to the diversity of edge devices and the continuous enrichment of data representation methods, multi-modal data exists widely. The processing of multi-source heterogeneous data collected by different edge devices has become an urgent problem in big data research. In order to make full use of heterogeneous data on edge devices and solve the problem of “data communication barriers” caused by data privacy in edge computing, in this paper we propose a novel fusion algorithm for multi-source heterogeneous data based on Tucker decomposition in federated learning. For the fusion problem of heterogeneous data without interaction in federated learning, the proposed algorithm introduces Tucker decomposition theory to capture the multi-dimensional characteristics of heterogeneous data by constructing a high-order tensor. Finally, the effectiveness of this algorithm is verified on the MOSI dataset.