ISSN 1000-1239 CN 11-1777/TP

    Default Latest Most Read
    Please wait a minute...
    For Selected: Toggle Thumbnails
    Journal of Computer Research and Development    2022, 59 (2): 253-254.   DOI: 10.7544/issn1000-1239.2022.qy0201
    Accepted: 28 January 2022

    Abstract639)   HTML10)    PDF (219KB)(308)       Save
    Related Articles | Metrics
    Spatial Data Intelligence: Concept, Technology and Challenges
    Song Xuan, Gao Yunjun, Li Yong, Guan Qingfeng, Meng Xiaofeng
    Journal of Computer Research and Development    2022, 59 (2): 255-263.   DOI: 10.7544/issn1000-1239.20220108
    Abstract1032)   HTML29)    PDF (690KB)(713)       Save
    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.
    Related Articles | Metrics
    Spatial Occupancy-Based Dominant Co-Location Patterns Mining
    Fang Yuan, Wang Lizhen, Wang Xiaoxuan, Yang Peizhong
    Journal of Computer Research and Development    2022, 59 (2): 264-281.   DOI: 10.7544/issn1000-1239.20210913
    Abstract274)   HTML8)    PDF (4254KB)(190)       Save
    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.
    Related Articles | Metrics
    Spatial-Temporal Graph Neural Network for Traffic Flow Prediction Based on Information Enhanced Transmission
    Ni Qingjian, Peng Wenqiang, Zhang Zhizheng, Zhai Yuqing
    Journal of Computer Research and Development    2022, 59 (2): 282-293.   DOI: 10.7544/issn1000-1239.20210901
    Abstract525)   HTML10)    PDF (1313KB)(433)       Save
    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.
    Related Articles | Metrics
    Location-Aware Joint Influence Maximizaton in Geo-Social Networks Using Multi-Target Combinational Optimization
    Jin Pengfei, Chang Xueqin, Fang Ziquan, Li Miao
    Journal of Computer Research and Development    2022, 59 (2): 294-309.   DOI: 10.7544/issn1000-1239.20210891
    Abstract229)   HTML5)    PDF (4256KB)(171)       Save
    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.
    Related Articles | Metrics
    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
    Journal of Computer Research and Development    2022, 59 (2): 310-328.   DOI: 10.7544/issn1000-1239.20210875
    Abstract339)   HTML14)    PDF (2947KB)(221)       Save
    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.
    Related Articles | Metrics
    Dynamic Ride-Hailing Route Planning Based on Deep Reinforcement Learning
    Zheng Bolong, Ming Lingfeng, Hu Qi, Fang Yixiang, Zheng Kai, Li Guohui
    Journal of Computer Research and Development    2022, 59 (2): 329-341.   DOI: 10.7544/issn1000-1239.20210905
    Abstract876)   HTML25)    PDF (2081KB)(650)       Save
    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.
    Related Articles | Metrics
    Fast and Distributed Map-Matching Based on Contraction Hierarchies
    Li Ruiyuan, Zhu Haowen, Wang Rubin, Chen Chao, Zheng Yu
    Journal of Computer Research and Development    2022, 59 (2): 342-361.   DOI: 10.7544/issn1000-1239.20210904
    Abstract531)   HTML16)    PDF (3130KB)(285)       Save
    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.
    Related Articles | Metrics
    A Shortest Path Query Method over Temporal Graphs
    Zhang Tianming, Xu Yiheng, Cai Xinwei, Fan Jing
    Journal of Computer Research and Development    2022, 59 (2): 362-375.   DOI: 10.7544/issn1000-1239.20210893
    Abstract322)   HTML7)    PDF (1242KB)(180)       Save
    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.
    Related Articles | Metrics
    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
    Journal of Computer Research and Development    2022, 59 (2): 376-389.   DOI: 10.7544/issn1000-1239.20210892
    Abstract224)   HTML3)    PDF (2328KB)(170)       Save
    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.
    Related Articles | Metrics