The exponential growth of video data highlights the necessity of exploring large-scale video repositories to extract valuable insights. Querying video clips based on content and temporal attributes is a critical task. However, existing solutions face two major challenges: insufficient flexibility in handling complex query conditions involving statistical reasoning and temporal constraints, and low efficiency under high query quality requirements and resource constraints.

The Reverse 𝑘-Nearest Neighbor (R𝑘NN) query over moving objects on road networks seeks to find all moving objects that consider the specified query point as one of their 𝑘 nearest neighbors.In location based services, many users probably submit R𝑘NN queries simultaneously.However, existing methods largely overlook how to efficiently process multiple such queries together, missing opportunities to share redundant computations and thus reduce overall processing costs.To address this, this work is the first to explore batch processing of multiple R𝑘NN queries, aiming to minimize total computation by sharing duplicate calculations across queries.To tackle this issue, we propose the BR𝑘NN-Light algorithm, which uses rapid verification and pruning strategies based on geometric constraints, along with an optimized range search technique, to speed up the process of identifying the R𝑘NNs for each query.Furthermore, it proposes a dynamic distance caching mechanism to enable computation reuse when handling multiple queries, thereby significantly reducing unnecessary computations.Experiments on multiple real-world road networks demonstrate the superiority of the BR𝑘NN-Light algorithm on the processing of batch queries. CCS Concepts• Theory of computation → Database query processing and optimization (theory); Data structures and algorithms for data management.

With the rise of Large Language Models (LLMs), tourists increasingly use it for route planning by entering keywords for attractions, instead of relying on traditional manual map services. LLMs provide generally reasonable suggestions, but often fail to generate optimal plans that account for detailed user requirements, given the vast number of potential POIs and possible routes based on POI combinations within a real-world road network. In this case, a route-planning API could serve as an external tool, accepting a sequence of keywords and returning the top-k best routes tailored to user requests. To address this need, this paper introduces the Keyword-Aware Top-k Routes (KATR) query that provides a more flexible and comprehensive semantic to route planning that caters to various user's preferences including flexible POI visiting order, flexible travel distance budget, and personalized POI ratings. Subsequently, we propose an explore-and-bound paradigm to efficiently process KATR queries by eliminating redundant candidates based on estimated score bounds from global to local levels. Extensive experiments demonstrate our approach's superior performance over existing methods across different scenarios.

The problem of identifying thek-shortest paths (KSPs for short) in a dynamic road network is essential to many location-based services. Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Very often such services have to process numerous KSP queries over large road networks at the same time, thus there is a pressing need to identify distributed solutions for this problem. However, most existing approaches are designed to identify KSPs on a static graph in a sequential manner (i.e., the$(i+1)^{th}$shortest path is generated based on the$i^{th}$shortest path), restricting their scalability and applicability in a distributed setting. We therefore propose KSP-DG, a distributed algorithm for identifyingk-shortest paths in a dynamic graph. It is based on partitioning the entire graph into smaller subgraphs, and reduces the problem of determining KSPs into the computation of partial KSPs in relevant subgraphs, which can execute in parallel on a cluster of servers. A distributed two-level index called DTLP is developed to facilitate the efficient identification of relevant subgraphs. A salient feature of DTLP is that it indexes a set of virtual paths that are insensitive to varying traffic conditions in an efficient and compact fashion, leading to very low maintenance cost in dynamic road networks. This is the first treatment of the problem of processing KSP queries over dynamic road networks. Extensive experiments conducted on real road networks confirm the superiority of our proposal over baseline methods.

We study the problem of processing continuous$k$nearest neighbor (C$k$NN) queries over moving objects on road networks, which is an essential operation in a variety of applications. We are particularly concerned with scenarios where the object densities in different parts of the road network evolve over time as the objects move. Existing methods on C$k$NN query processing are ill-suited for such scenarios as they utilize index structures with fixed granularities and are thus unable to keep up with the evolving object densities. In this paper, we directly address this problem and propose an object density aware index structure called ODIN that is an elastic tree built on a hierarchical partitioning of the road network. It is equipped with the unique capability of dynamically folding/unfolding its nodes, thereby adapting to varying object densities. We further present the ODIN-KNN-Init and ODIN-KNN-Inc algorithms for the initial identification of the$k$NNs and the incremental update of query result as objects move. Thorough experiments on both real and synthetic datasets confirm the superiority of our proposal over several baseline methods.

