Abstract Keyword search, which identifies transactions associated with specified keywords across historical blocks, is a critical query type in blockchain analytics. However, existing approaches, such as on-chain indexing and off-chain synchronization, may lead to significant space overhead or challenges in maintaining data freshness. To address these challenges, we propose BlockSketch, a novel probabilistic data structure (PDS) that adopts a differentiated encoding strategy, aimed at resolving the trade-off between query performance and storage overhead in blockchain indexing. BlockSketch features a hierarchical filtering architecture that combines Bloom filters and Sketches within a binary tree framework, enabling dynamic structural maintenance. Keywords are categorized as “hot” or “cold” based on their on-chain frequency and encoded into the most suitable component to achieve resource-efficient storage and accurate querying. In addition, BlockSketch integrates two distinct query rules, namely “level-down” and “jump,” to balance query accuracy and efficiency when processing keywords with varying frequencies. Furthermore, we enhance the query efficiency of BlockSketch by merging inefficient lower-level nodes into more compact ones and pruning redundant node checks during query execution. Extensive experiments on a real-world dataset demonstrate that BlockSketch delivers up to 73% faster query processing, achieves 44.56% of the average false positive rate of baselines at low multiplicity and as low as 1.52% at high multiplicity, and saves 79% in storage compared to state-of-the-art methods.

Existing blockchain systems can quickly respond to verifiable primary key queries based on authenticated indexes. However, many blockchain applications also require high-performance queries on non-primary keys. For example, traders query NFT or tokenized RWA with certain features, e.g., type and return. Therefore, it necessitates authenticated secondary indexes to support efficient verifiable queries on non-primary keys. However, the existing approach to authenticated index design that couples index and authenticated digest together does not adapt well to the phased nature of non-primary key queries, making the most time-consuming process of commitment generation severely block the query process. In this study, we propose the first authenticated secondary index MEST for verifiable non-primary key queries. MEST decouples the data index and authenticated digest, which can parallelize commitment generation on the secondary index and the query processing on the primary index, thus greatly reducing the latency of the non-primary key query. Furthermore, we adopt an Extendible Hash Table to index data and propose a Merkle Growth Tree to generate commitment, which can dynamically adapt to the rapid growth of data and the skew in data access pattern. Extensive experiments on both synthetic and real datasets demonstrate that MEST improves throughput by 3.17×, reduces latency by 59%, and exhibits better scalability than baselines.

Smart contracts have expanded blockchain applications, but permissioned blockchain systems face severe through-put challenges, especially with the increasing complexity of nested contract transactions. These transactions, involving cross-contract interactions and deep call chains, intensify execution conflicts and rollback overhead, ultimately limiting parallelism. We propose Loom, a deterministic execution framework that enhances the efficiency of nested contract transactions. Loom employs snapshot-based concurrent pre-execution to decompose transactions into fine-grained subtransactions. To reduce rollback overhead, it introduces a two-phase rollback algorithm to minimize computational redundancy and fine-grained rescheduling to improve subtransaction-level parallelism during re-execution. Additionally, a multi-phase parallelism mechanism optimizes resource utilization across transaction blocks. Experimental results show that Loom achieves 6.1 × to$10.2\times$higher throughput while reducing rollback overhead by 89.9% to 98.4%, significantly outperforming state-of-the-art solutions.

Anomaly detection has emerged as a prominent research area with extensive exploration across various applications. Existing methods predominantly focus on detecting all anomalies exhibiting unusual patterns, however, they overlook the critical need to prioritize the detection of target anomaly categories (anomalies of primary interest) that could pose significant threats to various systems. This oversight results in the excessive involvement of valuable human labor and resources in dealing with non-target anomalies (that are of lower interest). This work is focused on target-class anomaly detection, which entails overcoming several challenges: (1) deficient prior information regarding non-target anomalies and (2) an elevated false positive rate caused by the presence of non-target anomalies. Thus, we introduce a novel semi-supervised model, called TargAD, which leverages a few labeled target anomalies, along with potential non-target anomaly candidates and normal candidates selected from unlabeled data. By introducing a novel loss function, TargAD effectively maximizes the distributional differences among normal candidates, target anomalies, and non-target anomaly candidates, leading to a significant improvement in detecting target anomalies. Furthermore, when confronted with novel non-target anomaly scenarios, TargAD maintains its accuracy in detecting target anomalies. We conducted extensive experiments, the results of which demonstrate that TargAD outperforms eleven state-of-the-art baselines on a real-world dataset and three publicly available datasets, with average AUPRC improvements of 5.9%-24.8%, 9.2%-57.8%, 2.7%-71.3%, and 2.0%-70.3%, respectively.

