Interactive visual query systems are essential for the exploration and analysis of geospatial data. However, developing such systems has become increasingly challenging in recent years due to the conflict between the unprecedented volume of data and the need for instantaneous feedback. To address this challenge, we present HiVQ, a High-performance Visual Query system for real-time interactive visual query of geospatial big data. HiVQ adopts an innovative “Query as Visualization” paradigm, transforming user interactions into pixel value queries which can be processed efficiently with specialized indices and optimization strategies. Unlike conventional solutions that query and visualize geospatial objects sequentially, HiVQ effectively omits most geospatial objects and unnecessary computations that do not affect the final visualization, ensuring minimal sensitivity to data volume. Experimental results show that HiVQ accelerates visual queries by at least seven times compared to SOTA methods. This demonstration enables users to interactively explore and analyze spatial data with billions of nodes at any scale, receiving responses in milliseconds as they dynamically adjust analysis parameters, query conditions, or map styling. The demonstration video is available at https://gitee.com/kyrie-Bang/HiVQ-Demo.

With the development of satellite technology and the proliferation of remote sensing data, developing and designing effective cross-modal image-text retrieval methods has become a popular research topic. The main challenge in this area is to establish effective mapping relationships between visual and textual modalities to form a shared latent space. Existing approaches usually focus on extracting features from each modality independently using pre-trained unimodal models. However, these techniques rarely consider heterogeneous representations of image-text data hindering robust feature extraction and representation to measure high-level semantic similarity, leading to uncertainty struggles between different modalities/objects. To address these limitations, in this paper, we propose a novel Triplet Dictionary-driven learning and Uncertainty-aware Fusion (TDUF) framework, which is end-to-end efficient training of remote sensing cross-model image-text retrieval models. Firstly, a rich feature space is extracted by constructing a structural representation of the Region Adjacency Graph Embedding(RAGE) through local feature description and unsupervised segmentation, and by reducing the data dimensionality in the encoder while preserving the image structural information. Secondly, the Triplet Dictionary-Driven Learning(TDDL) employs a two-layer optimization strategy to construct a sparse metric space, enhancing intra-modal similarity and inter-modal dissimilarity. Finally, Uncertainty-Aware Fusion(UAF) are constructed to quantify the uncertainty of heterogeneous representations using multilevel feature aligners and feature impressions to achieve cross-modal fair comparisons at the object and feature levels. Furthermore, extensive experiments demonstrate that TDUF achieves state-of-the-art performance, outperforming CLIP-based methods by 8.1 % in mean Recall (mR) on remote sensing benchmarks, further enhancement of the ability to obtain geospatial information quickly and accurately.

In the rapidly evolving global shipping industry, accurate vessel trajectory prediction is essential for effective maritime traffic management. However, the inherent uncertainties in vessel voyages pose significant challenges for existing methods in achieving precise long-term predictions. Inspired by the success of large language models (LLMs) in natural language processing, we propose SEMINT—a novel framework that integrates SEMantic cognition and INTent context-awareness for long-term vessel trajectory prediction. SEMINT leverages LLMs to semantically interpret vessel navigation behaviors and infer multiple voyage intents. The final intent inference is derived from the consensus among multiple reasoning chains, which are then combined with historical preferences to form an intent context. Guided by this context, a Transformer-based trajectory prediction model captures the dependencies between critical waypoints and voyage intent, thereby achieving stable long-term numerical predictions. SEMINT combines the advantages of LLMs and task-specific deep learning models, transforming voyage uncertainties into high-level intent diversity and simplifying the learning process for long-term movement patterns. Experiments on real-world datasets show that SEMINT outperforms previous methods, reducing average and final displacement errors by 28.47% and 31.59%, respectively.

Pointly Supervised Object Detection (PSOD) has attracted considerable interests due to its lower labeling cost as compared to box-level supervised object detection. However, the complex scenes, densely packed and dynamic-scale objects in Remote Sensing (RS) images hinder the development of PSOD methods in RS field. In this paper, we make the first attempt to achieve RS object detection with single point supervision, and propose a PSOD method tailored for RS images. Specifically, we design a point label upgrader (PLUG) to generate pseudo box labels from single point labels, and then use the pseudo boxes to supervise the optimization of existing detectors. Moreover, to handle the challenge of the densely packed objects in RS images, we propose a sparse feature guided semantic prediction module which can generate high-quality semantic maps by fully exploiting informative cues from sparse objects. Extensive ablation studies on the DOTA dataset have validated the effectiveness of our method. Our method can achieve significantly better performance as compared to state-of-the-art image-level and point-level supervised detection methods, and reduce the performance gap between PSOD and box-level supervised object detection. Code is available at https://github.com/heshitian/PLUG.

