Blockchain-enabled internet of things (BIoT) has emerged as a promising paradigm to enhance security and privacy in distributed environments. While blockchain ensures data integrity through immutable and tamper-proof records, its adoption in resource-constrained devices (RCDs) remains challenging due to computationally intensive consensus mechanisms and inefficient storage practices. This paper introduces ReBIoT, a secure and lightweight framework designed to optimise blockchain integration within RCD-based systems. ReBIoT decentralises intelligence by enabling interactive decision-making among nodes, replacing traditional heavy consensus verification. It further incorporates a self-learning rule-based data filtering (SRDF) mechanism to remove redundant or irrelevant data, and applies forking and versioning with fixed-length chunking to improve immutability and storage efficiency. The layered architecture of ReBIoT progressively filters raw data and prevents duplication, providing a flexible interface for various distributed applications. Experimental evaluations demonstrate that ReBIoT significantly reduces computational and storage overheads while maintaining data reliability and security.

DRAM faults are the main hardware cause of node unavailability in clouds. To enable early preventive actions and mitigate DRAM fault impacts, prior studies focus on predicting DRAM uncorrectable errors (UEs) that typically cause immediate node unavailability. However, in Alibaba Cloud, we observe that correctable error(CE) storm (numerous CEs occur in a short period) dominates 41% DRAM-caused node unavailability (DCNU). In this paper, we propose to predict DCNU by taking into account both UEs and CE storms. Specifically, observing that DCNUs have strong relevance to the temporal statistics and spatial patterns of CEs, we design novel spatio-temporal features and use soft labels to build a DCNU predictor. We propose novel rule mining algorithms that can generate accurate and interpretable rules to improve the prediction performance. Considering the predictor’s real effects cannot be evaluated by traditional metrics like F1-score, we propose a new metric, NURR, to quantify the node unavailability reduction rate and tune model hyperparameters with NURR. The comparative study shows that our approach achieves over 40% better NURR than existing methods and runs stably in the production environment.

DRAM failures are one of the leading failures in large-scale clouds. Previous studies focus on predicting DRAM uncorrectable errors (UEs) and mitigating the impact of DRAM failures through node-level workload migration and proactive dual in-line memory module (DIMM) replacement. For cloud systems, node migration means migrating all virtual machines (VMs) to other nodes. Such a coarse-grained migration consumes considerable resources. Inspired by the observation that DRAM errors tend to cluster in space, this paper proposes Pegasus, the first VM-level solution to mitigate DRAM failures. The key idea of Pegasus is to use the VM as the basic unit for predicting DRAM failures instead of the whole node. Specifically, we introduce a new concept of DRAM-caused risky VMs, which causes node unavailability when accessed. We design a novel Error-VM mapping framework deployed on a large-scale cloud. Statistical results confirm that DRAM errors are concentrated in the address space managed by a small number of VMs. By combining ECC and spatio-temporal features, our predictor achieves decent performance. Pegasus has been deployed online on over $\mathbf{3 0 0, 0 0 0}$ nodes in the production cloud. The comparative study shows that the prediction performance of Pegasus is comparable to node-level solutions. Meanwhile, our approach offers over $\mathbf{7 0 \%}$ lower costs and avoids more than $\mathbf{1 0 \%}$ of VM crashes compared to node-level mitigation.

High-dimensional vector similarity search (HVSS) is critical for many data processing and AI applications. However, traditional HVSS methods often require extensive data access for distance calculations, leading to inefficiencies. Triangle-inequality-based lower bound pruning is a widely used technique to reduce the number of data access in low-dimensional spaces but becomes less effective in high-dimensional settings. This is attributed to the ''distance concentration'' phenomenon, where the lower bounds derived from the triangle inequality become too small to be useful. To address this, we propose TRIM, which enhances the effectiveness of traditional triangle-inequality-based pruning in high-dimensional vector similarity search using two key ways: (1) optimizing landmark vectors used to form the triangles, and (2) relaxing the lower bounds derived from the triangle inequality, with the relaxation degree adjustable according to user's needs. TRIM is a versatile operation that can be seamlessly integrated into both memory-based (e.g., HNSW, IVFPQ) and disk-based (e.g., DiskANN) HVSS methods, reducing distance calculations and disk access. Extensive experiments show that TRIM enhances memory-based methods, improving graph-based search by up to 90% and quantization-based search by up to 200%, while achieving a pruning ratio of up to 99%. It also reduces I/O costs by up to 58% and improves efficiency by 102% for disk-based methods, while preserving high query accuracy. Our source code is available at https://github.com/petrizhang/TRIM.

Next point-of-interest (POI) recommendationpredicts user’s next movement and facilitates location-based applications such as destination suggestion and travel planning. State-of-the-art (SOTA) methods learn an adaptive graph from user trajectories and compute POI representations using graph neural networks (GNNs). However, a single graph cannot capture thediverse dependenciesamong the POIs (e.g., geographical proximity and transition frequency). To tackle this limitation, we propose theAdaptiveGraphContrastiveLearning(AGCL) framework. AGCL constructs multiple adaptive graphs, each modeling a kind of POI dependency and producing one POI representation; and the POI representations from different graphs are merged into amulti-facet representationthat encodes comprehensive information. To train the POI representations, we tailor agraph-based contrastive learning, which encourages the representations of similar POIs to align and dissimilar POIs to differentiate. Moreover, to learn the sequential regularities of user trajectories, we design an attention mechanism to integrate spatial-temporal information into the POI representations. An explicitspatial-temporal biasis also employed to adjust the predictions for enhanced accuracy. We compare AGCL with 10 state-of-the-art baselines on 3 datasets. The results show that AGCL outperforms all baselines and achieves an improvement of 10.14% over the best performing baseline in average accuracy.

Reverse$k$nearest neighbor search$(\mathbf{R}k\mathbf{NNS})$plays an important role in various data processing and analysis tasks, seeking to pinpoint data considering the query data$q$among their$k$nearest neighbors. As large models gain popularity, processing high-dimensional vectors has become more and more widespread. However, existing$\mathbf{R}k\mathbf{NNS}$solutions face inefficiency when handling large-scale high-dimensional vectors due to their sensitivity to data dimensions and sizes during index construction or the verification of numerous candidate results in the query phase. Motivated by these challenges and the inherent intricacies of high-dimensional data processing, in this paper, we study an approximate version of the$\mathbf{R}k\mathbf{NNS}$problem$(\mathbf{R}k\mathbf{ANNS})$for high-dimensional vectors, aiming to offer efficient and practical solutions. To this end, we propose a new proximity-graph-based index called HAMG, which enables finding the query results within$k$hops from$q$. We also present a user-friendly query algorithm on HAMG that can adaptively adjust the search scope based on the desired query recall of users. To further enhance the query process, two pruning strategies are proposed to reduce the number of candidates requiring verification. Extensive experiments validate that HAMG scales well for data dimensions and sizes, and our query algorithm improves query efficiency by up to two orders of magnitude while maintaining comparable query accuracy against existing approaches.