Permissioned blockchain, as a multi-replica system, has its performance significantly affected by both the consensus protocol and the transaction execution protocol. Currently, there are many works optimizing the consensus or transaction execution of permissioned blockchain. However, existing works mainly focus on optimizing either consensus or transaction execution independently, lacking a holistic perspective. Based on this observation, we consider optimizing the permissioned blockchain from the holistic optimization perspective. Specifically, we heuristically design a transaction execution protocol TELL towards leaderless consensus to achieve collaborative optimization of consensus and transaction execution. Leaderless consensus is essentially a parallel running of multiple leader-based consensus instances, based on this characteristic, TELL pertinently designs intra-instance execution and inter-instances merging protocols. Additionally, we devise a novel State Hash Table (SHT) to record transactions' accessed states, so as to improve conflict serialization efficiency. Besides, we propose Dynamic Commitment Epoch (DCE) to adapt to instances' running status and decrease blocks' committing latency. Experimental results shows that compared with existing works, TELL further improves the performance of permissioned blockchain.

Today, blockchain ledgers utilize concurrent deterministic execution schemes to scale up. However, ordering fairness is not preserved in these schemes: although they ensure all replicas achieve the same serial order, this order does not always align with the fair, consensus-established order when executing smart contracts with runtime-determined accesses. To preserve ordering fairness, an intuitive method is to concurrently execute transactions and re-execute any order-violating ones. This in turn increases unforeseen conflicts, leading to scaling bottlenecks caused by numerous costly aborts under contention. To address these issues, we propose Spectrum, a novel deterministic execution scheme for smart contract execution on blockchain ledgers. Spectrum preserves the consensus-established serial order (so-called strict determinism) with high performance. Specifically, we leverage a speculative deterministic concurrency control to execute transactions in speculation and enforce an agreed-upon serial order by aborting and re-executing any mis-speculated ones. To overcome the scaling bottleneck, we present two key optimizations based on speculative processing: operation-level rollback and predictive scheduling, for reducing both the overhead and the number of mis-speculations. We evaluate Spectrum by executing EVM-based smart contracts on popular benchmarks, showing that it realizes fair smart contract execution by preserving ordering fairness and outperforms competitive schemes in contended workloads by 1.4x to 4.1x.

Warehouse dwell time (WDT) of a truck is a critical metric for evaluating plant-logistics efficiency, including the time of the truck's queuing outside and loading inside the warehouse. ButWDTprediction is challenging as it is affected by diverse factors like loading distinct types and weights of the cargoes, and varying amounts of loading tasks in different time slots. Besides, each trucks'WDTis transitively influenced by its preceding trucks' loading time in the queue. In this paper, we propose a multi-block dwell time prediction framework consisting ofLSTMmodel and self-attention mechanism, called SDP. In view of that low performance ofSDPbrought by sparse loading data of some warehouses, we further design a multi-source adaptation based block-to-block transfer learning module. We present a warehouse similarity measurement based on loading tasks allocated and loading ability of the warehouses, according to which we enhance overall prediction performance by learning from high-performanceWDTprediction models of similar warehouses. Experimental results on a large-scale logistics data set demonstrate that our proposal can reduce Mean Absolute Percentage Error (MAPE) by an average of 10.0%, Mean Absolute Error(MAE) by an average of 16.5%, and Root Mean Square Error(RMSE) by an average of 17.0% as compared to the baselines.

Permissioned blockchains are being widely applied to solve the trust problem in enterprise collaboration. However, most of these systems suffer from low throughput and flexibility lacking issues. In this paper, we present a blockchain system SChain with scalable concurrent execution based on a flexible architecture. SChain separates the functionality of a complete "node" into three sub-functions and assigns them to different peers within every organization. Then each organization can scale each sub-function flexibly with no need for negotiation between organizations. Based on this architecture, SChain explores scalable concurrent execution from two levels. First, SChain takes the advantage of multiple peers to execute transactions collectively, while promising they make the same results as one peer does serially. Second, SChain enables concurrent transaction execution across blocks to utilize the resources of peers fully, breaking up the block-by-block process manner, based on a pipelined workflow. The extensive evaluation results demonstrate that SChain significantly outperforms the serial execution and other competing systems-level approaches.

