Search

Abstract Background In various fields, searching for the Longest Common Subsequences (LCS) of Multiple (i.e., three or more) sequences (MLCS) is a classic but difficult problem to solve. The primary bottleneck in this problem is that present state-of-the-art algorithms require the construction of a huge graph (called a direct acyclic graph, or DAG), which the computer usually has not enough space to handle. Because of their massive time and space consumption, present algorithms are inapplicable to issues with lengthy and large-scale sequences. Results A mini Directed Acyclic Graph (mini-DAG) model and a novel Path Elimination Algorithm are proposed to address large-scale MLCS issues efficiently. In mini-DAG, we employ the branch and bound approach to reduce paths during DAG construction, resulting in a very mini DAG (mini-DAG), which saves memory space and search time. Conclusion Empirical experiments have been performed on a standard benchmark set of DNA sequences. The experimental results show that our model outperforms the leading algorithms, especially for large-scale MLCS problems.

Social Internet of Things (SIoT) is extended to integrate social networks in the Internet of Things (IoT). SIoT enriches IoT, and thus resource (or service) discovery and consolidation in SIoT becomes an important and challenging problem. In this paper, we represent the SIoT as the heterogeneous information networks (HINs) with multi-typed entities and relations, and resolve this problem from the perspective of cohesive subgraph search. Specifically, given a query node $q$ , we discover a cohesive subgraph containing $q$ from a HIN, where all nodes are of the same type as $q$ and have dense relationships. Yet existing solutions cannot be applied to various HINs, and the result subgraph is not accurate and close enough due to ignoring the connectivity among nodes within the subgraph. To this end, 1) we extend the connectivity with novel meta-path-based edge-disjoint paths to HINs, and propose the $k$ -path connected component ( $k$ -PCC) to measure the cohesiveness of subgraph in HINs; 2) we model the densest connected subgraph containing $q$ as the $k$ -PCC with the maximum connectivity including $q$ , called the Steiner Maximum Path-Connected Subgraph (SMPCS); 3) we develop efficient algorithms based on an index tree for searching the SMPCS. Extensive experiments on four real HINs are conducted to demonstrate the effectiveness and efficiency of our proposed approaches.

COVID-19 virus is raging across the planet. In countries where the epidemic is under control, the main mode of virus transmission is through the transport of imported refrigerated food from epidemic areas. Blockchain is a great way for the government to trace every piece of food. However, the high-performance requirements of the blockchain system for nodes limit its wide application. Several sharding-based blockchain systems have been proposed to solve this limitation. Which blocks should be saved by nodes in the sharding-based blockchain system is a new problem. To solve this problem, the optimized data storage method is proposed in this paper. Five features of block popularity are presented, including the objective feature of a block, the objective feature of the block associated with the node, the historical popularity, the hidden popularity and the storage requirements. Then the ELM classifier is used in the optimized model due to its high performance of training and classification. Finally, the experimental results on synthetic data demonstrate the accuracy and efficiency of the optimized data storage model.

Abstract A time-dependent graph is, informally speaking, a graph structure dynamically changes with time. In such graphs, the weights associated with edges dynamically change over time, that is, the edges in such graphs are activated by sequences of time-dependent elements. Many real-life scenarios can be better modeled by time-dependent graphs, such as bioinformatics networks, transportation networks, and social networks. In particular, the time-dependent graph is a very broad concept, which is reflected in the related research with many names, including temporal graphs, evolving graphs, time-varying graphs, historical graphs, and so on. Though static graphs have been extensively studied, for their time-dependent generalizations, we are still far from a complete and mature theory of models and algorithms. In this paper, we discuss the definition and topological structure of time-dependent graphs, as well as models for their relationship to dynamic systems. In addition, we review some classic problems on time-dependent graphs, e.g., route planning, social analysis, and subgraph problem (including matching and mining). We also introduce existing time-dependent systems and summarize their advantages and limitations. We try to keep the descriptions consistent as much as possible and we hope the survey can help practitioners to understand existing time-dependent techniques.

With the rapid development of mobile Internet and sharing economy, carpooling over real-time taxi-calling service has attracted more and more attention. Many popular taxi-calling service platforms, e.g., didi and Uber, have developed carpooling service to the passengers. Their goal is maximizing overall profit while meeting passengers' convenience and economic benefits. Many researchers have deeply studied this problem. They usually focus on minimizing the total travel distance of drivers or making passengers' cost as fair as possible. However, these efforts ignore the fact that a “high quality” planning path crowed with potential passengers is more valuable than a “low quality” path for both workers and passengers. An effective high quality path planning algorithm is more desired. In this paper, we propose an efficient framework, named PPVF(short for path prediction and verification-based framework) for path planning over the road network. We first select a group of high quality paths from the historical transaction record set and manage them by proposing a novel index named PCR-Tree. Then we use them for supporting the path planning. Furthermore, we propose a searching and verification-based algorithm for further improving the path planning quality. Theoretical analysis and extensive experimental results demonstrate the effectiveness of the proposed algorithms.