Information networks generally exhibit three characteristics, namely dynamicity, heterogeneity, and node attribute diversity. However, most existing network embedding approaches only consider two of the three when embedding each node into low-dimensional space. Adding to such an existing approach a technique of processing the remaining characteristic can easily cause incompatibility. One solution to process the three characteristics together is to treat the dynamic heterogeneous attributed network (DHAN) as a temporal sequence of heterogeneous attributed network (HAN) snapshots. For example, existing graph convolutional networks (GCNs)-based DHAN embedding approaches embed the HAN snapshots to get static representations offline, and then dynamically capture temporal dependencies between adjacent snapshots online to maintain fresh representations of the DHAN. However, those approaches encounter the convergence problem when stacking multiple convolutional layers to capture more topological information. Some other existing approaches dynamically update the representations of HAN snapshots online, neglecting the efficiency requirement of online scenarios and the temporal dependencies between snapshots. To address the two issues, we propose a new framework called Dynamic Heterogeneous Attributed Network Embedding (DHANE), consisting of a static model MGAT and a dynamic model NICE. MGAT captures more topological information while maintaining GCN convergence by performing metagraph-based attention in each convolutional layer. NICE preserves network freshness while reducing the computational load of the update by only examining network changes and updating their embedding representations. Extensive experiments show that DHANE achieves up to 27× speedup and 9.1-26.4% higher accuracy on several real dynamic heterogeneous attributed networks for online classification.

This paper presents an efficient and scalable framework for Range Filtered Approximate Nearest Neighbors Search (RF-ANNS) over high-dimensional vectors associated with attribute values. Given a query vector q and a range [ l, h ], RF-ANNS aims to find the approximate k nearest neighbors of q among data whose attribute values fall within [ l, h ]. Existing methods including pre-, post-, and hybrid filtering strategies that perform attribute range filtering before, after, or during the ANNS process, all suffer from significant performance degradation when query ranges shift. Though building dedicated indexes for each strategy and selecting the best one based on the query range can address this problem, it leads to index consistency and maintenance issues. Our framework, called UNIFY, constructs a unified Proximity Graph-based (PG-based) index that seamlessly supports all three strategies. In UNIFY, we introduce SIG, a novel S egmented I nclusive G raph, which segments the dataset by attribute values. It ensures the PG of objects from any segment combinations is a sub-graph of SIG, thereby enabling efficient hybrid filtering by reconstructing and searching a PG from relevant segments. Moreover, we present H ierarchical S egmented I nclusive G raph (HSIG), a variant of SIG which incorporates a hierarchical structure inspired by HNSW to achieve logarithmic hybrid filtering complexity. We also implement pre- and post-filtering for HSIG by fusing skip list connections and compressed HNSW edges into the hierarchical graph. Experimental results show that UNIFY delivers state-of-the-art RF-ANNS performance across small, mid, and large query ranges.

Knowledge graphs (KGs) play a vital role in enhancing search results and recommendation systems. With the rapid increase in the size of KGs, they are becoming inaccurate and incomplete. This problem can be solved by the KG completion methods, of which graph attention network (GAT)-based methods stand out because of their superior performance. However, existing GAT-based KG completion methods often suffer from overfitting issues when dealing with heterogeneous KGs, primarily due to the unbalanced number of samples. Additionally, these methods demonstrate poor performance in predicting the tail (head) entity that shares the same relation and head (tail) entity with others. To solve these problems, we propose GATH, a novel GAT -based method designed for H eterogeneous KGs. GATH incorporates two separate attention network modules that work synergistically to predict the missing entities. We also introduce novel encoding and feature transformation approaches, enabling the robust performance of GATH in scenarios with imbalanced samples. Comprehensive experiments are conducted to evaluate GATH’s performance. Compared with the existing state-of-the-art GAT-based model on Hits@10 and MRR metrics, our model improves performance by 5.2% and 5.2% on the FB15K-237 dataset and by 4.5% and 14.6% on the WN18RR dataset, respectively.

Desirable information processing in space-terrestrial integrated vehicle networks (STINs) handles data distributed in different satellites while transmitting, where efficient modeling time-varying resources is critical. Existing works are not applicable to STINs, however, because they lack the joint consideration of different movement patterns and fluctuating loads. In this paper, we propose theTime-Varying Resource Graph (TVRG)to model dynamic resources in STINs, by leveraging the advantages of software-defined networking in flexible resource management. Firstly, we propose theSTIN mobility modelto uniformly model different movement patterns in STINs. Then, we propose alayered Resource Modeling and Abstraction (RMA)approach, where evolutions of node resources are modeled as Markov processes, by encoding predictable topologies and influences of fluctuating loads as states. Besides, we propose the low-complexity domain resource abstraction algorithm by defining two mobility-based and load-aware partial orders on resource abilities. Finally, we formulate theTVRG-based Processing on the Way (TPoW)problem for data flows with processing requirements and multiple sources. We propose aMulti-level Processing on the Way (MPoW)approach with a bounded approximation ratio, realizing adaptive matching of resources and demands of processing and transmission. To evaluate the RMA approach, we propose aTVRG-based Routing (TR)algorithm for time-sensitive and bandwidth-intensive data flows, with the multi-level on-demand scheduling ability. Comprehensive simulation results demonstrate that our RMA-TR and MPoW outperform most related schemes by decreasing nearly 40% bandwidth consumption with the shortest end-to-end delay.

Recently, after successfully revolutionising financial services, blockchain is now transforming a variety of other domains. However, current working abstraction requires technology to have more maturity from several key perspectives, and linear data processing is one of them. Blockchain, with its core characteristics like immutability, traceability, and decentralisation, has the potential to support various types of data. Currently, we find this design an ideal model to support spatial data structures, which, to the best of our knowledge, is a novel feature. We lead this opportunity to enrich blockchain with efficient spatial keyword data. We introduce spatial keyword index for block (SKIB), which is a cryptographically signed tree, thus maintaining the storage and integrity of original data from its spatial topological contexts. To demonstrate our work, we implement both textual first and spatial first pruning techniques. The comprehensive evaluation shows that SKIB provides efficient spatial keyword data processing on blockchains.

The cover tree (CT) and its improved version are hierarchical data structures that simplified navigating nets while maintaining good runtime guarantees. They can perform nearest neighbor search in logarithmic time and provide efficient computation in practice. In this article, we revisit cover trees for nearest neighbor search, and propose a more competitive method. The central idea of our method is to fully exploit the unused distance and direction information. More specially, our method introduces three novel concepts/techniques: (i) range list, (ii) quadrant information, and (iii) vectorial angle cosine. These techniques are seamlessly integrated into our suggested data structure and search algorithms. As an extra bonus, we explore approximate nearest neighbor and$k$nearest neighbor based on the proposed techniques, and present algorithms for handling updates. Extensive experimental results, based on both real and synthetic datasets, consistently demonstrate that our method is attractive and competitive, compared against existing cover tree structures for nearest neighbor search and its variants.

Retrosynthetic planning plays an important role in the field of organic chemistry, which could generate a synthetic route for the target product. The synthetic route is a series of reactions which are started from the available molecules. The most challenging problem in the generation of the synthetic route is the large search space of the candidate reactions. Estimating the cost of candidate reactions has been proved effectively to prune the search space, which could achieve a higher accuracy with the same search iteration. And the estimation of one reaction is comprised of the estimations of all its reactants. So, how to estimate the cost of these reactants will directly influence the quality of results. To get a better performance, we propose a new framework, named GNN-Retro, for retrosynthetic planning problem by combining graph neural networks(GNN) and the latest search algorithm. The structure of GNN in our framework could incorporate the information of neighboring molecules, which will improve the estimation accuracy of our framework. The experiments on the USPTO dataset show that our framework could outperform the state-of-the-art methods with a large margin under the same settings.