Remote sensing (RS) image semantic segmentation has attracted much attention due to its wide applications. However, deep learning based RS image semantic segmentation methods usually require substantial manual pixel-wise annotations, which are expensive and hard to obtain in practice. Although existing semi-supervised RS semantic segmentation methods effectively reduce dependence on labeled data, they generally focus on information consistency between labeled and unlabeled images, but ignore the potential context information between different areas of the RS image. In fact, the objects contained in a RS image usually have some long-range dependence between each other, since trees are usually on both sides of a road, and the middle of two rows of houses is commonly a road. Therefore, we believe that the potential dependencies between different areas of the RS image should be beneficial for reducing the label dependence of RS semantic segmentation. Based on this point, we propose a novel semi-supervised RS image semantic segmentation network named SegMind, which is based on mean teacher (MT) architecture and adopts Masked Image Modeling (MIM) to enhance information interactions of different areas. Moreover, Contrastive Learning (CL) and entropy loss are introduced to SegMind framework to further improve the linear separability and prediction confidence of the proposed model. Experiments on three datasets have demonstrated the superiority of proposed method over the state-of-the-art methods. The code is available at https://github.com/lzh-ggs-ddu/SegMind.

Remote sensing (RS) images change detection (CD) aims to obtain change information of the target area between multi-temporal RS images. With the modernization of cities, building change detection (BCD) plays a pivotal role in land resource planning, smart city construction and natural disaster assessment, and it is a typical application field of change detection task. Recently, deep learning based methods have shown their superiority in RS image change detection. However, the performance of the existing supervised change detection methods relies heavily on a large amount of high quality annotated bi-temporal RS image as training data, which is usually hard to obtain in practice. To address this issue, a semi-supervised BCD method using a pseudo bi-temporal data generator with consistency regularization was proposed. This method only needs a very small amount of single-temporal RS images with building extraction labels as labeled data. Firstly, with the help of the pseudo bi-temporal data generator, the model can generate a large number of pseudo bi-temporal images with CD labels from a small number of single-temporal images and corresponding building extraction labels automatically, which greatly augments the labeled data set for CD model training. Then, we proposed an error-prone data enhancement fine-tuning strategy to improve the learning effect of the proposed model to these synthesized training data. Finally, we enhance the robustness of the model by forcing the model to make consistent predictions on the images before and after perturbations. Extensive experimental results demonstrate that our method can effectively improve the BCD performance of the model even if labeled data are scare, and outperforms the state-of-the-art methods.

Fine-grained entity typing (FET) aims to deduce specific semantic types of the entity mentions in the text. Modern methods for FET mainly focus on learning what a certain type looks like. And few works directly model the type differences, that is, let models know the extent that which one type is different from others. To alleviate this problem, we propose a type-enriched hierarchical contrastive strategy for FET. Our method can directly model the differences between hierarchical types and improve the ability to distinguish multi-grained similar types. On the one hand, we embed type into entity contexts to make type information directly perceptible. On the other hand, we design a constrained contrastive strategy on the hierarchical structure to directly model the type differences, which can simultaneously perceive the distinguishability between types at different granularity. Experimental results on three benchmarks, BBN, OntoNotes, and FIGER show that our method achieves significant performance on FET by effectively modeling type differences.

Cellular Signal Strength (CSS), defined as the signal power received by mobile phones, is an important aspect of geographic information flow analysis, because the density of such information can reflect the urbanization variables such as population, gross domestic product, built-up area, electric power consumption, etc. Despite the importance, the real-time analysis of global CSS distribution remains a challenging problem due to the large data scale. In this article, a Display-driven Computing (DisDC) technique is designed and applied to provide efficient large scale interactive CSS visualization, generating results by calculating the value of each pixel that directly for display. Specifically, we present an efficient CSS measurement algorithm, which introduces spatial indexes and a corresponding query strategy; besides, an optimized parallel computing architecture is proposed to ensure the ability of real-time visualization. Experiments show that our approach obviously outperforms traditional methods and is capable of handling more than 40 million base stations in real-time. Moreover, an online demonstration is provided athttps://github.com/MemoryMmy/CSSMap.

