Bipartite graphs are widely used to model relationships among diverse entities in domains such as gene co-expression networks, collaboration networks, and customer-product interactions. A fundamental problem in analyzing bipartite graphs is the maximum balanced biclique (MBBC) search, which identifies the maximum fully connected subgraph with an equal number of vertices on both sides in the given bipartite graph. Despite its utility, the MBBC model suffers from practical limitations: its strict all-to-all connectivity and exact size-equality requirements make it impractical for noisy, incomplete real-world bipartite data. To overcome these limitations, we propose the maximum balanced k-biplex (MBKBP) model, which relaxes the stringent requirements of MBBC. In MBKBP, each vertex is allowed to miss up to k neighbors on the opposite side of the bipartite graph, and a user-defined parameter$\delta$ensures approximate balance between the two vertex sets. This flexibility enhances robustness to noise, accommodates incomplete data, and broadens the model's applicability. To compute the MBKBP in a given bipartite graph, a baseline approach involves enumerating all maximal balanced k-biplexes and identifying the largest one. However, as confirmed by our experiments, this approach is computationally inefficient. To address this challenge, we introduce the concept of$(z_{L},\ z_{R})$search space and propose a new framework to compute the MBKBP. By generating a series of smaller$(z_{L)}z_{R})$search spaces, our framework significantly reduces the number of maximal k-biplexes that need to be explored. Additionally, we leverage the$\delta$-balance property to refine the search spaces further and develop three categories of pruning rules to minimize computational overhead. Extensive experiments on real-world bipartite graphs demonstrate that our algorithm achieves up to three orders of magnitude speedup compared to baseline approache, showcasing its efficiency and practicality for bipartite graph analysis.

Abstract Time series data are pervasive, with a multitude of applications across various fields including science, industry, Entertainment, medicine, and biology. These data sets often encompass large volumes of information. In the context of databases containing time series data, the increasing frequency of query tasks, such as (i) point queries, (ii) range queries, and (iii) top-k similarity queries, necessitates the enhancement of query processing efficiency. The question thus arises: how can the efficiency of these data processing tasks be enhanced? The solution is twofold. Firstly, dimensionality reduction algorithms can be employed to reduce the complexity of the data. Secondly, we can focus on the optimization of query algorithms. Consequently, based on these ideas, in this paper, we present an optimized framework for efficiently executing time series queries in the openGauss database, called TSQ. The framework is composed of two primary components: a dimensionality reduction (DR) module and a similarity query (SQ) module. The DR module incorporates several algorithms based on space-filling curves, which, through our enhancements, are capable of handling both high and low precision time series data more effectively. In the context of the SQ module, we employ two main optimization strategies, Early Abandoning and Sliding Window, to greatly improve the efficiency of similarity queries. Experimental results on four real-world time series datasets show that our framework not only optimizes general query tasks but also significantly enhances the efficiency of similarity queries.

Spatial databases play a vital role in a number of applications ranging from geographic information systems to location-based services. Application tasks typically access underlying spatial data to answer queries. However, non-experts lack the expertise necessary for formulating spatial queries. To fill in this gap, we propose an effective framework that translatesnaturallanguage queries overspatialdata into executable database queries, called NALSpatial. The framework consists of two core phases: (i)natural language understandingand (ii)natural language translation. Phase (i) extracts key entity information, comprehends the query intent and determines the query type by employing natural language processing techniques and deep learning algorithms. The key entities and query type are passed to phase (ii), which makes use of entity mapping rules and structured language models to construct executable database queries. NALSpatial supports dealing with five types of queries including (i)basic queries (e.g. distance and area), (ii)range queries, (iii)nearest neighbor queries, (iv)spatial join queriesand (v)aggregation queries. We develop NALSpatial in an open-source extensible database system SECONDO. Extensive experiments show that NALSpatial on average achieves response time of about 2.5 seconds, translatability of 95% and translation precision of 92%, outperforming three state-of-the-art methods.