DRAM faults are major hardware sources of cloud node unavailability. To enable early preventive actions and mitigate DRAM fault impacts, prior studies focus on predicting DRAM uncorrectable errors (UEs) that typically cause immediate node unavailability. In our cloud with over half a million nodes, we firstly observe that the correctable error storm (numerous CEs occur in a short period) dominates 56% DRAM-caused node unavailability (DCNU). Therefore, we propose to predict DCNU that takes account into both UEs and CE storms. Observing that DCNUs have strong relevance to temporal statistics and spatial patterns of CEs, we design novel spatio-temporal features to train the prediction model. Considering the model’s real effects cannot be evaluated by traditional metrics like F1-score, we propose a new metric NURR to quantify the node unavailability reduction and tune model hyperparameters with NURR. Our approach achieves over 40% better NURR than existing methods on historical data and runs stably in the production environment.

Infectious diseases have been recognized as major public health concerns for decades. Close contact discovery is playing an indispensable role in preventing epidemic transmission. In this light, we study the continuous exposure search problem: Given a collection of moving objects and a collection of moving queries, we continuously discover all objects that have been directly and indirectly exposed to at least one query over a period of time. Our problem targets a variety of applications, including but not limited to disease control, epidemic pre-warning, information spreading, and co-movement mining. To answer this problem, we develop an exact group processing algorithm with optimization strategies. Further, we propose an approximate algorithm that substantially improves the efficiency without false dismissal. Extensive experiments offer insight into effectiveness and efficiency of our proposed algorithms.

Next Point-of Interest (POI) recommendation plays an important role in location-based applications, which aims to recommend the next POIs to users that they are most likely to visit based on their historical trajectories. Existing methods usually use rich side information, or customized POI graphs to capture the sequential patterns among POIs. However, the graphs only focus on connectivity between POIs. Few studies propose to explicitly learn a weighted POI graph, which could reflect the transition patterns among POIs and show the importance of its different neighbors for each POI. In addition, these approaches simply utilize the user characteristics for personalized POI recommendation without sufficient consideration. To this end, we construct a novel User-POI Knowledge Graph with strong representation ability, called Spatial-Temporal Knowledge Graph (STKG). STKG is used to learn the representations of each node (i.e., user, POI) and each edge. Then, we design a similarity function to construct our POI transition graph based on the learned representations. To incorporate the learned graph into sequential model, we propose a novel network Graph-Flashback for recommendation. Graph-Flashback applies a simplified Graph Convolution Network (GCN) on the POI transition graph to enrich the representation of each POI. Further, we define a similarity function to consider both spatiotemporal information and user preference in modelling sequential regularity. Experimental results on two real-world datasets show that our proposed method achieves the state-of-the-art performance and significantly outperforms all existing solutions.

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.

With the increase of dirty data, data cleaning turns into a crux of data analysis. The accuracy limitation of the existing integrity constraints-based cleaning approaches results from insufficient rules. In this paper, we present a novel hybrid data cleaning framework on top of Markov logic networks (MLNs), termed as${\sf MLNClean}$, which is capable of learning instantiated rules to supplement the insufficient integrity constraints.${\sf MLNClean}$consists of two steps, i.e.,pre-processingandtwo-stage data cleaning. In the pre-processing step,${\sf MLNClean}$first infers a set of probable instantiated rules according to MLNs and then builds a two-layer MLN index structure to generate multiple data versions and facilitate the cleaning process. In the two-stage data cleaning step,${\sf MLNClean}$first presents a concept ofreliability scoreto clean errors within each data version separately, and afterward eliminates the conflict values among different data version using a novel concept offusion score. Considerable experimental results on both real and synthetic scenarios demonstrate the effectiveness of${\sf MLNClean}$in practice.

The advance of tour recommendation allows people to get well-fit route plans, which contain a sequence of Points of Interest (POIs) based on tourists’ constraints and preferences. Large-scale POIs, called Super-POIs in this article, often contain multiple scenic spots and entrances. Tourists have to specify a suitable tour route inside Super-POI to obtain good tour experience. However, most of existing tour recommendation algorithms ignore the detailed information inside Super-POIs. By taking super-POIs into account, we proposeEmbedded Tour(eTOUR), a two-layer framework considering route design of POIs (Outer Model) and scenic routes inside the Super-POIs (Inner Model) respectively. To combine two models, an Embedded GRASP-VNS Algorithm is introduced based on an embedding strategy. For Outer Model, we apply Greedy Randomized Adaptive Search Procedure (GRASP) for route construction and Variable Neighborhood Search (VNS) for local improvement. Super-POI is treated as a “meta node” in outer route construction. For Inner Model, the optimal route inside Super-POI obtained by DFS-based Tree Search with Pruning is revised dynamically to adapt to the outer route. Furthermore, we discuss a special case in the Super-POI where a key graph is defined and treated as the “must go” route. We modify the solution of Chinese Postman Problem in this case to reduce the time complexity. Finally, experiments based on two real datasets demonstrate the effectiveness of our proposal.

With the growth of dirty data, data cleaning turns into a crux of data analysis. In this paper, we propose a novel hybrid data cleaning framework, termed as MLNClean, which is capable of learning instantiated rules to supplement the insufficient integrity constraints. MLNClean consists of two steps, i.e., pre-processing and two-stage data cleaning. In the pre-processing step, MLNClean first infers a set of probable instantiated rules according to Markov logic network (MLN) and then builds a two-layer MLN index to generate multiple data versions and facilitate the cleaning process. In the two-stage data cleaning step, MLNClean first presents a concept of reliability score to clean errors within each data version separately, and then, it eliminates the conflict values among different data versions using a novel concept of fusion score. Considerable experimental results on both real and synthetic scenarios demonstrate the effectiveness of MLNClean.

Route planning and recommendation have attracted much attention for decades. In this paper, we study a continuous optimal route combination problem: Given a dynamic road network and a stream of trip queries, we continuously find an optimal route combination for each new query batch over the query stream such that the total travel time for all routes is minimized. Each route corresponds to a planning result for a particular trip query in the current query batch. Our problem targets a variety of applications, including traffic-flow management, real-time route planning and continuous congestion prevention. The exact algorithm bears exponential time complexity and is computationally prohibitive for application scenarios in dynamic traffic networks. To address this problem, a self-aware batch processing algorithm is developed in this paper. Extensive experiments offer insight into the accuracy and efficiency of our proposed algorithms.

It is critical but difficult to efficiently model re-sources in space-terrestrial integrated networks (STINs). Existing work is not applicable to STINs because they lack the joint consideration of different movement patterns and fluctuating loads. In this paper, we propose the time-varying resource graph (TVRG) to model STINs from the resource perspective. Firstly, we propose the STIN mobility model to uniformly model different movement patterns in STINs. Then, we propose a layered Resource Modeling and Abstraction (RMA) approach, where evolutions of node resources are modeled as Markov processes, by encoding predictable topologies and influences of fluctuating loads as states. Besides, we propose the low-complexity domain resource abstraction algorithm by defining two mobility-based and load-aware partial orders on resource abilities. Finally, we propose an efficient TVRG-based Resource Scheduling (TRS) algorithm for time-sensitive and bandwidth-intensive data flows, with the multi-level on-demand scheduling ability. Comprehensive simulation results demonstrate that the RMA-TRS outperforms related schemes in terms of throughput, end-to-end delay and flow completion time.