Abstract Advanced knowledge engineering (KE), represented by knowledge graph (KG), drives the development of various fields and engineering technologies and provides various knowledge fusion and knowledge empowerment interfaces. At the same time, advanced system engineering (SE) takes model-based system engineering (MBSE) as the core to realize formal modeling and process analysis of the whole system. The two complement each other and are the key technologies for the transition from 2.0 to 3.0 in the era of artificial intelligence and the transition from perceptual intelligence to cognitive intelligence. This survey summarizes an advanced information fusion system, from model-driven to knowledge-enabled. Firstly, the concept, representative methods, key technologies and application fields of model-driven system engineering are introduced. Then, it introduces the concept of knowledge-driven knowledge engineering, summarizes the architecture and construction methods of advanced knowledge engineering and summarizes the application fields. Finally, the combination of advanced information fusion systems, development opportunities and challenges are discussed.

Recent advances in Computer Vision (CV) algorithms have improved accuracy and efficiency, making video annotations possible with high accuracy. In this paper, we utilize the annotated data provided by such algorithms and construct graph representations to capture both object labels and spatial-temporal relationships of objects in videos. We define the problem of Spatial and Temporal Constrained Ranked Retrieval (STAR Retrieval) over videos. Based on the graph representation, we propose a two-phase approach, consisting of the ingestion phase, where we construct and materialize the Graph Index (GI), and the query phase, where we compute the top ranked windows (video clips) according to the window matching score efficiently. We propose two algorithms to perform Spatial Matching (SMA) and Temporal Matching (TM) separately with an early-stopping mechanism. Our experiments demonstrate the effectiveness of the proposed methods, achieving orders of magnitude speedups on queries with high selectivity.

Recent advances in Computer Vision and Deep Learning have made possible the efficient extraction of structured information from frames of video feeds. As such, a stream of objects and their associated classes along with unique object identifiers derived via object tracking can be generated, providing unique objects as they are captured across frames. In this paper we initiate a study of temporal queries involving objects and their co-occurrences in video feeds. For example, queries that identify video segments during which the same two red cars and the same two humans appear jointly for five minutes are of interest to many applications ranging from law enforcement to security and safety. We take the first step and define such queries in a way that they incorporate certain physical aspects of video capture such as object occlusion. We present an architecture consisting of three layers, namely object detection/tracking, intermediate data generation, and query evaluation. We propose two techniques, Marked Frame Set (MFS) and Sparse State Graph (SSG), to organize all detected objects in the intermediate data generation layer, which effectively, given the queries, minimizes the number of objects and frames that have to be considered during query evaluation. We also introduce an algorithm called SSG-CM that processes incoming frames against the SSG and efficiently prunes objects and frames unrelated to query evaluation, while maintaining all states required for succinct query evaluation. We present the results of a thorough experimental evaluation utilizing both real and synthetic data, establishing the trade-offs between MFS and SSG. We stress various parameters of interest in our evaluation and demonstrate that the proposed query evaluation methodology coupled with the proposed algorithms is capable to evaluate temporal queries over video feeds efficiently, achieving orders of magnitude performance benefits.

The problem of route planning on road network is essential to many Location-Based Services (LBSs). Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Thus, a practical route planning strategy is required to supply the continuous route optimization considering the historic, current, and future traffic condition. However, few existing works comprehensively take into account these various traffic conditions during the route planning. Moreover, the LBSs usually suffer from extensive concurrent route planning requests in rush hours, which imposes a pressing need to handle numerous queries in parallel for reducing the response time of each query. However, this issue is also not involved by most existing solutions. We therefore investigate a parallel traffic condition driven route planning model on a cluster of processors. To embed the future traffic condition into the route planning, we employ a GCN model to periodically predict the travel costs of roads within a specified time period, which facilitates the robustness of the route planning model against the varying traffic condition. To reduce the response time, a Dual-Level Path (DLP) index is proposed to support a parallel route planning algorithm with the filter-and-refine principle. The bottom level of DLP partitions the entire graph into different subgraphs, and the top level is a skeleton graph that consists of all border vertices in all subgraphs. The filter step identifies a global directional path for a given query based on the skeleton graph. In the refine step, the overall route planning for this query is decomposed into multiple sub-optimizations in the subgraphs passed through by the directional path. Since the subgraphs are independently maintained by different processors, the sub-optimizations of extensive queries can be operated in parallel. Finally, extensive evaluations are conducted to confirm the effectiveness and superiority of the proposal.