Identifying disinformation from online social media is crucial for maintaining a credible cyberspace. Although features from the content and propagation topology are widely exploited by existing studies to distinguish disinformation from normal ones, they are becoming less effective as content can be intentionally written to mislead readers and topological features are difficult to be extracted due to the high variance and diversity of reposting trees. Moreover, related works mainly focus on modeling the complete information propagation event, ignoring the staged evolution patterns along with propagation, which may also degrade the detection performance. In this paper, we conceive and implement a novel framework called DMPS for identifying disinformation, which Dynamically Models diverse topological structures of reposting trees as well as the textual content streams across different Propagation Stages. In particular, DMPS learns expressive representations of the structural features via meta-trees and extracts sequential features of the content for intra-stage modeling, then it captures temporal dependencies for inter-stage modeling. The whole framework is optimized in a binary classification manner. Experiments based on multilingual social media datasets validate the effectiveness and superiority of DMPS over state-of-the-art models. We believe that this study can provide insights for crisis management in response to disinformation in social network campaigns.

Spatial databases play a vital role in many applications that access spatial data via appropriate queries. However, most application users lack the expertise necessary for formulating spatial queries. To fill in this gap, we propose an effective framework called NALSpatial that translates natural language queries over spatial data into executable database queries. NALSpatial consists of two core phases. The natural language understanding phase extracts key entity information, comprehends the query intent and determines the query type. The key entities and query type are passed to the subsequent natural language translation phase, which employs entity mapping rules and structured language models to construct executable database queries accordingly. We implement NALSpatial on the open-source extensible database system SECONDO to support range queries, nearest neighbor queries, spatial joins and aggregation queries. Extensive experiments show that NALSpatial on average achieves response time of about 2.5 seconds, translatability of 95% and translation precision of 92%, outperforming state-of-the-art natural language transformation methods.

Given a set of spatio-temporal objects, a top-k window aggregate query reports top-k tuples that are ordered with respect to the number of objects during a given time interval and within a spatial range. For example, when analyzing traffic density in a city, one wishes to retrieve top-k time intervals in a certain area that are decreasingly ordered according to the number of vehicles passing by. As simply performing sequential scan over all objects is a costly procedure, an index structure is typically built to enhance the query performance. A crucial step during the evaluation is to determine the number of objects in an arbitrary node, called coverage number sequence. This is a challenging task since objects appear and disappear at different time points such that the number of objects in the query node changes over time. Also, as a hierarchical index structure, the value of a node at high level is achieved by performing the aggregation over its child nodes. Simply enumerating all objects rooted in the query node suffers from performance issues mainly due to (i) traversing the sub-tree to retrieve a large number of time points and (ii) repeatedly performing the aggregation at certain time points. We propose an efficient approach to solve the performance issue for both R-tree and Octree and support updating for new arrival data objects being inserted into the index. Our approach outperforms alternative methods in general according to a thorough analysis on the complexity. Coverage number sequences as well as proposed optimization techniques are utilized to enhance the performance of window aggregate queries. We confirm the superiority of our approach over alternative methods by performing a comprehensive experimental evaluation over large real datasets in a database system.

Spatial databases have a wide range of applications such as urban planning, engineering management and data visualization for epidemic investigation. The number of users in spatial databases becomes significantly large due to the increasing demand of application requirements. Users send their queries and analysis tasks to the system and receive the corresponding feedback. However, there is a lack of research on natural language interfaces in spatial databases. In this demo, we present NALSD, a natural language transformation system designed specifically for spatial data queries. NALSD comprises two core components: (i) natural language understanding and (ii) natural language translation. The system enables automatic translation of natural language query on spatial data into executable language for the underlying database, and supports range query, nearest neighbor query and spatial join query. We demonstrate how to obtain database executable language and visualize query results based on the SECONDO system.

A multi-attribute trajectory consists of a spatio-temporal trajectory and a set of descriptive attributes. Such data enrich the representation of traditional spatio-temporal trajectories to have comprehensive knowledge of moving objects. Range query is a fundamental operator over multi-attribute trajectories. Such a query contains two predicates, spatio-temporal and attribute, and returns the objects whose locations are within a distance threshold to the query trajectory and attributes contain expected values. There are different execution plans for answering the query. To enhance the capability of a trajectory database, an optimizer is essentially required to (i) accurately estimate the cost for alternative query strategies in terms of disk accesses, (ii) build a decision-making module that automatically sorts the data in an appropriate way and selects the optimal query plan, and (iii) update the analytical models when new trajectories are arrived. The cost model supports both uniform and non-uniform spatio-temporal data distribution and incorporates attribute distribution. The optimizer is fully developed inside a database system kernel and comprehensively evaluated in terms of accuracy and effectiveness by using large real and synthetic datasets.