Aggregate nearest neighbor (Ann) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor (Fann) problem further generalizesAnnby introducing an extra flexibility parameter$\phi$that ranges in$(0, 1]$. In this article, we focus onFannon road networks, denoted asFann$_\mathcal {R}$, and its keyword-aware variant, denoted asKFann$_\mathcal {R}$. To solve these problems, we propose a series of universal (i.e., suitable for bothmaxandsum) algorithms, including a Dijkstra-based algorithm that enumerates$P$instead of$\phi |Q|$-combinations of$Q$, a queue-based approach that processes data points from-near-to-far, and a framework that combinesincremental euclidean restriction(IER) and$k$NN. We also propose a specific exact solution tomax-Fann$_\mathcal {R}$and a constant-factor ratio approximate solution tosum-Fann$_\mathcal {R}$. These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend this problem to top-$k$and multipleFann$_\mathcal {R}$(resp.,KFann$_\mathcal {R}$) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality.

Pricing is essential in optimizing transportation resource allocation. Congestion pricing is widely used to reduce urban traffic congestion. We propose and investigate a novel Dynamic Pricing Strategy (DPS) to price travelers' trips in intelligent transportation platforms (e.g., DiDi, Lyft, Uber). The trips are charged according to their “congestion contributions” to global urban traffic systems. The dynamic pricing strategy retrieves a matching between n travelers' trips and the potential travel routes (each trip has k potential routes) to minimize the global traffic congestion. We believe that DPS holds the potential to benefit society and the environment, such as reducing traffic congestion and enabling smarter and greener transportation. The DPS problem is challenging due to its high computation complexity (there exist kn matching possibilities). We develop an efficient and effective approximate matching algorithm based on local search, as well as pruning techniques to further enhance the matching efficiency. The accuracy and efficiency of the dynamic pricing strategy are verified by extensive experiments on real datasets.

The research interest in specialized hardware accelerators for deep neural networks (DNN) spikes recently owing to their superior performance and efficiency. However, today’s DNN accelerators primarily focus on accelerating specific "kernels" such as convolution and matrix multiplication, which are vital but only part of an end-to-end DNN-enabled application. Meaningful speedups over the entire application often require supporting computations that are, while massively parallel, ill-suited to DNN accelerators. Integrating a general-purpose processor such as a CPU or a GPU incurs significant data movement overhead and leads to resource under-utilization on the DNN accelerators.We propose Simultaneous Multi-mode Architecture (SMA), a novel architecture design and execution model that offers general-purpose programmability on DNN accelerators in order to accelerate end-to-end applications. The key to SMA is the temporal integration of the systolic execution model with the GPU-like SIMD execution model. The SMA exploits the common components shared between the systolic-array accelerator and the GPU, and provides lightweight reconfiguration capability to switch between the two modes in-situ. The SMA achieves up to 63% performance improvement while consuming 23% less energy than the baseline Volta architecture with TensorCore.

Matching similar pairs of trajectories, called trajectory similarity join, is a fundamental functionality in spatial data management. We consider the problem of semantic trajectory similarity join (STS-Join). Each semantic trajectory is a sequence of Points-of-interest (POIs) with both location and text information. Thus, given two sets of semantic trajectories and a threshold θ, the STS-Join returns all pairs of semantic trajectories from the two sets with spatio-textual similarity no less than θ. This join targets applications such as term-based trajectory near-duplicate detection, geo-text data cleaning, personalized ridesharing recommendation, keyword-aware route planning, and travel itinerary recommendation.With these applications in mind, we provide a purposeful definition of spatio-textual similarity. To enable efficient STS-Join processing on large sets of semantic trajectories, we develop trajectory pair filtering techniques and consider the parallel processing capabilities of modern processors. Specifically, we present a two-phase parallel search algorithm. We first group semantic trajectories based on their text information. The algorithm's per-group searches are independent of each other and thus can be performed in parallel. For each group, the trajectories are further partitioned based on the spatial domain. We generate spatial and textual summaries for each trajectory batch, based on which we develop batch filtering and trajectory-batch filtering techniques to prune unqualified trajectory pairs in a batch mode. Additionally, we propose an efficient divide-and-conquer algorithm to derive bounds of spatial similarity and textual similarity between two semantic trajectories, which enable us prune dissimilar trajectory pairs without the need of computing the exact value of spatio-textual similarity. Experimental study with large semantic trajectory data confirms that our algorithm of processing semantic trajectory join is capable of outperforming our well-designed baseline by a factor of 8-12.

There is an emerging trend of integrating machine learning (ML) techniques into database systems (DB). Considering that almost all the ML toolkits assume that the input of ML algorithms is a single table even though many real-world datasets are stored as multiple tables due to normalization in DB. Thus, data scientists have to perform joins before learning a ML model. This strategy is called learning after joins, which incurs redundancy avoided by normalization. In the area of ML, the Support Vector Machine (SVM) is one of the most standard classification tools. In this paper, we focus on the factorized SVM with gaussian kernels over normalized data. We present factorized learning approaches for two main SVM optimization methods, i.e., Gradient Descent (GD) and Sequential Minimal Optimization (SMO), by factorizing gaussian kernel function computation. Furthermore, we transform the normalized data into matrices, and boost the efficiency of SVM learning via linear algebra operations. Extensive experiments with nine real normalized data sets demonstrate the efficiency and scalability of our proposed approaches.

Region search is an important problem in location-based services due to its wide applications. In this paper, we study the problem of optimal region search with submodular maximization (ORS-SM). This problem considers a region as a connected subgraph. We compute an objective value over the locations in the region using a submodular function and a budget value by summing up the costs of edges in the region, and aim to search the region with the largest objective score under a budget value constraint. ORS-SM supports many applications such as the most diversified region search. We prove that the problem is NP-hard and develop two approximation algorithms with guaranteed error bounds. We conduct experiments on two applications using three real-world datasets. The results demonstrate that our algorithms can achieve high-quality solutions and are faster than a state-of-the-art method by orders of magnitude.

In recent years, spatial-keyword queries have attracted much attention with the fast development of location-based services. However, current spatial-keyword techniques are disk-based, which cannot fulfill the requirements of high throughput and low response time. With the surging data size, people tend to process data in distributed in-memory environments to achieve low latency. In this paper, we present the distributed solution, i.e., Skia (Spatial-Keyword In-memory Analytics), to provide a scalable backend for spatial-textual analytics. Skia introduces a two-level index framework for big spatial-textual data including: (1) efficient and scalable global index, which prunes the candidate partitions a lot while achieving small space budget; and (2) four novel local indexes, that further support low latency services for exact and approximate spatial-keyword queries. Skia can support common spatial-keyword queries via traditional SQL programming interfaces. The experiments conducted on large-scale real datasets have demonstrated the promising performance of the proposed indexes and our distributed solution.

Learning user’s preference from check-in data is important for POI recommendation. Yet, a user usually has visited some POIs while most of POIs are unvisited (i.e., negative samples). To leverage these “no-behavior” POIs, a typical approach is pairwise ranking, which constructs ranking pairs for the user and POIs. Although this approach is generally effective, the negative samples in ranking pairs are obtained randomly, which may fail to leverage “critical” negative samples in the model training. On the other hand, previous studies also utilized geographical feature to improve the recommendation quality. Nevertheless, most of previous works did not exploit geographical information comprehensively, which may also affect the performance. To alleviate these issues, we propose a geographical information based adversarial learning model (Geo-ALM), which can be viewed as a fusion of geographic features and generative adversarial networks. Its core idea is to learn the discriminator and generator interactively, by exploiting two granularity of geographic features (i.e., region and POI features). Experimental results show that Geo- ALM can achieve competitive performance, compared to several state-of-the-arts.