The emergence of digital asset applications, driven by Web 3.0 and powered by blockchain technology, has led to a growing demand for blockchain-specific graph analytics to unearth the insights. However, current blockchain data analytics systems are unable to perform efficient ad-hoc graph analytics over both live and past time windows due to their inefficient data synchronization and slow graph snapshots retrieval capability. To address these issues, we propose ChainDash, a blockchain data analytics system that dedicates a highly-parallelized data synchronization component and a retrieval-optimized temporal graph store. By leveraging these techniques, ChainDash supports efficient ad-hoc graph analytics of smart contract activities over arbitrary time windows. In the demonstration, we showcase the interactive visualization interfaces of ChainDash, where attendees will execute customized queries for ad-hoc graph analytics of blockchain data.

Permissioned blockchain is increasingly being used as a collaborative platform for sharing data. However, current blockchain-based data sharing is unable to balance privacy pro-tection and query functionality, limiting its application scenarios. Order-preserving encryption/encoding (OPE) allows encrypting data to prevent privacy leakage while still supporting efficient order-oriented queries on ciphertexts. But existing OPE schemes are constrained by limited use cases and inherent performance limitations that make them difficult to be adopted by permissioned blockchain where performance is a major concern. In this paper, we present BlockOPE, an efficient OPE scheme designed around the first study integrating OPE into blockchain systems. By supporting parallel processing with a conflict-reducing design, we argue that BlockOPE is feasible for permissioned blockchain, achieving orders-of-magnitude performance improvement while preserving the ideal OPE security. Additionally, we improve query processing by leveraging an adaptive lightweight client cache. Extensive experiment results and theoretical analysis illustrate the practicability of our approach.

The current blockchain system suffers from serious scalability bottleneck, which greatly limits the application in large-scale. Furthermore, with the emergence of high-throughput consensus algorithms in permissioned blockchain, how to efficiently execute smart contracts becomes a critical challenge. To solve this issue, a two-phase concurrent execution mechanism has been adopted recently, where the primary executes a batch of transactions concurrently in the first phase, then the rest replays them in the second phase to achieve consistency. However, these works only enable intra-node concurrency, not inter-node concurrency. This demonstration showcases SEFrame, a novel execution framework for smart contracts of permissioned blockchain to achieve intra- and inter-node concurrency with the confidentiality guarantee of Intel Software Guard Extensions (SGX). We use real-time dashboards containing the output of SEFrame, which allows attendees to interactively explore how SEFrame achieves efficient inter- and intra-node concurrency.

Although the emergence of the programmable smart contract makes blockchain systems easily embrace a wide range of industrial services, how to execute smart contracts efficiently becomes a big challenge nowadays. Due to the existence of Byzantine nodes, existing mature concurrency control protocols in database cannot be employed directly, since the mechanism of executing smart contracts varies a lot. Furthermore, even though smart contract execution follows a two-phase style, i.e., the primary node executes a batch of smart contracts in the first phase and the validators replay them in the second phase, existing parallel solutions merely focus on the optimization for the first phase, rather than the second phase. In this paper, we propose a novel two-phase concurrency control protocol to optimize both phases for the first time. First, the primary executes transactions in parallel and generates a transaction dependency graph with high parallelism for validators. Then, a graph partition algorithm is devised to divide the original graph into several sub-graphs to preserve parallelism and reduce communication cost remarkably. Finally, we propose a deterministic replay protocol to re-execute the primary’s parallel schedule concurrently. Moreover, this two-phase protocol is further optimized by integrating with PBFT. Theoretical analysis and extensive experimental results illustrate that the proposed scheme outperforms state-of-art solutions significantly.

Travel time prediction of a given trajectory plays an indispensable role in intelligent transportation systems. Although many prior researches have struggled for accurate prediction results, most of them achieve inferior performance due to insufficient feature extraction of travel speed and road network structure from the trajectory data, which confirms the challenges involved in this topic. To overcome those issues, we propose a novel neuralNetworkforTravelTimePredictionbased on tensor decomposition and graph embedding, namedTTPNet, which can extract travel speed and representation of road network structure effectively from historical trajectories, as well as predict the travel time with better accuracy. Specifically,TTPNetconsists of three components: the first module (Travel Speed Features Layer) leverages non-negative tensor decomposition to restore travel speed distributions on different roads in the previous hour, and integrates a CNN-RNN model to extract both long-term and short-term travel speed features of the query trajectory; the second module (Road Network Structure Features Layer) utilizes graph embedding to generate the representation of local and global road network structure; the last module (Deep LSTM Prediction Layer) completes the final predicting task. Empirical results over two real-world large-scale datasets show that our proposedTTPNetmodel can achieve significantly better performance and remarkable robustness.