Emerging applications over spatio-temporal trajectories require representing the data from diverse aspects. We study multi-attribute trajectories each of which consists of a sequence of time-stamped locations and a set of attributes characterizing diverse aspects. We investigate continuous range queries over multi-attribute trajectories. Such a query returns trajectories whose attributes contain expected values and whose locations are always within a distance threshold to the query trajectory during the entire overlapping time period. To efficiently answer the query, an optimal method of partitioning the trajectories is proposed and an index structure is developed to support the combined search using both spatio-temporal parameters and attribute values. Query algorithms and auxiliary structures are developed, accompanied with optimization strategies and thorough theoretical analysis. Using both real and synthetic datasets, we carry out comprehensive experiments in a prototype database system to evaluate the efficiency and scalability of our designs. The experimental results show that our approach outperforms six alternative approaches by a factor of 5-50x on large datasets.

Abstract Knowledge graph has wide applications in the field of computer science. In the knowledge service environment, the information is large and explosive, and it is difficult to find knowledge of common phenomena. The urban traffic knowledge graph is a knowledge system that formally describes urban traffic concepts, entities and their interrelationships. It has great application potential in application scenarios such as user travel, route planning, and urban planning. This paper first defines the urban traffic knowledge graph and the star subgraph query of the urban traffic knowledge graph. Then, the road network data and trajectory data are collected to extract the urban traffic knowledge, and the urban traffic knowledge graph is constructed with this knowledge. Finally, a star subgraph query algorithm on the urban traffic knowledge graph is proposed. The discussion of the star subgraph query mode gives the corresponding application scenarios of our method in the urban traffic knowledge graph. Experimental results verify the performance advantages of this method.

The rise of GPS-equipped mobile devices has led to the emergence of big trajectory data. The collected raw data usually contain errors and anomalies information caused by device failure, sensor error, and environment influence. Low-quality data fails to support application requirements and therefore raw data will be comprehensively cleaned before usage. Existing methods are suboptimal to detect GPS data errors and do the repairing. To solve the problem, we propose a framework called GPSClean to analyze the anomalies data and develop effective methods to repair the data. There are primarily four modules in GPSClean : (i) data preprocessing, (ii) data filling, (iii) data repairing, and (iv) data conversion. For (i), we propose an approach named MDSort (Maximum Disorder Sorting) to efficiently solve the issue of data disorder. For (ii), we propose a method named NNF (Nearest Neighbor Filling) to fill missing data. For (iii), we design an approach named RCSWS (Range Constraints and Sliding Window Statistics) to repair anomalies and also improve the accuracy of data repairing by mak7ing use of driving direction. We use 45 million real trajectory data to evaluate our proposal in a prototype database system SECONDO. Experimental results show that the accuracy of RCSWS is three times higher than an alternative method SCREEN and nearly an order of magnitude higher than an alternative method EWMA.

In recent years, the rise of mobile devices has led to the emergence of big trajectory data. Raw GPS records usually include many errors and abnormal information due to equipment error and environment influence. To provide high quality data for applications, an important task is to efficiently detect and effectively repair different types of anomalies in GPS records. In this demo, we develop a tool called GPSClean to detect and repair abnormal GPS data. The tool well supports repairing five kinds of anomalies in GPS data and is developed in an open source database system for managing trajectory data. We demonstrate GPSClean by using large real GPS data.

Moving objects databases (MODs) have been extensively studied due to their wide variety of applications including traffic management, tourist service and mobile commerce. However, queries in natural languages are still not supported in MODs. Since most users are not familiar with structured query languages, it is essentially important to bridge the gap between natural languages and the underlying MODs system commands. Motivated by this, we design a natural language interface for moving objects, named NALMO. In general, we use semantic parsing in combination with a location knowledge base and domain-specific rules to interpret natural language queries. We design a corpus of moving objects queries for model training, which is later used to determine the query type. Extracted entities from parsing are mapped through deterministic rules to perform query composition. NALMO is able to well translate moving objects queries into structured (executable) languages. We support four kinds of queries including time interval queries, range queries, nearest neighbor queries and trajectory similarity queries. We develop the system in a prototype system SECONDO and evaluate our approach using 240 natural language queries extracted from popular conference and journal papers in the domain of moving objects. Experimental results show that (i) NALMO achieves accuracy and precision 98.1 and 88.1, respectively, and (ii) the average time cost of translating a query is 1.47s.