Computational sprinting is an effective mechanism to temporarily boost the performance of data center servers. However, given the great effect on performance improvement, how to make the sprinting process controllable and how to maximize the sprinting efficiency have not been well discussed yet. Those can be significant problems for a data center when computational sprinting is needed for more than a few minutes, since it requires the support of energy storage, whose capacity is limited. The control and efficiency of sprinting not only involve how fast to run servers and how to allocate resources to corunning workloads, but also the impact on power overload, and how to handle the overload with circuit breakers and energy storage to ensure power safety. Different workloads can impact sprinting in different ways, and hence efficient sprinting requires workload-specific strategies. In this paper, we propose SprintCon to realize controllable and efficient computational sprinting for data center servers. SprintCon mainly consists of a power load allocator and two different power controllers. The allocator analyzes how to divide the power load to different power sources. The server power controller adapts the CPU cores that process batch workloads, to improve the efficiency in terms of computing, energy and cost. The UPS power controller dynamically adjusts the discharge rate of UPS energy storage to satisfy the time-varying power demand of interactive workloads, and ensure power safety. The experiment results show that compared to state-of-theart solutions, SprintCon can achieve 6-56% better computing performance and up to 87% less demand of energy storage.

With the increasing availability of moving-object tracking data, use of this data for route search and recommendation is increasingly important. To this end, we propose a novel parallel split-and-combine approach to enable route search by locations (RSL-Psc). Given a set of routes, a set of places to visit O, and a threshold θ, we retrieve the route composed of sub-routes that (i) has similarity to O no less than θ and (ii) contains the minimum number of sub-route combinations. The resulting functionality targets a broad range of applications, including route planning and recommendation, ridesharing, and location-based services in general. To enable efficient and effective RSL-Psc computation on massive route data, we develop novel search space pruning techniques and enable use of the parallel processing capabilities of modern processors. Specifically, we develop two parallel algorithms, Fully-Split Parallel Search (FSPS) and Group-Split Parallel Search (GSPS). We divide the route split-and-combine task into ∑k=0 M S(|O|,k+1) sub-tasks, where M is the maximum number of combinations and S(⋅) is the Stirling number of the second kind. In each sub-task, we use network expansion and exploit spatial similarity bounds for pruning. The algorithms split candidate routes into sub-routes and combine them to construct new routes. The sub-tasks are independent and are performed in parallel. Extensive experiments with real data offer insight into the performance of the algorithms, indicating that our RSL-Psc problem can generate high-quality results and that the two algorithms are capable of achieving high efficiency and scalability.

Exploring Hidden Points of Interest (H-POIs), which are rarely referred in online search and recommendation systems due to insufficient check-in records, benefits business and individuals. In this work, we investigate how to eliminate the hidden feature of H-POIs by enhancing conventional crowdsourced ranking aggregation framework with heterogeneous (i.e., H-POI and Popular Point of Interest (P-POI)) pairwise tasks. We propose a two-phase solution focusing on both effectiveness and efficiency. In offline phase, we substantially narrow down the search space by retrieving a set of geo-textual valid heterogeneous pairs as the initial candidates and develop two practical data-driven strategies to compute worker qualities. In the online phase, we minimize the cost of assessment by introducing an active learning algorithm to jointly select pairs and workers with worker quality, uncertainty of P-POI rankings and uncertainty of the model taken into account. In addition, a (Minimum Spanning) Tree-constrained Skip search strategy is proposed for the purpose of reducing search time cost. Empirical experiments based on real POI datasets verify that the ranking accuracy of H-POIs can be greatly improved with small number of query iterations.

Sentence similarity modeling lies at the core of many natural language processing applications, and thus has received much attention. Owing to the success of word embeddings, recently, popular neural network methods achieved sentence embedding. Most of them focused on learning semantic information and modeling it as a continuous vector, yet the syntactic information of sentences has not been fully exploited. On the other hand, prior works have shown the benefits of structured trees that include syntactic information, while few methods in this branch utilized the advantages of word embeddings and another powerful technique-attention weight mechanism. This paper suggests to absorb their advantages by merging these techniques in a unified structure, dubbed as attention constituency vector tree (ACVT). Meanwhile, this paper develops a new tree kernel, known as ACVT kernel, which is tailored for sentence similarity measure based on the proposed structure. The experimental results, based on 19 widely used semantic textual similarity datasets, demonstrate that our model is effective and competitive, when compared against state-of-the-art models. Additionally, the experimental results validate that many attention weight mechanisms and word embedding techniques can be seamlessly integrated into our model, demonstrating the robustness and universality of our model.

Emerging data analytic workloads such as graph processing, neural network and edge data preprocesing desire efficient memory read operations. Unfortunately, due to the necessity of dynamic refresh, modern DRAM systems have to stall access during refresh cycles. As DRAM device density continues to grow, refresh operations can be a crucial throughput bottleneck. To fully unleash memory access performance, we revisit conventional refresh mechanism and DRAM architecture. We propose DR refresh, a specific refresh mechanism that enable read and refresh operations to be done simultaneously. We devise DR DRAM, a specific memory hardware system that can efficiently deploy DR refresh. Unlike traditional refresh, DR explores device refresh that only refreshes a designated device at a time. Meanwhile, DR increases read efficiency by recovering the inaccessible data that resides on a device under refreshing. We also propose Hybrid Refresh Main Memory (HRMM) which can designate refresh schemes (DR or traditional refresh) in a specific memory space. We expect that our design can benefit many real-life tasks such as SPEC CPU2006, CNN, LLT and PageRank.

As social networks become a major source of information, predicting the outcome of information diffusion has appeared intriguing to both researchers and practitioners. By organizing and categorizing the joint efforts of numerous studies on popularity prediction, this article presents a hierarchical taxonomy and helps to establish a systematic overview of popularity prediction methods for microblog. Specifically, we uncover three lines of thoughts: the feature-based approach, time-series modelling, and the collaborative filtering approach and analyse them, respectively. Furthermore, we also categorize prediction methods based on their underlying rationale: whether they attempt to model the motivation of users or monitor the early responses. Finally, we put these prediction methods to test by performing experiments on real-life data collected from popular social networks Twitter and Weibo. We compare the methods in terms of accuracy, efficiency, timeliness, robustness, and bias. As far as we are concerned, there is no precedented survey aimed at microblog popularity prediction at the time of submission. By establishing a taxonomy and evaluation for the first time, we hope to provide an in-depth review of state-of-the-art prediction methods and point out directions for further research. Our evaluations show that time-series modelling has the advantage of high accuracy and the ability to improve over time. The feature-based methods using only temporal features performs nearly as well as using all possible features, producing average results. This suggests that temporal features do have strong predictive power and that power is better exploited with time-series models. On the other hand, this implies that we know little about the future popularity of an item before it is posted, which may be the focus of further research.