Delayed and missed detection of road closure brings a great influence on the quality of the digital map. The existing solutions using trajectory data aim to identify the closed roads according to the drastic drop property in traffic flow. But in actual applications, such methods may lead to the misidentification of a traffic jam as closure, and cannot detect some events like one side closure of two-way road and the closure in the middle of the road. With the occurrence of road closure, there are variations of turning volume of neighboring roads and the increment of U-turn frequency on the closed roads besides the drastic drop of traffic flow. In this paper, we present a high-efficiency road closure detection framework based upon multi-feature fusion, called RCDM. It consists of an off-line road closure feature modeling part and an online identification part. In the off-line phase, we first partition the road network into grids, and then extract road closure features of grids and those of roads from historical data. In the online phase, on the basis of the predictions for road closure features, we screen out closed grid candidates in terms of traffic flow plunge property and further pinpoint the closed road sections according to turning behavior variations of roads. Extensive experimental results on three real data sets from Chengdu, Shanghai and Beijing validate that our method has higher detection accuracy and efficiency compared with the existing methods.

Since there are no security concerns such as Sybil attacks, selfish mining, etc., the higher the system throughput, the better for the permissioned blockchain. And with the emergence of consensus algorithms, the throughput rates of permissioned blockchain can be up to thousands of transactions per second. The existing serial execution method for smart contracts becomes a new bottleneck for the system. Due to the lack of mutual trust between nodes, for a batch of smart contracts contained in a block, the traditional two-phase smart contract concurrency approach can only achieve concurrency within a single node, but not the parallel execution of contracts between nodes. In this paper, we propose a new two-phase framework based on trusted hardware Intel SGX, which can avoid the re-execution of all smart contracts on all nodes and improve parallelism between nodes. And consistency between nodes is achieved directly with state replication, rather than by re-executing transactions. We design a pre-execution mechanism for smart contracts in untrusted memory to batch fetch all the state data that a smart contract needs to access to reduce frequent enclave transitions during smart contract execution. Besides, we propose a method that generates a compact read-write set and a data structure named Merkle Forest which can generate the compact Merkle multiproofs for the initial data in untrusted memory in parallel and can quickly verify the correctness of the data passed in the enclave. Finally, we integrate all the techniques proposed in this paper into an open-source system BFT-SMaRt to evaluate our approach in a distributed setting. Experimental results show the efficiency of the proposed methods.

The full-replication data storage mechanism, as commonly utilized in existing blockchains, suffers from poor scalability, since it requires every node to preserve a complete copy of the whole block data locally to tolerant potential Byzantine failures. In a hostile environment, the malicious node may discard or tamper data deliberately. Thus, existing distributed storage method, which partitions data into multiple parts and distributes them over all nodes, cannot suit for blockchains. This demonstration showcases BFT-Store, a novel distributed storage engine for blockchains to break full-replication by integrating erasure coding with Byzantine Fault Tolerance (BFT) consensus protocol. This demonstration will (\romannumeral1) allow audience members to see how BFT-Store partitions block data over all nodes to reduce the storage occupation of system, and (\romannumeral2) allow audience members to see how BFT-Store recovers blocks under distributed scenario even with Byzantine failure.

We demonstrate SChain, a consortium blockchain that scales transaction processing to support large-scale enterprise applications. The unique advantage of SChain stems from the exploitation of both intra- and inter-block concurrency. The intra-block concurrency not only takes advantage of the multi-core processor on a single peer but also leverages the capacity of multiple peers. The interblock concurrency enables simultaneous processing across multiple blocks to increase the utilization of various peers. In our demonstration, we use real-time dashboards containing visualization based on the output of SChain to give the attendees interactive explorations of how SChain achieves intra- and inter-block concurrency.