In recent years, natural language processing has received increasing attention in the field of database. The main task is to bridge the gap between non-expert users who are not familiar with formal query languages and the system executable language. In this demo, we develop a tool called NLMO that performs the translation of NL questions to executable query languages over moving objects databases. The tool well supports spatio-temporal range queries and nearest neighbor queries. We demonstrate the tool by reporting executable languages translated from the natural language input.

Due to the widespread use of GPS-enabled devices such as smartphones, the research field of moving objects databases has been quite active in the past decade. Human movements are recorded, managed and analyzed for a plethora of applications. In this demo, we introduce a toolbox named IMO to simulate and query infected moving objects. This is primarily motivated by COVID-19 virus pandemic recently. We model the spreading behavior to demonstrate when and where people are infected. The protection policy is simulated such that one can see the isolation and self protection effects such as human movement restriction and the wearing of masks. Optimization techniques are developed to enhance the performance, including data storage, data partition and index structures. This is not a standalone software but a toolbox embedded in SECONDO, an open source and extensible database system. To the best of our knowledge, simulating and querying infected objects are not supported in existing moving objects prototype systems. Demo attendees can conveniently pose their queries and adjust parameters in the interface and the system will visualize the result after only a short delay.

A multi-attribute trajectory consists of a sequence of time-stamped locations and a set of attributes that characterize diverse aspects of the corresponding moving object. In this paper, we study continuous range queries over multi-attribute trajectories. Such a query returns the objects whose attributes contain expected values and whose locations are always within a distance threshold to the query trajectory during the entire overlapping time period. To efficiently answer the query, an optimal method of partitioning the trajectories is proposed and an index structure is developed to support the combined search of spatio-temporal parameters and attribute values. We provide a general solution that is able to process multi-attribute trajectories as well as traditional trajectories without attributes. We carry out comprehensive experiments in a prototype database system to evaluate the efficiency and scalability of our designs. The experimental results show that our approach outperforms five alternative approaches by a factor of 5-50x on large datasets.

Shortest path queries between two points on road networks are fundamental operators for many applications. In spite of extensive research having been conducted on processing two static points, little attention has been paid to deal with two moving objects on road networks. This is a challenging issue because the shortest path varies when the locations of objects change. To solve the problem, we develop a system with the functionality that efficiently returns a group of shortest paths at different time intervals. We aim to continuously report the shortest path between two moving objects. The variable paths are visualized in the user interface such that one can be clearly noticed how the path changes over time. Real datasets Nanjing roads are used in the demonstration. The technique can be used for analyzing historical movements of objects.

The research field of moving objects has been quite active in the past 20 years. The recording of position data becomes easy and huge amounts of mobile data are collected. Moving objects databases represent time-dependent objects and support queries with spatial and temporal constraints. In this paper we provide the vision of a multi-model and intelligent moving objects database. The goal is to enhance the data management of moving objects by providing extensive data models for different applications and fusing artificial intelligence techniques. Toward this goal, we propose how to develop corresponding modules and integrate them into the system to achieve the next-generation moving objects database.

Motivated by the trend of providing comprehensive knowledge about trajectory data, we study multi-attribute trajectories each of which contains a sequence of time-stamped locations and a set of characteristic attributes. This enriches the data representation by providing a comprehensive description of moving objects and thus enables new types of queries on moving object trajectories. In this paper, we consider answering range queries that return trajectories (i) containing particular attribute values and (ii) passing a certain area during the query time. We integrate standard trajectories and attributes into one unified framework and propose an index structure as well as the query algorithm. The structure is general and flexible in terms of handling both multi-attribute trajectories and standard trajectories, answering a range of queries and supporting update-intensive applications. The evaluation is conducted in a prototype database system and experimental results demonstrate that our method outperforms alternative methods by a factor of 3-10 on a data set of one million real trajectories and synthetic attribute values.