Aggregate nearest neighbor (ANN) query has been studied in both the Euclidean space and road networks. The flexible aggregate nearest neighbor (FANN) problem further generalizes ANN by introducing an extra flexibility. Given a set of data points P, a set of query points Q, and a user-defined flexibility parameter φ that ranges in (0, 1], an FANN query returns the best candidate from P, which minimizes the aggregate (usually max or sum) distance to any φ |Q| objects in Q. In this paper, we focus on the problem in road networks (denoted as FANNR), and present a series of universal (i.e., suitable for both max and sum) algorithms to answer FANNRqueries in road networks, including a Dijkstra-based algorithm enumerating P, a queue-based approach that processes data points from-near-to-far, and a framework that combines Incremental Euclidean Restriction (IER) and kNN. We also propose a specific exact solution to max-FANNRand a specific approximate solution to sum-FANNRwhich can return a near-optimal result with a guaranteed constant-factor approximation. These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend the FANNRto k-FANNR, and successfully adapt most of the proposed algorithms to answer k-FANNRqueries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real road networks to demonstrate their superior efficiency and high quality.

Modern bike sharing system, in which bikes can be parked freely, extends the flexibility of traditional bike sharing system and thus has greatly facilitated urban transportation. However, the balance of such system is often broken by the user behaviors. And how to manage a large number of bikes which parked randomly in a city is a difficult problem. To tackle this problem, we propose a two-step solution. First, we deal with the bike trajectory data and design the Spatial-Temporal Bike Flow Prediction (ST-BFP) model, which is a convolutional network based on residual framework with history external factors to predict the bike flows. Second, to make the system return to balance state as soon as possible, we propose an Improved Local Search Algorithm (ILSA) for path planning with multiple carriers based on forecast result, which schedules multiple carriers in real time to complete the rebalance task collaboratively. Finally, we validate our model and algorithm via real-data based experiment. Experimental results demonstrate that our method can balance the entire system efficiently.

Sentence similarity modeling lies at the core of many natural language processing applications, and thus has received much attention. Owing to the success of word embeddings, recently, popular neural network methods have achieved sentence embedding, obtaining attractive performance. Nevertheless, most of them focused on learning semantic information and modeling it as a continuous vector, while the syntactic information of sentences has not been fully exploited. On the other hand, prior works have shown the benefits of structured trees that include syntactic information, while few methods in this branch utilized the advantages of word embeddings and another powerful technique ? attention weight mechanism. This paper makes the first attempt to absorb their advantages by merging these techniques in a unified structure, dubbed as ACV-tree. Meanwhile, this paper develops a new tree kernel, known as ACVT kernel, that is tailored for sentence similarity measure based on the proposed structure. The experimental results, based on 19 widely-used datasets, demonstrate that our model is effective and competitive, compared against state-of-the-art models.

Shortest path query is one of the most fundamental and classic problems in graph analytics, which returns the complete shortest path between any two vertices. However, in many real-life scenarios, only critical vertices on the shortest path are desirable and it is unnecessary to search for the complete path. This paper investigates the shortest path sketch by defining a top- $k$ critical vertices ( $k$ CV) query on the shortest path. Given a source vertex $s$ and target vertex $t$ in a graph, $k$ CV query can return the top- $k$ significant vertices on the shortest path $SP(s,t)$ . The significance of the vertices can be predefined. The key strategy for seeking the sketch is to apply off-line preprocessed distance oracle to accelerate on-line real-time queries. This allows us to omit unnecessary vertices and obtain the most representative sketch of the shortest path directly. We further explore a series of methods and optimizations to answer $k$ CV query on both centralized and distributed platforms, using exact and approximate approaches, respectively. We evaluate our methods in terms of time, space complexity and approximation quality. Experiments on large-scale real-world networks validate that our algorithms are of high efficiency and accuracy.

The prevalence of mobile Internet techniques and Online-To-Offline (O2O) business models has led the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC is to assign real-time tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects, tasks and workers, or assume the static offline scenarios, where the spatio-temporal information of all the tasks and workers is known in advance. Recently, some new emerging O2O applications incur new challenges: SC platforms need to assign three types of objects, tasks, workers and workplaces, and support dynamic real-time online scenarios, where the existing solutions cannot handle. In this paper, based on the aforementioned challenges, we formally define a novel dynamic online task assignment problem, called the trichromatic online matching in real-time spatial crowdsourcing (TOM) problem, which is proven to be NP-hard. Thus, we first devise an efficient greedy online algorithm. However, the greedy algorithm can be trapped into local optimal solutions easily. We then present a threshold-based randomized algorithm that not only guarantees a tighter competitive ratio but also includes an adaptive optimization technique, which can quickly learn the optimal threshold for the randomized algorithm. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

WiFi Direct is a recent device-to-device communication technology standardized by the WiFi Alliance. Its increasing availability on popular mobile systems (e.g. Android) presents a unique opportunity for developers to implement mobile social networks (MSNs), a new paradigm that facilitates data dissemination without Internet access by leveraging human mobility and short-range communication technologies. Since WiFi Direct is not originally designed for such applications, it is significant to learn its performance in practice. In this paper, we investigate goodput and fairness of WiFi Direct for data dissemination in MSNs. To this end, we develop an MSN application and conduct three sets of experiments on a testbed comprising several Android devices. Experimental results show that the data loads and mobility of nodes greatly impact the goodput and fairness.

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.

We present the Simba (Spatial In-Memory Big data Analytics) system, which offers scalable and efficient in-memory spatial query processing and analytics for big spatial data. Simba natively extends the Spark SQL engine to support rich spatial queries and analytics through both SQL and DataFrame API. It enables the construction of indexes over RDDs inside the engine in order to work with big spatial data and complex spatial operations. Simba also comes with an effective query optimizer, which leverages its indexes and novel spatial-aware optimizations, to achieve both low latency and high throughput in big spatial data analysis. This demonstration proposal describes key ideas in the design of Simba, and presents a demonstration plan.

As location-based services (LBSs) become popular, location-dependent queries have raised serious privacy concerns since they may disclose sensitive information in query processing. Among typical queries supported by LBSs, shortest path queries may reveal information about not only current locations of the clients, but also their potential destinations and travel plans. Unfortunately, existing methods for private shortest path computation suffer from issues of weak privacy property, low performance or poor scalability. In this paper, we aim at a strong privacy guarantee, where the adversary cannot infer almost any information about the queries, with better performance and scalability. To achieve this goal, we introduce a general system model based on the concept of Oblivious Storage (OS), which can deal with queries requiring strong privacy properties. Furthermore, we propose a new oblivious shuffle algorithm to optimize an existing OS scheme. By making trade-offs between query performance, scalability and privacy properties, we design different schemes for private shortest path computation. Eventually, we comprehensively evaluate our schemes upon real road networks in a practical environment and show their efficiency.

Large spatial data becomes ubiquitous. As a result, it is critical to provide fast, scalable, and high-throughput spatial queries and analytics for numerous applications in location-based services (LBS). Traditional spatial databases and spatial analytics systems are disk-based and optimized for IO efficiency. But increasingly, data are stored and processed in memory to achieve low latency, and CPU time becomes the new bottleneck. We present the Simba (Spatial In-Memory Big data Analytics) system that offers scalable and efficient in-memory spatial query processing and analytics for big spatial data. Simba is based on Spark and runs over a cluster of commodity machines. In particular, Simba extends the Spark SQL engine to support rich spatial queries and analytics through both SQL and the DataFrame API. It introduces indexes over RDDs in order to work with big spatial data and complex spatial operations. Lastly, Simba implements an effective query optimizer, which leverages its indexes and novel spatial-aware optimizations, to achieve both low latency and high throughput. Extensive experiments over large data sets demonstrate Simba's superior performance compared against other spatial analytics system.