Knowledge graph is becoming an indispensable resource that offers structured information for numerous AI applications. However, the knowledge graph often suffers from its incompleteness. Building a complete, high-quality knowledge graph is time-consuming and requires significant human annotation efforts. In this paper, we study the Knowledge Graph Population task, which aims at extending the scale of structured knowledge, with a special focus on reducing data preparation and annotation efforts. Previous works mainly based on discriminative methods build classifiers and verify candidate triplets that are extracted from texts, which heavily rely on the quality of data collection and co-occurrance of entities in the text. However, such methods fail to generalize on entity pairs that are not highly co-occurred, and fail to discover entity pairs that are not co-occurred at all in the given text corpus. We introduce a generative perspective to approach this task and define each relationship by learning the data distribution that embodies the core common properties for relational reasoning. A generative modelKGGenis proposed, which samples from the learned data distribution for each relation and can generate triplets regardless of entity pair co-occurrence in the text corpus. To further improve the generation quality while alleviate human annotation efforts, adversarial learning is adopted to not only encourage generating high quality triplets, but also give model the ability to automatically assess the generation quality. Quantitative and qualitative experimental results conducted on two real-world generic knowledge graphs show that the proposed modelKGGengenerates novel and meaningful triplets with improved efficiency and less human annotation comparing with the state-of-the-art approaches.

Query feeds recommendation is a new recommended paradigm in mobile search applications, where a stream of queries need to be recommended to improve user engagement. It requires a great quantity of attractive queries for recommendation. A conventional solution is to retrieve queries from a collection of past queries recorded in user search logs. However, these queries usually have poor readability and limited coverage of article content, and are thus not suitable for the query feeds recommendation scenario. Furthermore, to deploy the generated queries for recommendation, human validation, which is costly in practice, is required to filter unsuitable queries. In this paper, we propose TitIE, a query mining system to generate valuable queries using the titles of documents. We employ both an extractive text generator and an abstractive text generator to generate queries from titles. To improve the acceptance rate during human validation, we further propose a model-based scoring strategy to pre-select the queries that are more likely to be accepted during human validation. Finally, we propose a novel dual learning approach to jointly learn the generation model and the selection model by making full use of the unlabeled corpora under a semi-supervised scheme, thereby simultaneously improving the performance of both models. Results from both offline and online evaluations demonstrate the superiority of our approach.

We present DiSA, a Display-driven Spatial Analysis framework for interactive analysis of large-scale geographical vector data. DiSA calculates visualization of analysis results directly using a parallel per-pixel approach with efficient fine-grained spatial indexes. Compared with conventional object-based methods, DiSA can greatly reduce the computational complexity (from O(n) to O(log(n)) in some cases), making it less sensitive to data volumes. Experimental results verify that DiSA can provide analysis of billion-scale spatial objects in milliseconds. We demonstrate DiSA with various application scenarios including raw data exploration, spatial buffer and overlay analysis, and global cellular signal strength analysis. Users can explore 10 millions of spatial objects, adjust algorithm parameters, and always see the results in real-time on a personal computer.

This paper investigates Earth observation scheduling of agile satellite constellation based on evolutionary multiobjective optimization (EMO). The mission planning of agile Earth observation satellite (AEOS) is to select and specify the observation activities to acquire images on the earth surface. This should be done in accordance with operational constraints and in order to maximize certain objectives. In this paper three objectives are considered, i. e. profit, quality and timeliness. Preference-based EMO methods are introduced to generate solutions preferable for the decision maker, whose preference is expressed by a reference point. An improved algorithm based on R-NSGA-II, which is named CD-NSGA-II, is proposed and compared with other algorithms in various scheduling scenarios. Results show that the chosen preference modeling paradigm allows to focus search on the interesting part of the Pareto front. Moreover, the tested algorithms behave differently with the change of reference point and degree of conflicts, among them CD-NSGA-II has the best overall performance. Suggestions on applying these algorithms in practice are also given in this paper.