Owing to a wide variety of deployment of GPS -enabled devices, tremendous amounts of trajectories have been generated in distributed stream manner. It opens up new opportunities to track and analyze the moving behaviors of the entities. In this work, we focus on the issue of outlier detection over distributed trajectory streams, where the outliers refer to a few entities whose motion behaviors are significantly different from their local neighbors. In view of skewed distribution property and evolving nature of trajectory data, and on-the-fly detection requirement over distributed streams, we first design a high-efficiency outlier detection solution. It consists of identifying abnormal trajectory fragment and exceptional fragment cluster at the remote sites and then detecting abnormal evolving object at the coordinator site. Further, given that outlier detection accuracy would be damaged due to using inappropriate proximity thresholds or a few trajectory data not having sufficient neighbors at the remote sites, we extract proximity thresholds of different regions and spatial context relationship of each region from historical data to improve the precision. Built upon this is an improved version consisting of off-line modeling phase and on-line detection phase. During the on-line phase, the proximity thresholds that are derived from historical trajectories during the off-line phase are leveraged to assist in detecting abnormal trajectory fragments and exceptional fragment clusters at the remote sites. Additionally, at the coordinator site, the detection results of some remote sites can be refined by incorporating those of other remote sites with neighborhood relationship. Extensive experimental results on real data demonstrate that our proposed methods own high detection validity, less communication cost and linear scalability for online identifying outliers over distributed trajectory streams.

The full-replication data storage mechanism, as commonly utilized in existing blockchains, is the barrier to the system's scalability, since it retains a copy of entire blockchain at each node so that the overall storage consumption per block is O(n) with n participants. Yet another drawback is that this mechanism may limit the throughput in permissioned blockchain. Moreover, due to the existence of Byzantine nodes, existing partitioning methods, though widely adopted in distributed systems for decades, cannot suit for blockchain systems directly, so that it is critical to devise new storage mechanism for blockchain systems. This article proposes a novel storage engine, called BFT-Store, to enhance storage scalability by integrating erasure coding with Byzantine Fault Tolerance (BFT) consensus protocol. The first property of BFT-store is that the storage consumption per block can be reduced to O(1) for the first time, which enlarges overall storage capability when more nodes attend the blockchain. Second, we design an efficient online re-encoding protocol for storage scale-out and a hybrid replication scheme to enhance reading performance. Analysis in theory and extensive experimental results illustrate the scalability, availability and efficiency of BFT-Store via the implementation in an open-source permissioned blockchain Tendermint.

Traffic forecasting on the entire road network is challenging due to the non-linear temporal dynamics and complex spatial correlations. Multi-step traffic forecasting further increases the difficulty because of the accumulated prediction errors. Existing forecasting models attempt to extract both spatial and temporal features of all locations on the road network for prediction, but often overlook the interaction between the two types of features, which has led to sub-optimal performance. In this work, we tackle this problem by proposing InterNet, which applies the multi-head attention mechanism on the extracted spatio-temporal features and enables the interaction of the spatial (temporal) features of one location with the temporal (spatial) features of all locations. Moreover, we extract the features of all locations using a graph convolutional layer and a bidirectional LSTM layer, before feeding them into the multi-head attention layer. The three layers are seamlessly integrated and thereby enable end-to-end learning. Experimental results show that the InterNet model outperforms the state-of-the-art models in terms of the prediction accuracy, which demonstrates the potential of such interactions.

In this demo, we present SEBDB, a novel blockchain database that integrates immutability and transparency properties of blockchain with modeling and query ability of relational database. In summary, SEBDB has the following advantages: First, it adopts the linked structure and full replication of data among multiple participants to guarantee immutability and transparency. Second, it introduces the relational model to blockchain without introducing extra overhead, based on which relational queries are supported. SEBDB supports SQL-like language as the general interface to support convenient application development, in which intrinsic operations are re-defined and re-implemented to suit for blockchain platform. Third, it supports rich verifiable queries based on the proposed authenticated index, thin clients can participate in the system regardless of limitations of storage, network, and computing resources. We demonstrate the usability and scalability of SEBDB using a donation system.

The full-replication data storage mechanism, as commonly utilized in existing blockchain systems, is lack of sufficient storage scalability, since it reserves a copy of the whole block data in each node so that the overall storage consumption per block is O(n) with n nodes. Moreover, due to the existence of Byzantine nodes, existing partitioning methods, though widely adopted in distributed systems for decades, cannot suit for blockchain systems directly, thereby it is critical to devise a new storage mechanism. This paper proposes a novel storage engine, called BFT-Store, to enhance storage scalability by integrating erasure coding with Byzantine Fault Tolerance (BFT) consensus protocol. First, the storage consumption per block can be reduced to O(1), which enlarges overall storage capability when more nodes join blockchain. Second, an efficient online re-encoding protocol is designed for storage scale-out and a hybrid replication scheme is employed to improve reading performance. Last, extensive experimental results illustrate the scalability, availability and efficiency of BFT-Store, which is implemented on an open-source permissioned blockchain Tendermint.