Cloud storage system poses new challenges to the community to support efficient concurrent querying tasks for various data-intensive applications, where indices always hold important positions. In this paper, we explore a practical method to construct a two-layer indexing scheme for multi-dimensional data in diverse server-centric cloud storage system. We first propose RT-HCN, an indexing scheme integrating R-tree based indexing structure and HCN-based routing protocol. RT-HCN organizes storage and compute nodes into an HCN overlay, one of the newly proposed sever-centric data center topologies. Based on the properties of HCN, we design a specific index mapping technique to maintain layered global indices and corresponding query processing algorithms to support efficient query tasks. Then, we expand the idea of RT-HCN onto another server-centric data center topology DCell, discovering a potential generalized and feasible way of deploying two-layer indexing schemes on other server-centric networks. Furthermore, we prove theoretically that RT-HCN is both space-efficient and query-efficient, by which each node actually maintains a tolerable number of global indices while high concurrent queries can be processed within accepted overhead. We finally conduct targeted experiments on Amazon's EC2 platforms, comparing our design with RT-CAN, a similar indexing scheme for traditional P2P network. The results validate the query efficiency, especially the speedup of point query of RT-HCN, depicting its potential applicability in future data centers.

Nowadays massive log streams are generated from many Internet and cloud services. Storing log streams consumes a large amount of disk space and incurs high cost. Traditional compression methods can be applied to reduce storage cost, but are inefficient for log analysis, because fetching relevant log entries from compressed data often requires retrieval and decompression of large blocks of data. We propose a column-wise compression approach for well-formatted log streams, where each log entry can be independently compressed or decompressed for analysis. Specifically, we separate a log entry into several columns and compress each column with different models. We have implemented our approach as a library and integrated it into two applications, a log search system and a log joining system. Experimental results show that our compression scheme outperforms traditional compression methods for decompression times and has a competitive compression ratio. For log search, our approach achieves better query times than using traditional compression algorithms for both in-core and out-of-core cases. For joining log streams, our approach achieves the same join quality with only 30% memory of uncompressed streams.

Channel interference and node mobility cause significant performance degradation to wireless networks. In multichannel multi-flow mobile cognitive ad hoc networks, it becomes even worse due to both unexpected primary user activities and potential interference among multiple flows. In this paper, we propose a Joint Routing and Channel Assignment (JRCA) approach based on delay prediction. Firstly, it formulates the JRCA problem with the objective of delay minimization. Next, a delay prediction model is proposed based on the channel collision probability. Then, a heuristic algorithm joints routing and channel assignment is designed to solve the JRCA problem. the JRCA algorithm can find out the path with minimal end- toend (e2e) delay. NS2-based simulation results demonstrate that the JRCA approach significantly outperforms related proposals in terms of average e2e delay.

As cloud computing has become prominent, the need for searching cloud data has grown increasingly urgent. However, cloud search may be incorrect due to errors of cloud providers and attacks from other malicious tenants. Previous work on verifiable computing returns results with probabilistically checkable proofs, which targets at different applications other than search and requires a large computation overhead. We propose a hybrid approach for generating proofs of cloud search results. Specifically, we model search indices as sets and search operations as set intersections, and build proofs based on RSA accumulators and aggregated membership and no membership witnesses. Because generating witnesses for large sets is computationally expensive, we employ interval-based witnesses for fast proof generation. To reduce proof size, our hybrid method uses Bloom filters when set difference is large. Evaluation on real datasets shows that our hybrid approach generates proofs in an average of 0.197s, up to 83.2% faster than previous work with a smaller proof size. Experiments also show our approach allows incremental updates with constant cost.

Probabilistic range query (PRQ) over uncertain moving objects has attracted much attentions in recent years. Most of existing works focus on the PRQ for objects moving freely in two-dimensional (2D) space. In contrast, this paper studies the PRQ over objects moving in a constrained 2D space where objects are forbidden to be located in some specific areas. We dub it the constrained space probabilistic range query (CSPRQ). We analyze its unique properties and show that to process the CSPRQ using a straightforward solution is infeasible. The key idea of our solution is to use a strategy calledpre-approximationthat can reduce the initial problem to a highly simplified version, implying that it makes the rest of steps easy to tackle. In particular, this strategy itself is pretty simple and easy to implement. Furthermore, motivated by the cost analysis, we further optimize our solution. The optimizations are mainly based on two insights: (i) the number ofeffective subdivisions is no more than 1; and (ii) an entity with the largerspanis more likely to subdivide a single region. We demonstrate the effectiveness and efficiency of our proposed approaches through extensive experiments under various experimental settings, and highlight an extra finding—the precomputation based method suffers a non-trivial preprocessing time, which offers an important indication sign for the future research.

With the enormous and increasing user demand, I/O performance is one of the primary considerations to build a data center. Several new technologies in data centers, such as tiered storage [33], prompt the widespread usage of multi-level cache techniques. In these storage systems, the upper level storage typically serves as a cache for the lower level, which forms a distributed multi-level cache system. However, although many excellent multi-level cache algorithms are proposed to improve the I/O performance, they still have potential to be enhanced by investigating the history information of hints [28]. To address this challenge, in this paper, we propose a novel Hint Frequency-based Approach (HFA), to improve the overall multi-level cache performance of storage systems. The main idea of HFA is using hint frequencies (the total number of demotions/promotions by employing demote/promote hints) to efficiently explore the valuable history information of data blocks among multiple levels. HFA can be applied with several popular multi-level cache algorithms, such as Demote, Promote, Hint-K, etc. Simulation results show that, compared to original multi-level cache algorithms such as Demote, Promote and Hint-K, HFA can improve the I/O performance by up to 20% under different I/O workloads.

In this paper, we investigate the secure nearest neighbor (SNN) problem, in which a client issues an encrypted query point E(q) to a cloud service provider and asks for an encrypted data point in E(D) (the encrypted database) that is closest to the query point, without allowing the server to learn the plaintexts of the data or the query (and its result). We show that efficient attacks exist for existing SNN methods [21], [15], even though they were claimed to be secure in standard security models (such as indistinguishability under chosen plaintext or ciphertext attacks). We also establish a relationship between the SNN problem and the order-preserving encryption (OPE) problem from the cryptography field [6], [5], and we show that SNN is at least as hard as OPE. Since it is impossible to construct secure OPE schemes in standard security models [6], [5], our results imply that one cannot expect to find the exact (encrypted) nearest neighbor based on only E(q) and E(D). Given this hardness result, we design new SNN methods by asking the server, given only E(q) and E(D), to return a relevant (encrypted) partition E(G) from E(D) (i.e., G ⊆ D), such that that E(G) is guaranteed to contain the answer for the SNN query. Our methods provide customizable tradeoff between efficiency and communication cost, and they are as secure as the encryption scheme E used to encrypt the query and the database, where E can be any well-established encryption schemes.

This work deals with the approximate string search in large spatial databases. Specifically, we investigate range queries augmented with a string similarity search predicate in both euclidean space and road networks. We dub this query the spatial approximate string (SAS) query. In euclidean space, we propose an approximate solution, the MHR-tree, which embeds min-wise signatures into an R-tree. The min-wise signature for an index node u keeps a concise representation of the union of q-grams from strings under the subtree of u. We analyze the pruning functionality of such signatures based on the set resemblance between the query string and the q-grams from the subtrees of index nodes. We also discuss how to estimate the selectivity of a SAS query in euclidean space, for which we present a novel adaptive algorithm to find balanced partitions using both the spatial and string information stored in the tree. For queries on road networks, we propose a novel exact method, RSASSOL, which significantly outperforms the baseline algorithm in practice. The RSASSOL combines the q-gram-based inverted lists and the reference nodes based pruning. Extensive experiments on large real data sets demonstrate the efficiency and effectiveness of our approaches.