The saliency detection provides an alternative methodology to semantic image understanding in many applications, for example, content-based image retrieval. To detect saliency for lunar remote sensing images, this letter proposes a crater feature model by analyzing the relationship between local interest points and saliency of lunar images. Based on the model, we propose a novel saliency detection method for lunar images. Our method merges and combines the speed-up robust feature features of the highlight region and shadow region of an impact crater to get the candidate regions of interest (ROI). Then, a descriptive feature vector is generated for each ROI, and the resulting saliency regions are distinguished from false detected and inconspicuous ones through a support vector machine. The method has been put into test on Chang'e-1 and Chang'e-2 lunar image data, and confirmed to be able to detect the salient region of impact craters correctly, with results much better than those obtained by the classical saliency detection method.

The earth observing mission scheduling problem is an important real-world problem that impacts the opportunity of dealing with emergencies and the collection of hazard monitoring research data. The period of traditional data acquisition cycle for earth science research is often too long to receive some important observation data in time. Besides, with rapid developing of sensor web techniques, the envisioned future earth scientists and emergency workers would like to investigate the natural phenomenon by using large numbers of sensors based on different platforms, such as satellite, balloon, aircraft and ground-based. How to schedule these sensors that are frequency agile and capable of multi-scene observations for completing a hazard monitoring research mission is a difficult task. In this paper, we focus on solving two problems above. The active observation model based on hazard monitoring domain knowledge is proposed for reducing responsive time of abnormal phenomenon. And then information gain model is introduced for evaluating observation schedule. On this basis, multi-platform sensor optimization scheduling model is constructed. Simulation and analysis show that the proposed model can solve the problem effectively. Moreover, the normal requests are also taken into account during these events for maximizing the value of various sensors.

Multi-class network traffic classification is a fundamental function for network services and management. Support vector machine (SVM) based network traffic classification has recently attracted increasing interest, for its high accuracy and low training sample size requirement. However, to better fit applications with delay requirements, it is desirable to reduce the high computation cost of existing SVM-based traffic classifiers. In this paper, we propose a novel scheme for SVM-based traffic classification (called fuzzy tournament). Experiment results based on real network traffic traces show that our proposed scheme can reduce computation cost by as much as 7.65 times; in the mean time, misclassification ratio is consistently reduced by up to 2.35 times as well.

Targets with uniform rotational motion may cause migration through cross-range cells during the imaging time, which makes the inverse synthetic aperture radar image smeared. Traditional motion compensation methods hardly work well because it is difficult to estimate the quadratic phase error (QPE) caused by uniform rotational motion efficiently. To solve this problem, a novel QPE estimation method based on phase cancellation (PC) is proposed in this letter. In this method, PC is used to eliminate the linear term of the phase, which is a disadvantage to the QPE estimation. By employing the weighted linear least squares algorithm, the QPE can be estimated efficiently and robustly. Experiments with both simulated and measured radar data demonstrate the performance of the proposed method.

In this paper, satellite imaging scheduling of cooperative multiple centers, an example of multi-agent systems, is discussed with a proposal of a novel Cooperative CoEvolutionary Planning Algorithm (CCEPA). Considering the numbers of the multi-center and the characteristics of targets to be observed, CCEPA decomposes the tasks into smaller components and evolves multiple solutions in the form of cooperative subpopulations. At the same time, for such evolutionary algorithm based on scheduling, a novel fixed-length binary encoding mechanism for tasks assigned to each center is also proposed. Incorporated with various features like archiving, dynamic sharing, the CCEPA is capable of maintaining archive diversity in the evolution and distributing the solutions uniformly along the Pareto front. Simulation and analysis show that the proposed algorithm can solve the problem effectively.

We present a distributed spatial index called CANQTree based on a content-addressable network (CAN) and QuadTree-alike structures. In our system, both spatial objects and their corresponding nodes in a QuadTree are identified by some points and mapped into CAN zones of peers. For a given spatial range query, CAN-QTree can provide O(n1/2) search performance. With a uniform distribution of spatial objects, given epsiv > 0, CAN-QTree can provably maintain a load imbalance of at most 2+epsiv between a highest loaded peer and a lightest loaded peer. Simulations show that our CAN-QTree is an effective spatial index with a guarantee of good load-balancing.