The inaccuracy of road intersection in digital road map easily brings serious effects on the mobile navigation and other applications. Massive traveling trajectories of thousands of vehicles enable frequent updating of road intersection topology. In this paper, we first expand the road intersection detection issue into a topology calibration problem for road intersection influence zone. Distinct from the existing road intersection update methods, we not only determine the location and coverage of road intersection, but figure out incorrect or missing turning paths within whole influence zone based on unmatched trajectories as compared to the existing map. The important challenges of calibration issue include that trajectories are mixing with exceptional data, and road intersections are of different sizes and shapes, etc. To address above challenges, we propose a three-phase calibration framework, called CITT. It is composed of trajectory quality improving, core zone detection, and topology calibration within road intersection influence zone. From such components it can automatically obtain high quality topology of road intersection influence zone. Extensive experiments compared with the state-of-the-art methods using trajectory data obtained from Didi Chuxing and Chicago campus shuttles demonstrate that CITT method has strong stability and robustness and significantly outperforms the existing methods.

Blockchain has been adopted in many applications to construct trust among multiple participants, such as supply chain management, digital assets transfer, philanthropy, etc. Blockchain platforms are often used as decentralized databases. However, existing blockchain platforms are far less convenient to use than traditional databases. They are lack of the capability of modelling complex tasks conveniently and efficiently, especially when both on-chain and off-chain data are involved at the same time. In this paper, we propose and implement a novel blockchain database, called SEBDB, which leverages the existing databases' functionality which are optimized for decades. Comparing to existing works, SEBDB is the first platform which considers both useability and scalability. Specifically, first, weaddrelationaldata semantics into blockchain platform, where each transaction is a tuple with multiple attributes in a pre-defined table. Second, we use SQL-like language as the general interface, instead of code-level APIs, to support convenient application development, in which intrinsic operations are re-defined and re-implemented to suit for blockchain platform. Third, as RDBMS has achieved great success in the past decades, our system, though not relying on RDBMS, treats it as an important component. Finally, we define a mini-benchmark to evaluate the performance of the blockchain database. Extensive experiments demonstrate the effectiveness and efficiency of our proposed system.

Large collections of GPS trajectory data provide us unprecedented opportunity to detect the road intersection automatically. However, in the real-world scenarios, the precision of existing detection methods cannot be guaranteed due to severe challenges including (i) low-quality raw GPS trajectory data and (ii) the difficulty of differentiating intersections from nonintersections. To tackle above issues, we propose a novel twophase road intersection detection framework, called as RIDF, which is comprised of trajectory quality improving and intersection extracting. More importantly, through extracting candidate cells based on direction statistic analysis and refining the locations of intersections using hybrid clustering strategy, our approach can effectively detect road intersections of different size. An experimental evaluation on two real data sets extensively assesses the quality of RIDF method by comparing it with state-of-theart methods. Experimental results demonstrate that our proposal can overcome the limitations of existing methods and thus have better accuracy than the existing work.

Motivated by many practical applications in logistics and mobility-as-a-service, we study the top-k optimal sequenced routes (KOSR) querying on large, general graphs where the edge weights may not satisfy the triangle inequality, e.g., road network graphs with travel times as edge weights. The KOSR querying strives to find the top-k optimal routes (i.e., with the top-k minimal total costs) from a given source to a given destination, which must visit a number of vertices with specific vertex categories (e.g., gas stations, restaurants, and shopping malls) in a particular order (e.g., visiting gas stations before restaurants and then shopping malls). To efficiently find the top-k optimal sequenced routes, we propose two algorithms PruningKOSR and StarKOSR. In PruningKOSR, we define a dominance relationship between two partially-explored routes. The partially-explored routes that can be dominated by other partially-explored routes are postponed being extended, which leads to a smaller searching space and thus improves efficiency. In StarKOSR, we further improve the efficiency by extending routes in an A manner. With the help of a judiciously designed heuristic estimation that works for general graphs, the cost of partially explored routes to the destination can be estimated such that the qualified complete routes can be found early. In addition, we demonstrate the high extensibility of the proposed algorithms by incorporating Hop Labeling, an effective label indexing technique for shortest path queries, to further improve efficiency. Extensive experiments on multiple real-world graphs demonstrate that the proposed methods significantly outperform the baseline method. Furthermore, when k = 1, StarKOSR also outperforms the state-of-the-art method for the optimal sequenced route queries.