The problem of identifying the k -shortest paths (KSPs for short) in a dynamic road network is essential to many location-based services. Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Very often such services have to process numerous KSP queries over large road networks at the same time, thus there is a pressing need to identify distributed solutions for this problem. However, most existing approaches are designed to identify KSPs on a static graph in a sequential manner (i.e., the (i+1)-th shortest path is generated based on the i-th shortest path), restricting their scalability and applicability in a distributed setting. We therefore propose KSP-DG, a distributed algorithm for identifying k-shortest paths in a dynamic graph. It is based on partitioning the entire graph into smaller subgraphs, and reduces the problem of determining KSPs into the computation of partial KSPs in relevant subgraphs, which can execute in parallel on a cluster of servers. A distributed two-level index called DTLP is developed to facilitate the efficient identification of relevant subgraphs. A salient feature of DTLP is that it indexes a set of virtual paths that are insensitive to varying traffic conditions, leading to very low maintenance cost in dynamic road networks. This is the first treatment of the problem of processing KSP queries over dynamic road networks. Extensive experiments conducted on real road networks confirm the superiority of our proposal over baseline methods.

This paper studies the problem of mining frequent co-occurrence patterns across multiple data streams, which has not been addressed by existing works. Co-occurrence pattern in this context refers to the case that the same group of objects appear consecutively in mul-tiple streams over a short time span, signaling tight correlations be-tween these objects. The need for mining such patterns in real-time arises in a variety of applications ranging from crime prevention to location-based services to event discovery in social media. Since the data streams are usually fast, continuous, and unbounded, existing methods on mining frequent patterns requiring more than one pass over the data cannot be directly applied. Therefore, we propose DIMine and CooMine, two algorithms to discover fre-quent co-occurrence patterns across multiple data streams. DIMine is an Apriori-style algorithm based on an inverted index, while CooMine uses an in-memory data structure called the Seg-tree to compactly index the data that are already seen but have not expired yet. CooMine employs a one-pass algorithm that uses the filter-and-refine strategy to obtain the co-occurrence patterns from the Seg-tree as updates to the streams arrive. Extensive experiments on two real datasets demonstrate the superiority of the proposed approaches over a baseline method, and show their respective ap-plicability in different senarios. 1.

Central to many applications involving moving objects is the task of processing k-nearest neighbor (k-NN) queries. Most of the existing approaches to this problem are designed for the centralized setting where query processing takes place on a single server; it is difficult, if not impossible, for them to scale to a distributed setting to handle the vast volume of data and concurrent queries that are increasingly common in those applications. To address this problem, we propose a suite of solutions that can support scalable distributed processing of k-NN queries. We first present a new index structure called Dynamic Strip Index (DSI), which can better adapt to different data distributions than exiting grid indexes. Moreover, it can be naturally distributed across the cluster, therefore lending itself well to distributed processing. We further propose a distributed k-NN search (DKNN) algorithm based on DSI. DKNN avoids having an uncertain number of potentially expensive iterations, and is thus more efficient and more predictable than existing approaches. DSI and DKNN are implemented on Apache S4, an open-source platform for distributed stream processing. We perform extensive experiments to study the characteristics of DSI and DKNN, and compare them with three baseline methods. Experimental results show that our proposal scales well and significantly outperforms the alternative methods.

Keyword search over relational databases has recently received significant attention. Many solutions and prototypes have been developed. However, due to large memory consumption requirements and unpredictable running time, most of them cannot be applied directly to situations where memory is limited and quick response is required, such as when performing keyword search over databases in mobile devices as part of the OLAP funtionalities. In this paper, we attack the keyword search problem from a new perspective, and propose a cascading top-k keyword search algorithm, which generates supernodes in each step of search instead of computing the Steiner trees as done in many existing approaches. This new algorithm consumes less memory and significantly reduces the response time. Experiments show that the method can achieve high search efficiency compared with the state-of-the-art approaches.