Electromagnetic detection satellite (EDS) is a type of Earth observation Satellites (EOSs). The Information collected by EDSs is very important in some application domain, such as industry, science and military. The scheduling of EDSs is a complex combinatorial optimization problem. Current research mainly focuses on the scheduling of imaging satellites and SAR satellites, little work on the scheduling of EDSs for its specific requirements. Considering the specific constrains of EDSs, we established a MultiSatellites scheduling model and proposed a scheduling algorithm based on genetic algorithm. A hybrid algorithm incorporated with genetic algorithm and stochastic climbing algorithm was constructed to improve the scheduling algorithm. To deal with some specific constrains, a punish function method was introduced. We have conducted some experiments to validate correctness and practicability of our scheduling algorithms.

Aiming at the existing problem of single buffer replacement policy and the inability of predicting future SQLs execution in current database buffer replacement algorithm, proposed a new database buffer replacement algorithm---CG-ABR (call graph optimizing adaptive buffer replacement algorithm). CG-ABR could adapt to current SQL's access behavior automatically by getting it through query optimizer, and this algorithm optimized the management method of buffer access information, and generated the call graph according to the SQL's execution order of application program's logic, based on this call graph, the future SQLs execution can be predicted, and the pages might not be accessed hereafter, would be replaced, which could optimize the buffer space. The experiments and analysis showed that CG-ABR algorithm is effective in buffer replacement, with high hit ratio to real time access types and enormous value in practicing applications.

EOSs (Earth Observing Satellites) circle the earth to take shotswhich are requested by customers. To make replete use of resourcesof EOSs, it is required to deal with the problem of united imagingscheduling of EOSs in a given scheduling horizon, which is acomplicated multi-objective combinatorial optimization problem. Inthis paper, we construct a mathematical model for the problem byabstracting imaging constraints of different EOSs. Then we propose anovel multi-objective EOSs imaging scheduling method, which is basedon the Strength Pareto Evolutionary Algorithm 2. The specialencoding technique and imaging constraint control are applied toguarantee feasibility of solutions. The approach is tested upon fourreal application problems of CBERS EOSs series. From the results, itis confirmed that the proposed approach is effective in solvingmulti-objective EOSs imaging scheduling problems.

This paper introduces an efficient non-blocking spatial join (NSJ, for short) algorithm to deal with spatial objects from remote sources via underlying network. The objectives of NSJ are: (1) start reporting the first output join results as soon as possible, and (2) minimize the cost for output the remaining results. As some other previous non-blocking join algorithms, NSJ includes two stages: memory-join stage and disk-join stage The memory-join stage employs a join process as along as receiving spatial objects, and the disk-join stage is responsible for the uncompleted join process during the memory-join stage after all spatial objects are received completely. We propose a dynamic concurrent flush policy(DCFP) based on resident degree to process memory overflow, which makes join process in memory-join stage more efficiently. We also develop an optimal data access schedule algorithm based on BEA (Bond Energy Algorithm) to reduce redundant I/O and CPU cost in disk-join stage. Extensive experiments prove that our technique delivers result significantly more efficient than the previous methods.

This paper investigates the issues when several complementary geospatial Web services are chained to be a customized application process. This paper proposes a conceptual framework and a data structure, called service chain graph (SCG), to describe the geospatial Web service integration and the dynamic construction of service chaining process. A set of dynamic structural transformation rules is given to model the dynamic process of service chaining. Implementation issues are discussed and a prototype system is briefly presented for integration of several distributed, heterogeneous geospatial data services based on the model proposed by this paper.

The emergence of Web services has led to more interest into Web service composition, which is an active area of research. The formidable problem of efficient and effective composition of existing Web services is the subject of much current attention. The study of workflow model is one of the most important parts and a key layer of Web service composition. The existing approaches have difficulties in modeling dynamic and complex service composition process, so we propose a novel workflow model named Service/Resource Net (SRN) for Web service composition, which is an extended Petri-net-based model with some new elements, such as time, resource taxonomy, condition, etc. To establish formal concept system of Web service taxonomy in SRN, we present Web service semigroup based on group theory. Moreover, meta-service is proposed based on the definition of generating element in cyclic monoid. As the supplement of traditional analysis methods of basic Petri net, some new methods based on graph theory are presented for SRN analyzing and evaluating. For system and methodology validation purpose, SRN is applied to a case study in our research project.