The classical K Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for vehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely affecting service qualities. In this paper, we formalize the K Shortest Paths with Diversity (KSPD) problem that identifies top-k shortest paths such that the paths are dissimilar with each other and the total length of the paths is minimized. We first prove that the KSPD problem is NP-hard and then propose a generic greedy framework to solve the KSPD problem in the sense that (1) it supports a wide variety of path similarity metrics which are widely adopted in the literature and (2) it is also able to efficiently solve the traditional KSP problem if no path similarity metric is specified. The core of the framework includes the use of two judiciously designed lower bounds, where one is dependent on and the other one is independent on the chosen path similarity metric, which effectively reduces the search space and significantly improves efficiency. Empirical studies on 5 real-world and synthetic graphs and 5 different path similarity metrics offer insight into the design properties of the proposed general framework and offer evidence that the proposed lower bounds are effective.

The existing detection techniques are not tailored to identify the outlier which is close to its neighbors according to some features, but behaves significantly distinct from its neighbors in terms of the other features. In this paper, we propose a feature grouping-based mechanism, and then present two algorithms to detect outliers (TF-outlier and MO-outlier) upon trajectory streams. The effectiveness and efficiency of our proposal are validated by the experiments on real trajectory data.

The wide deployments of GPS-embedded devices have produced multiple rapid voluminous trajectory streams, which needs to be analyzed to extract abnormal behaviors of moving objects in real-time. To date, outlier detection over distributed trajectory streams has not received enough focuses due to the constraint factors like skewness distribution and evolving nature of trajectory data, and on-the-fly execution requirement with minimal communication cost. In this paper, we present the first scalable decentralized outlier detection framework over distributed trajectory streams, called ODDTS. It consists of remote site processing and coordinator processing, with the aim of continuously providing feature-grouping based outliers detection over distributed trajectory streams. Extensive experiments over real data demonstrate high detecting validity, less communication cost and linear scalability of ODDTS method for online identifying outliers upon distributed trajectory streams.

The classical K Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for vehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely affecting service qualities. In this paper, we formalize the K Shortest Paths with Diversity (KSPD) problem that identifies top-k shortest paths such that the paths are dissimilarwith each other and the total length of the paths is minimized. We first prove that the KSPD problem is NP-hard and then propose a generic greedy framework to solve the KSPD problem in the sense that (1) it supports a wide variety of path similarity metrics which are widely adopted in the literature and (2) it is also able to efficiently solve the traditional KSP problem if no path similarity metric is specified. The core of the framework includes the use of two judiciously designed lower bounds, where one is dependent on and the other one is independent on the chosen path similarity metric, which effectively reduces the search space and significantly improves efficiency. Empirical studies on five real-world and synthetic graphs and five different path similarity metrics offer insight into the design properties of the proposed general framework and offer evidence that the proposed lower bounds are effective.

Outlier detection acts as one of the most important analysis tasks for trajectory stream. In stream scenarios, such properties as unlimitedness, time-varying evolutionary, sparsity, and skewness distribution of trajectories pose new challenges to outlier detection technique. Trajectory outlier detection techniques mainly focus on finding trajectory that is dissimilar to the majority of the others, which is based on the hypothesis that they are probably generated by a different mechanism. Most distance-based methods tend to utilize a function (e.g., weighted linear sum) to measure the similarity of two arbitrary objects provided that representative features have been extracted in advance. However, this kind of method is not tailored to identify the outlier which is close to its neighbors according to some features, but behaves significantly different from its neighbors in terms of the other features. To address this issue, we propose a feature grouping-based mechanism that divides all the features into two groups, where the first group (Similarity Feature) is used to find close neighbors and the second group (Difference Feature) is used to find outliers within the similar neighborhood. According to the feature differences among local adjacent objects in one or more time intervals, we present two outlier definitions, including local anomaly trajectory fragment (TF-outlier) and evolutionary anomaly moving object (MO-outlier ). We devise a basic solution and then an optimized algorithm to detect both types of outliers. Experimental results show that our proposal is both effective and efficient to detect outliers upon trajectory data streams.

In modern cities, more and more people drive the vehicles, equipped with the GPS devices, which create a large scale of trajectories. Gathering and analyzing these large-scale trajectory data provide a new opportunity to understand the city dynamics and to reveal the hidden social and economic phenomena. This paper designs and implements a tool, named as PGWinFunc, to analyze trajectory data by extending a traditional relational database. Firstly we introduce some efficient query process and optimization methods for SQL Window Aggregate Functions in PostgreSQL. Secondly, we present how to mine the LBS (Location-Based Service) patterns, such as the average speed and traffic flow, from the large-scale trajectories with SQL expression with Window Aggregate Functions. Finally, the effectiveness and efficiency of the PGWinFunc tool are demonstrated and we also visualized the results by BAIDU MAP.