For GIS data situated on a road network, shortest path search is a basic operation. In practice, however, users are often interested at routing when certain constraints on the textual information have been also incorporated. This work complements the standard shortest path search with multiple keywords and an approximate string similarity function, where the goal is to find the shortest path that passes through at least one matching object per keyword; we dub this problem the multi-approximate-keyword routing (MAKR) query. We present both exact and approximate solutions. When the number κ of query keywords is small (e.g., κ ≤ 6), the exact solution works efficiently. However, when κ increases, it becomes increasingly expensive (especially on large GIS data). In this case, our approximate methods achieve superb query efficiency, excellent scalability, and high approximation quality, as indicated in our extensive experiments on large, real datasets (up to 2 million points on road networks with hundreds of thousands of nodes and edges). We also prove that one approximate method has a κ-approximation in the worst case.

Optimal location (OL) queries are a type of spatial queries particularly useful for the strategic planning of resources. Given a set of existing facilities and a set of clients, an OL query asks for a location to build a new facility that optimizes a certain cost metric (defined based on the distances between the clients and the facilities). Several techniques have been proposed to address OL queries, assuming that all clients and facilities reside in an Lpspace. In practice, however, movements between spatial locations are usually confined by the underlying road network, and hence, the actual distance between two locations can differ significantly from their Lpdistance. Motivated by the deficiency of the existing techniques, this paper presents the first study on OL queries in road networks. We propose a unified framework that addresses three variants of OL queries that find important applications in practice, and we instantiate the framework with several novel query processing algorithms. We demonstrate the efficiency of our solutions through extensive experiments with real data.

Aggregate similarity search, a.k.a. aggregate nearest neighbor (Ann) query, finds many useful applications in spatial and multimedia databases. Given a group Q of M query objects, it retrieves the most (or top-k) similar object to Q from a database P, where the similarity is an aggregation (e.g., sum, max) of the distances between the retrieved object p and all the objects in Q. In this paper, we propose an added flexibility to the query definition, where the similarity is an aggregation over the distances between p and any subset of ÆM objects in Q for some support 0 < Æ d 1. We call this new definition flexible aggregate similarity (Fann) search, which generalizes the Ann problem. Next, we present algorithms for answering Fann queries exactly and approximately. Our approximation algorithms are especially appealing, which are simple, highly efficient, and work well in both low and high dimensions. They also return nearoptimal answers with guaranteed constant-factor approximations in any dimensions. Extensive experiments on large real and synthetic datasets from 2 to 74 dimensions have demonstrated their superior efficiency and high quality.

Given a set of points P and a query set Q, a group enclosing query (Geq) fetches the point p* ∈ P such that the maximum distance of p* to all points in Q is minimized. This problem is equivalent to the Min-Max case (minimizing the maximum distance) of aggregate nearest neighbor queries for spatial databases. This work first designs a new exact solution by exploring new geometric insights, such as the minimum enclosing ball, the convex hull, and the furthest voronoi diagram of the query group. To further reduce the query cost, especially when the dimensionality increases, we turn to approximation algorithms. Our main approximation algorithm has a worst case √2-approximation ratio if one can find the exact nearest neighbor of a point. In practice, its approximation ratio never exceeds 1.05 for a large number of data sets up to six dimensions. We also discuss how to extend it to higher dimensions (up to 74 in our experiment) and show that it still maintains a very good approximation quality (still close to 1) and low query cost. In fixed dimensions, we extend the √2-approximation algorithm to get a (1 + ε)-approximate solution for the Geq problem. Both approximation algorithms have O(log N + M) query cost in any fixed dimension, where N and M are the sizes of the data set P and query group Q. Extensive experiments on both synthetic and real data sets, up to 10 million points and 74 dimensions, confirm the efficiency, effectiveness, and scalability of the proposed algorithms, especially their significant improvement over the state-of-the-art method.

This work presents a novel index structure, MHR-tree, for efficiently answering approximate string match queries in large spatial databases. The MHR-tree is based on the R-tree augmented with the min-wise signature and the linear hashing technique. The min-wise signature for an index node u keeps a concise representation of the union of q-grams from strings under the sub-tree of u. We analyze the pruning functionality of such signatures based on set resemblance between the query string and the q-grams from the sub-trees of index nodes. MHR-tree supports a wide range of query predicates efficiently, including range and nearest neighbor queries. We also discuss how to estimate range query selectivity accurately. We present a novel adaptive algorithm for finding balanced partitions using both the spatial and string information stored in the tree. Extensive experiments on large real data sets demonstrate the efficiency and effectiveness of our approach.

Finding the k nearest neighbors (kNN) of a query point, or a set of query points (kNN-Join) are fundamental problems in many application domains. Many previous efforts to solve these problems focused on spatial databases or stand-alone systems, where changes to the database engine may be required, which may limit their application on large data sets that are stored in a relational database management system. Furthermore, these methods may not automatically optimize kNN queries or kNN-Joins when additional query conditions are specified. In this work, we study both the kNN query and the kNN-Join in a relational database, possibly augmented with additional query conditions. We search for relational algorithms that require no changes to the database engine. The straightforward solution uses the user-defined-function (UDF) that a query optimizer cannot optimize.We design algorithms that could be implemented by SQL operators without changes to the database engine, hence enabling the query optimizer to understand and generate the “best” query plan. Using only a small constant number of random shifts for databases in any fixed dimension, our approach guarantees to find the approximate kNN with only logarithmic number of page accesses in expectation with a constant approximation ratio and it could be extended to find the exact kNN efficiently in any fixed dimension. Our design paradigm easily supports the kNN-Join and updates. Extensive experiments on large, real and synthetic, data sets confirm the efficiency and practicality of our approach.

Given a set of points P and a query point q, the reverse furthest neighbor (Rfn) query fetches the set of points p isin P such that q is their furthest neighbor among all points in PU{q}. This is the monochromatic Rfn (Mrfn) query. Another interesting version of Rfn query is the bichromatic reverse furthest neighbor (Brfn) query. Given a set of points P, a query set Q and a query point q isin Q, a Brfn query fetches the set of points p isin P such that q is the furthest neighbor of p among all points in Q. The Rrfn query has many interesting applications in spatial databases and beyond. For instance, given a large residential database (as P) and a set of potential sites (as Q) for building a chemical plant complex, the construction site should be selected as the one that has the maximum number of reverse furthest neighbors. This is an instance of the Brfn query. This paper presents the challenges associated with such queries and proposes efficient, R-tree based algorithms for both monochromatic and bichromatic versions of the Rrfn queries. We analyze properties of the Rrfn query that differentiate it from the widely studied reverse nearest neighbor queries and enable the design of novel algorithms. Our approach takes advantage of the furthest Voronoi diagrams as well as the convex hulls of either the data set P (in the Mrfn case) or the query set Q (in the Brfn case). For the Brfn queries, we also extend the analysis to the situation when Q is large in size and becomes disk-resident. Experiments on both synthetic and real data sets confirm the efficiency and scalability of proposed algorithms over the brute-force search based approach.