The widespread use of GPS-enabled devices has led to huge amounts of trajectory data. In addition to location and time, trajectories are associated with descriptive attributes representing different aspects of real entities, called multi-attribute trajectories. This comes from the combination of several data sources and enables a range of new applications in which users can find interesting trajectories and discover potential relationships that cannot be determined solely based on GPS data. In this demo, we provide the motivation scenario and introduce a system that is developed to integrate standard trajectories (a sequence of timestamped locations) and attributes into one unified framework. The system is able to answer a range of interesting queries on multi-attribute trajectories that are not handled by standard trajectories. The system supports both standard trajectories and multi-attribute trajectories. We demonstrate how to form queries and animate multi-attribute trajectories in the system. To our knowledge, existing moving objects prototype systems do not support multi-attribute trajectories.

Assume that a database stores a set of intervals, each of which defines start and end points, a weight and a type. Typed intervals enrich the data representation and support applications involving different kinds of data intervals. Given a query time and type, the system reports k intervals that intersect the time, contain the type and have the largest weight. We develop a new structure to manage typed intervals based on the standard interval tree and propose efficient query algorithms. Experiments with synthetic datasets are conducted to verify the performance advantage of our solution over alternative methods.

In this paper, we introduce a benchmark called GMOBench that aims to evaluate the performance of a database system managing moving objects in different environments. In real life, people's movement can cover several environments rather than one, for example, Indoor → Walk → Bus. Consequently, the complete trip needs to be managed by a database system in order to support novel queries. Since existing methods are limited to one environment, new technologies are developed in a database system that is able to manage generic moving objects. A meaningful analysis and evaluation of such a system necessitates a comprehensive benchmark. GMOBench is settled in a realistic scenario which comprises (1) a data generator with the capability of creating a scalable set of trips representing the complete movement of humans (both indoor and outdoor); (2) a set of carefully designed and benchmark queries. We create the benchmark data in such a way that the dataset can mirror important characteristics and real world distributions of human mobility. We perform an extensive experimental study on comprehensive datasets to evaluate the performance of the system. The results demonstrate the effectiveness and efficiency of our approaches.

Moving objects representing movement in all real world environments (e.g., road network, bus network, indoor) should be managed in a database system, for the reason that a person's trip can cover several environments rather than one. GMOD (Generic Moving Objects Database) is a database system to manage moving objects that (1) travel through different environments; (2) contain multiple transportation modes such as Car → Walk → Indoor. To evaluate the performance of GMOD, one needs a comprehensive and scalable dataset consisting of all available environments and moving objects. Due to the difficulty of gaining real datasets, in this paper we present a tool called MWGen that creates the overall space for moving objects, composed of the following environments: road network, bus network, metro network, pavement areas and indoor. Based on roads, all outdoor environments are created. The indoor environment consisting of a set of buildings is established from public floor plans. Moving objects are generated based on trip planning where a navigation algorithm through different environments is developed. We are able to produce moving objects integrated with multiple transportation modes. In addition, trip planning in a single environment is also available, e.g., shortest path for pedestrians, indoor navigation. The generated data, including all infrastructures and moving objects, are managed by GMOD. We conduct an extensive performance study to evaluate MWGen on two real road datasets and a set of public floor plans.

In this demonstration, we introduce a system that is able to manage moving objects in all real world environments, e.g., road network, bus network and indoor. The complete trip of a person is managed by the system such as Walk, Car, Walk , and Indoor , where the precise locations of both outdoor and indoor movements are represented. Trajectories located in several environments are integrated into the same framework. The system supports the shortest path searching for start and end locations being in different environments, for example, from a room to a bus stop. A comprehensive and scalable set of moving objects is generated to simulate human movement in practice. Optimization methods are developed to efficiently answer novel queries regarding transportation modes and mobile environments. Most of these queries are not supported by existing methods because of the limitation of data representation.

Moving objects with multiple transportation modes (e.g., Car, Bus, Walk) can be represented by the reference method where the location is mapped to infrastructure objects, e.g., roads, buses, pavements. A scalable dataset is required to evaluate the performance of a database system managing these moving objects. To produce multimodal moving objects, infrastructure objects are essentially needed. Due to the major challenge of gaining real datasets, in this demonstration we propose a method create these infrastructure objects for different environments including pavement areas, bus network and indoor just from a given road network and some floor plans. An indoor viewer is also implemented in a database system for visualizing 3D indoor moving objects and trajectories. The work is to be used for evaluating the performance of a database system managing generic moving objects.