Location search and recommendation have received significant attention in recent years. To protect the users' privacy, we propose and study a novel privacy-protected route-based spatial-textual location (PPRSTL) query in road networks. Given a set of locations O with the textual description, a query route q with a set of query keywords to describe user's preference, the PPRSTL query finds the location with the highest spatial-textual similarity to the query route q. We believe that such type of query is very useful in many mobile applications such as location recommendation and discovery, and location-based services in general. The problem is challenging due to three reasons: (1) how to model the spatial and textual similarity practically; (2) how to constrain the search space in a comparatively small range in the spatial and textual domains, and; (3) how to protect the users' privacy when returning the query results. To overcome these challenges, we define a boolean spatial-textual measure to evaluate the similarity in the spatial and textual domains, and a two-phase search mechanism to protect users' privacy. We develop two expansion search algorithms that follow the filter-and-refinement paradigm, to compute the queries efficiently. Two pairs of upper and lower bounds are defined to prune the search space effectively. In addition, we adopt an expansion center selection method to further enhance the query efficiency. Finally, we conduct extensive experiments on real and synthetic spatial data sets to verify the performance of the developed algorithms.

Driven by the advance of positioning technology and the tremendous popularity of location-based services, location-record data have become unprecedentedly available. Publishing such data is of vital importance to the advancement of a wide spectrum of applications, such as marketing analysis, targeted advertising, and urban planning. However, the data collection may pose considerable threats to the individuals privacy. Local differential privacy (LDP) has recently emerged as a strong privacy standard for collecting sensitive information from users. Due to the inherent high dimensionality, it is particularly challenging to publish the location-record data under LDP. In this paper, we propose LDPart, a probabilistic top-down partitioning algorithm to effectively generate a sanitized location-record data. Our approach employs a carefully designed partition tree model to extract essential information in terms of location records. Furthermore, it also makes use of a novel adaptive user allocation scheme and a series of optimization techniques to improve the accuracy of the released data. The extensive experiments conducted on real-world datasets demonstrate that the proposed approach maintains high utility while providing privacy guarantees.

Outsourced data, as significant service offered by the cloud service provider (CSP), can effectively facilitate the data owner (DO) overcoming the storage limitations on massive data. To ensure the availability of data, DO usually outsources the data replications to multiple CSPs (multi-CSPs) and utilizes a third party metadata management (TPMM) to dominate the metadata of the corresponding replications. However, during the outsourced procedures, DO can hardly confirm the confidence of the TPMM who may take some malicious behaviors to affect the reliability of data. Thus, DO inevitably faces data security issues caused by the over-reliance on the semi-trusted TPMM to manage the metadata of replications. In this paper, we focus on the problem of reliable outsourced data service among multi-CSPs in untrusted environment, that is, how to reliably store and verify the metadata of the data replications in untrusted multi-CSPs environment. To address the problem, we use the novel blockchain technology as a medium to build a trusted outsourced service platform. Moreover, we fully consider the innovative characteristics of blockchain including decentralized architecture, redundancy storage, collective maintenance, and tamper resistant to ensure the data cannot be changed maliciously. We first design a blockchain-based outsourced service framework for storing data replications in untrusted environment, which contains three key layers, that is, storage layer, verification layer, and blockchain layer. Then, we devise a novel concept of verification peer (VP) for maintaining metadata stored by a form of blockchain, and each of which holds the entire blockchain locally to prevent metadata from being maliciously tampered with. Finally, based on the proposed model, we introduce a collaborative algorithm invoked by VPs to store and verify the metadata of replications. We present a completed analysis and conduct extensive experiments on multi-CSPs scenario. The evaluation results demonstrate that our proposed approach achieves superior performance.

Blockchain has received great attention in academia and industry due to its decentralization and immutability. From the perspective of transaction processing, blockchain is a distributed shared ledger and database with the characteristics of decentralization, traceability, and transparency. These features ensure the security of blockchain’s reliability. However, because a blockchain network requires complex consensus verification between users, it causes problems such as a high cost of data exchange and a low system throughput. Such problems are aggravated when executing a cross-chain transaction, as it is particularly important to ensure the atomicity and isolation of transactions across the blockchain. Considering this, in this paper, we propose the cross-chain transaction processing flow of EOVPC and efficient transaction processing based on version control. Different from the existing cross-chain transaction approaches based on locking, we propose optimistic approaches in which the updated data can be used immediately, with a rolling back procedure that guarantees atomicity. We conducted extensive experiments, which show that our approaches can improve the throughput and success rate significantly.

In recent years, Event Based Social Networks (EBSNs) appear in people’s daily life and are becoming increasing popular. In EBSNs, one typical task is to make personalized plans for users. Existing studies only consider the preference of users. They make plans by selecting interesting events for users. However, for organizers of events, they also would like more high-quality users to participate in their events, which may make the events more exciting. Existing studies are user-centered and ignore the requirement of organizers. What is more, organizers are allowed to modify their events dynamically before they are held. The platforms should be able to dynamically adjust the schedules of users. Therefore, we identify a new Incremental Bilateral Preference Stable Planning (IBPSP) problem over EBSNs and propose several solutions to deal with different situations. We conduct extensive experiments to verify the efficiency and effectiveness of the proposed algorithms.