Efficient path computation is essential for applications such as intelligent transportation systems (ITS) and network routing. In ITS navigation systems, many path requests can be submitted over the same, typically huge, transportation network within a small time window. While path precomputation (path view) would provide an efficient path query response, it raises three problems which must be addressed: 1) precomputed paths exceed the current computer main memory capacity for large networks; 2) disk-based solutions are too inefficient to meet the stringent requirements of these target applications; and 3) path views become too costly to update for large graphs (resulting in out-of-date query results). We propose a hierarchical encoded path view (HEPV) model that addresses all three problems. By hierarchically encoding partial paths, HEPV reduces the view encoding time, updating time and storage requirements beyond previously known path precomputation techniques, while significantly minimizing path retrieval time. We prove that paths retrieved over HEPV are optimal. We present complete solutions for all phases of the HEPV approach, including graph partitioning, hierarchy generation, path view encoding and updating, and path retrieval. In this paper, we also present an in-depth experimental evaluation of HEPV based on both synthetic and real GIS networks. Our results confirm that HEPV offers advantages over alternative path finding approaches in terms of performance and space efficiency.

Investigates optimization strategies for processing path queries with embedded spatial constraints, such as avoiding areas with certain characteristics. To resolve complex spatial constraints during path finding, we consider two decisions: (1) the spatial relation operations (e.g. intersection) between areas and links can be pre-processed or intermixed with path-finding, and (2) areas satisfying the query constraint can be pre-filtered or dynamically selected during path-finding. Based on these two decisions, we propose and implement the resulting four integrated query processing strategies, utilizing state-of-the-art technologies such as spatial joins for intersect computation, R-tree access structure for spatial overlap searching, and spatial clustering for efficient path searching. In this paper, we also report an experimental evaluation to show which strategies perform best in different scenarios.

The development of a cost model for predicting the performance of spatial joins has been identified in the literature as an important and difficult problem. The authors present the first cost model that can predict the performance of spatial joins using R-trees. Based on two existing R-trees (join targets), the model first estimates the number of expected I/Os for the join process by assuming a zero buffer size. The method for this estimation extends the cost model for R-tree window queries (developed by Kamel and Faloutsos (1993) and by Pagel et al. (1993)) to also handle spatial joins (which are more complex). In the context of spatial join processing, this number of zero-buffer expected I/Os is not practical for performance prediction in a buffered environment. To model the buffer impact, they use an (exponential) distribution function to measure the probability that a bufferless I/O would cause a page fault in a buffered environment. Based on this probability and the zero-buffer expected I/O cost, the estimated number of I/Os for an R-tree join can then be computed. The comparisons between the predictions from the cost model and the actual results from the experiments based on real GIS maps show that the average relative error ratio is about 10% with a maximum of about 20% for a wide range of buffer sizes. Therefore, our model is a useful tool for the query optimization of spatial join queries.

In this paper, we present an experimental evaluation of graph clustering strategies in terms of their effectiveness in optimizing I/O for path query processing in digital map databases.Clustering optimization is attractive because it does not incurs any run-time cost, and is complimentary to many of the existing techniques in path query optimization.We first propose a novel graph clustering technique, called Spatial Partition Clustering (SPC), that creates balanced partitions of links based on the spatial proximity of their origin nodes.We then select three alternative clustering techniques from the literature, namely two-way partitioning, approximately topological clustering, and random clustering, to compare their performance in path query processing with SPC.Experimental evahration indicatesthat our SPC performs the best for the high-locality graphs (such as GIS maps), whereas the two-way partitioning approach performs the best for no-locality random graphs.

Efficient path query processing is a key requirement for advanced database applications including GIS (Geographic Information Systems) and ITS (Intelligent Transportation Systems).We study the problem in the context of automobile navigation systems where a large number of path requests can be submitted over the tmrtsportation network within a short period of time.To guarantee efficient responsefor path queries, we employ a path view materiatization strategy for precomputing the best paths.We tackle the following three issues: (1) memory-resident solutions quickly exceed cr.nrentcomputer storage capacity for networks of thousands of nodes, (2) diskbased solutions have been found inefficient to meet the stringent performance requirements, and (3) path views become too costly to update for large graphs.We propose the HEPV (Hierarchical Encoded Path View) approach that addressesthese problems while guaranteeing the optimality of path retrieval.Our experimental fesuks reveaf that HEPV is more efficient than previously known path finding approaches.