Finding matching customers for a given product based on individual user's preference is critical for many applications, especially in e-commerce. Recently, the reverse top- k query is proposed to return a number of customers who regard a given product as one of the k most favorite products based on a linear model. Although a few "hot" products can be returned to some customers via reverse top- k query, a large proportion of products (over 90%, as our example illustrates, see Figure 2) cannot find any matching customers. Inspired by this observation, we propose a new kind of query (R- k Ranks) which finds for a given product, the top- k customers whose rank for the product is highest among all customers, to ensure 100% coverage for any given product, no matter it is hot or niche . Not limited to e-commerce, the concept of customer - product can be extended to a wider range of applications, such as dating and job-hunting. Unfortunately, existing approaches for reverse top- k query cannot be used to handle R- k Ranks conveniently due to infeasibility of getting enough elements for the query result. Hence, we propose three novel approaches to efficiently process R- k Ranks query, including one tree-based method and two batch-pruning-based methods. Analysis of theoretical and experimental results on real and synthetic data sets illustrates the efficacy of the proposed methods.

Evaluating similarity between sets is a fundamental task in computer science. However, there are many applications in which elements in a set may be uncertain due to various reasons. Existing work on modeling such probabilistic sets and computing their similarities suffers from huge model sizes or significant similarity evaluation cost, and hence is only applicable to small probabilistic sets. In this paper, we propose a simple yet expressive model that supports many applications where one probabilistic set may have thousands of elements. We define two types of similarities between two probabilistic sets using the possible world semantics; they complement each other in capturing the similarity distributions in the cross product of possible worlds. We design efficient dynamic programming-based algorithms to calculate both types of similarities. Novel individual and batch pruning techniques based on upper bounding the similarity values are also proposed. To accommodate extremely large probabilistic sets, we also design sampling-based approximate query processing methods with strong probabilistic guarantees. We have conducted extensive experiments using both synthetic and real datasets, and demonstrated the effectiveness and efficiency of our proposed methods.

Tracking data provenance (or lineage) has become increasingly important in many large-scale applications, and a few methods have been proposed to record data provenance recently. However, most of previous works mainly focus on deterministic databases except Trio style lineage that aims at probabilistic databases, which is much more challenging because of the exponential growth of possible world instances and dependence among intermediate tuples. This paper proposes an approach, named PHP-tree, to model how-provenance upon probabilistic databases. we also show how to evaluate probability based on a PHP-tree. Compared with Trio style lineage, our approach is independent of intermediate results and can calculate the probability both cases of restricted and complete propagation of data provenance. Detailed experimental results show the effectiveness, efficiency and scalability of our proposed model.

Query processing on uncertain data streams has attracted a lot of attentions lately, due to the imprecise nature in the data generated from a variety of streaming applications, such as readings from a sensor network. However, all of the existing works on uncertain data streams study unbounded streams. This paper takes the first step towards the important and challenging problem of answering sliding-window queries on uncertain data streams, with a focus on arguably one of the most important types of queries---top- k queries. The challenge of answering sliding-window top- k queries on uncertain data streams stems from the strict space and time requirements of processing both arriving and expiring tuples in high-speed streams, combined with the difficulty of coping with the exponential blowup in the number of possible worlds induced by the uncertain data model. In this paper, we design a unified framework for processing sliding-window top- k queries on uncertain streams. We show that all the existing top- k definitions in the literature can be plugged into our framework, resulting in several succinct synopses that use space much smaller than the window size, while are also highly efficient in terms of processing time. In addition to the theoretical space and time bounds that we prove for these synopses, we also present a thorough experimental report to verify their practical efficiency on both synthetic and real data.

It is challenge to maintain frequent items over a data stream, with a small bounded memory, in a dynamic environment where both insertion/deletion of items are allowed. In this paper, we propose a new novel algorithm, called hCount, which can handle both insertion and deletion of items with a much less memory space than the best reported algorithm. Our algorithm is also superior in terms of precision, recall and processing time. In addition, our approach does not request the preknowledge on the size of range for a data stream, and can handle range extension dynamically. Given a little modification, algorithm hCount can be improved to hCount*, which even owns significantly better performance than before.