Search

Cliques refer to subgraphs in an undirected graph such that vertices in each subgraph are pairwise adjacent. The maximum clique problem, to find the clique with most vertices in a given graph, has been extensively studied. Besides its theoretical value as an NP-hard problem, the maximum clique problem is known to have direct applications in various fields, such as community search in social networks and social media, team formation in expert networks, gene expression and motif discovery in bioinformatics and anomaly detection in complex networks, revealing the structure and function of networks. However, algorithms designed for the maximum clique problem are expensive to deal with real-world networks. In this paper, we first devise a randomized algorithm for the maximum clique problem. Different from previous algorithms that search from each vertex one after another, our approach RMC, for the randomized maximum clique problem, employs a binary search while maintaining a lower bound $\underline{\omega _c}$ ω c ̲ and an upper bound $\overline{\omega _c}$ ω c ¯ of $\omega (G)$ ω (G) . In each iteration, RMC attempts to find a $\omega _t$ ω t -clique where $\omega _t=\lfloor (\underline{\omega _c}+\overline{\omega _c})/2\rfloor$ ω t = ⌊ (ω c ̲ + ω c ¯) / 2 ⌋ . As finding $\omega _t$ ω t in each iteration is NP-complete, we extract a seed set $S$ S such that the problem of finding a $\omega _t$ ω t -clique in $G$ G is equivalent to finding a $\omega _t$ ω t -clique in $S$ S with probability guarantees ($\geq$ ≥ $ 1-n^{-c}$ 1 - n - c ). We propose a novel iterative algorithm to determine the maximum clique by searching a $k$ k -clique in $S$ S starting from $k=\underline{\omega _c}+1$ k = ω c ̲ + 1 until $S$ S becomes $\lbrace \rbrace$ { } , when more iterations benefit marginally. Due to the potential inconsistency of maximum clique algorithms, we study the problem of maximum clique enumeration and propose an efficient algorithm RMCE to enumerate all maximum cliques in a given graph. As confirmed by the experiments, both RMC and RMCE are much more efficient and robust than previous solutions, RMC can always find the exact maximum clique, and RMCE can always enumerate all maximum cliques in a given graph. [ABSTRACT FROM AUTHOR]

In real-world graphs such as social networks, Semantic Web and biological networks, each vertex usually contains rich information, which can be modeled by a set of tokens or elements. In this paper, we study a subgraph matching with set similarity (SMS$^2$ ) query over a large graph database, which retrieves subgraphs that are structurally isomorphic to the query graph, and meanwhile satisfy the condition of vertex pair matching with the (dynamic) weighted set similarity. To efficiently process the SMS $^2$ query, this paper designs a novel lattice-based index for data graph, and lightweight signatures for both query vertices and data vertices. Based on the index and signatures, we propose an efficient two-phase pruning strategy including set similarity pruning and structure-based pruning, which exploits the unique features of both (dynamic) weighted set similarity and graph topology. We also propose an efficient dominating-set-based subgraph matching algorithm guided by a dominating set selection algorithm to achieve better query performance. Extensive experiments on both real and synthetic datasets demonstrate that our method outperforms state-of-the-art methods by an order of magnitude. [ABSTRACT FROM AUTHOR]

Searching similar graphs in graph databases for a query graph has attracted extensive attention recently. Existing works on graph similarity queries are threshold based approaches which return graphs with distances to the query smaller than a given threshold. However, in many applications the number of answer graphs for the same threshold can vary significantly for different queries. In this paper, we study the problem of finding top- $k$ k most similar graphs for a query under the distance measure based on maximum common subgraph (MCS). Since computing MCS is NP-hard, we devise a novel framework to prune unqualified graphs based on the lower bounds of graph distance, and accordingly derive four lower bounds with different tightness and computational cost for pruning. To further reduce the number of MCS computations, we also propose an improved framework based on both lower and upper bounds, and derive three new upper bounds. To support efficient pruning, we design three indexes with different tradeoffs between pruning power and construction cost. To accelerate the index construction, we explore bound relaxation techniques, based on which approximate indexes can be efficiently built. We conducted extensive performance studies on real-life graph datasets to validate the effectiveness and efficiency of our approaches. [ABSTRACT FROM AUTHOR]

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. Since these problems are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets. [ABSTRACT FROM AUTHOR]

Spatial co-location patterns are subsets of spatial features usually located together in geographic space. Recent literature has provided different approaches to discover co-location patterns over point spatial data. However, most approaches consider the neighborhood relationship among spatial objects as binary and are mainly designed for point spatial features, thus are not appropriate for extended spatial features such as line strings and polygons, the neighborhood relationship among which is naturally continuous. This paper adopts a buffer-based model for measuring the spatial relationship of extended objects and mining co-location patterns. While the buffer-based model has several advantages for extended spatial features, it involves high computational complexity due to the expensive buffer-level overlay operation. To tackle this challenge, we introduce a coarse-level co-location mining framework, which follows a filter-and-refine paradigm. Within the framework, we develop a serious of rigorous upper bounds based on geometric property and progressively prune search space with these upper bounds. Moreover, we develop a join-less schema to further reduce computation cost of size-k(k > 2) co-location patterns. Finally, we conduct experiments with large-scale spatial data to validate the efficiency of the developed algorithms against several state-of-art methods. All experimental results demonstrate the superiority of our methods. [ABSTRACT FROM AUTHOR]

Automatic social circle detection in ego-networks is a fundamentally important task for social network analysis. So far, most studies focused on how to detect overlapping circles or how to detect based on both network structure and node profiles. This paper asks an orthogonal research question: how to detect circles by leveraging multiple views of the network structure? As a first step, we crawl ego networks from Twitter and model them by six views, including user relationships, user interactions, and user content. We then apply both standard and our modified multi-view spectral clustering techniques to detect circles on these ego-networks. By extensive automatic and manual evaluations, we deliver two major findings: first, multi-view clustering techniques detect better circles than single-view clustering methods; second, our modified clustering technique which presumes sparse networks are incomplete detects better circles than the standard clustering technique which ignores such potential incompleteness. In particular, the second finding makes us conjecture a direct application of standard clustering on potentially incomplete networks may yield biased results. We lightly investigate this issue by deriving a bias upper bound that integrates theories of spectral clustering and matrix perturbation, and discussing how the bound may be affected by several network characteristics. [ABSTRACT FROM PUBLISHER]

In this paper, we study a novel problem of influence maximization in trajectory databases that is very useful in precise location-aware advertising. It finds $k$ best trajectories to be attached with a given advertisement and maximizes the expected influence among a large group of audience. We show that the problem is NP-hard and propose both exact and approximate solutions to find the best set of trajectories. In the exact solution, we devise an expansion-based framework that enumerates trajectory combinations in a best-first manner and propose three types of upper bound estimation techniques to facilitate early termination. In addition, we propose a novel trajectory index to reduce the influence calculation cost. To support large $k$ , we propose a greedy solution with an approximation ratio of (1 − 1/e), whose performance is further optimized by a new proposed cluster-based method. We also propose a threshold method that can support any approximation ratio $\epsilon \in (0,1]$ . In addition, we extend our problem to support the scenario when there are a group of advertisements. In our experiments, we use real datasets to construct user profiles, motion patterns, and trajectory databases. The experimental results verified the efficiency of our proposed methods. [ABSTRACT FROM PUBLISHER]

An all-k-nearest-neighbor (AkNN) query finds from a given object set O , k nearest neighbors for each object in a specified query set Q. This operation is common in many applications such as GIS, data mining, and image analysis. Although it has received much attention in the Euclidean space, there is little prior work on the metric space. In this paper, we study the problem of AkNN retrieval in metric spaces, termed metric AkNN (MAkNN) search, and propose efficient algorithms for supporting MAk NN queries with arbitrary k value. Our methods utilize dynamic disk-based metric indexes (e.g., M-tree), employ a series of pruning rules, take advantage of grouping, reuse, pre-processing, and progressive pruning techniques, require no detailed representations of objects, and can be applied as long as the distance metric satisfies the triangle inequality. In addition, we extend our approaches to tackle metric self-AkNN (MSAkNN) search, a natural variation of MAkNN queries, where the query set Q is identical to the object set O. Extensive experiments using both real and synthetic data sets demonstrate, compared with state-of-the-art euclidean Ak NN, MAkNN, and MSAkNN algorithms, the performance of our proposed algorithms and the effectiveness of our presented techniques. [ABSTRACT FROM PUBLISHER]

Assessment of disclosure risk is of paramount importance in data privacy research and applications. The concept of differential privacy (DP) formalizes privacy in probabilistic terms and provides a robust concept for privacy protection. Practical applications of DP involve development of DP mechanisms to release data at a pre-specified privacy budget. In this paper, we generalize the widely used Laplace mechanism to the family of generalized Gaussian (GG) mechanism based on the $l_p$ global sensitivity of statistical queries. We explore the theoretical requirement for the GG mechanism to reach DP at prespecified privacy parameters, and investigate the connections and differences between the GG mechanism and the Exponential mechanism based on the GG distribution. We also present a lower bound on the scale parameter of the Gaussian mechanism of $(\epsilon, \delta)$ -probabilistic DP as a special case of the GG mechanism, and compare the utility of sanitized results in the tail probability and dispersion between the Gaussian and Laplace mechanisms. Lastly, we apply the GG mechanism in three experiments and compare the accuracy of sanitized results in the $l_1$ distance and Kullback-Leibler divergence, and examine the prediction power of a SVM classifier constructed with the sanitized data relative to the original results. [ABSTRACT FROM AUTHOR]

Information can be disseminated widely and rapidly through Online Social Networks (OSNs) with “word-of-mouth” effects. Viral marketing is such a typical application in which new products or commercial activities are advertised by some seed users in OSNs to other users in a cascading manner. The selection of initial seed users yields a tradeoff between the expense and reward of viral marketing. In this paper, we define a general profit metric that naturally combines the benefit of influence spread with the cost of seed selection in viral marketing. We carry out a comprehensive study on finding a set of seed nodes to maximize the profit of viral marketing. We show that the profit metric is significantly different from the influence metric in that it is no longer monotone. This characteristic differentiates the profit maximization problem from the traditional influence maximization problem. We develop new seed selection algorithms for profit maximization with strong approximation guarantees. We also derive several upper bounds to benchmark the practical performance of an algorithm on any specific problem instance. Experimental evaluations with real OSN datasets demonstrate the effectiveness of our algorithms and techniques. [ABSTRACT FROM PUBLISHER]

The problem of deriving lower and upper bounds for the edit distance between undirected, labeled graphs has recently received increasing attention. However, only one algorithm has been proposed that allegedly computes not only an upper but also a lower bound for non-uniform edit costs and incorporates information about both node and edge labels. In this paper, we demonstrate that this algorithm is incorrect. We present a corrected version \mathsf B\scriptstyleRANCH that runs in \mathcalO(n^2\Delta ^3+n^3) time, where \Delta is the maximum of the maximum degrees of input graphs G and H . We also develop a speed-up that runs in \mathcal{O}(n^2\Delta ^2+n^3) time and computes an only slightly less accurate lower bound. The lower bounds produced by \mathsf B\scriptstyleRANCH and \mathsf {B\scriptstyle{RANCH}}\mathsf{F\scriptstyle{AST}} are shown to be pseudo-metrics on a collection of graphs. Finally, we suggest an anytime algorithm \mathsf B\scriptstyleRANCH\mathsfT\scriptstyleIGHT that iteratively improves \mathsf B\scriptstyleRANCH ’s lower bound. \mathsf B\scriptstyleRANCH\mathsfT\scriptstyleIGHT runs in \mathcalO(n^3\Delta ^2+I(n^2\Delta ^3+n^3)) time, where the number of iterations $I$ is controlled by the user. A detailed experimental evaluation shows that all suggested algorithms are Pareto optimal, that they are very effective when used as filters for edit distance range queries, and that they perform excellently when used within classification frameworks. [ABSTRACT FROM AUTHOR]

In a social network, even about the same information the excitement between different users are different. If we want to spread a piece of new information and maximize the expected total amount of excitement, which seed users should we choose? This problem indeed is substantially different from the renowned influence maximization problem and cannot be tackled using the existing approaches. In this paper, motivated by the demand in a few interesting applications, we model the novel problem of activity maximization, and tackle the problem systematically. We first analyze the complexity and the approximability of the problem. We develop an upper bound and a lower bound that are submodular so that the Sandwich framework can be applied. We then devise a polling-based randomized algorithm that guarantees a data dependent approximation factor. Our experiments on four real data sets clearly verify the effectiveness and scalability of our method, as well as the advantage of our method against the other heuristic methods. [ABSTRACT FROM PUBLISHER]

A large amount of heterogeneous event data are increasingly generated, e.g., in online systems for Web services or operational systems in enterprises. Owing to the difference between event data and traditional relational data, the matching of heterogeneous events is highly non-trivial. While event names are often opaque (e.g., merely with obscure IDs), the existing structure-based matching techniques for relational data also fail to perform owing to the poor discriminative power of dependency relationships between events. We note that interesting patterns exist in the occurrence of events, which may serve as discriminative features in event matching. In this paper, we formalize the problem of matching events with patterns. A generic pattern based matching framework is proposed, which is compatible with the existing structure based techniques. To improve the matching efficiency, we devise several bounds of matching scores for pruning. Recognizing the np-hardness of the optimal event matching problem with patterns, we propose efficient heuristic. Finally, extensive experiments demonstrate the effectiveness of our pattern based matching compared with approaches adapted from existing techniques, and the efficiency improved by the bounding, pruning and heuristic methods. [ABSTRACT FROM AUTHOR]

Influence maximization is a recent but well-studied problem which helps identify a small set of users that are most likely to “influence” the maximum number of users in a social network. The problem has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the users, but location is an important factor in targeted marketing. In this paper, we propose and investigate the problem of influence maximization in location-aware social networks, or, more generally, Geo-social Influence Spanning Maximization. Given a query $q$ composed of a region $R$ , a regional acceptance rate $\rho$ , and an integer $k$ as a seed selection budget, our aim is to find the maximum geographic spanning regions (MGSR). We refer to this as the MGSR problem. Our approach differs from previous work as we focus more on identifying the maximum spanning geographical regions within a region $R$ , rather than just the number of activated users in the given network like the traditional influence maximization problem  [14] . Our research approach can be effectively used for online marketing campaigns that depend on the physical location of social users. To address the MGSR problem, we first prove NP-Hardness. Next, we present a greedy algorithm with a $1-1/e$ approximation ratio to solve the problem, and further improve the efficiency by developing an upper bounded pruning approach. Then, we propose the OIR -Tree index, which is a hybrid index combining ordered influential node lists with an R -tree. We show that our index based approach is significantly more efficient than the greedy algorithm and the upper bounded pruning algorithm, especially when $k$ is large. Finally, we evaluate the performance for all of the proposed approaches using three real datasets. [ABSTRACT FROM AUTHOR]

Feature selection approaches based on mutual information can be roughly categorized into two groups. The first group minimizes the redundancy of features between each other. The second group maximizes the new classification information of features providing for the selected subset. A critical issue is that large new information does not signify little redundancy, and vice versa. Features with large new information but with high redundancy may be selected by the second group, and features with low redundancy but with little relevance with classes may be highly scored by the first group. Existing approaches fail to balance the importance of both terms. As such, a new information term denoted as Independent Classification Information is proposed in this paper. It assembles the newly provided information and the preserved information negatively correlated with the redundant information. Redundancy and new information are properly unified and equally treated in the new term. This strategy helps find the predictive features providing large new information and little redundancy. Moreover, independent classification information is proved as a loose upper bound of the total classification information of feature subset. Its maximization is conducive to achieve a high global discriminative performance. Comprehensive experiments demonstrate the effectiveness of the new approach. [ABSTRACT FROM AUTHOR]

We study a nearest neighbor search problem on a matrix by its element values. Given a data matrix $D$ and a query matrix $q$ , the sub-window nearest neighbor search problem finds a sub-window of $D$ that is the most similar to $q$ . This problem has a wide range of applications, e.g., geospatial data integration, object detection, and motion estimation. In this paper, we propose an efficient progressive search solution that overcomes the drawbacks of existing solutions. First, we present a generic approach to build level-based lower bound functions on top of basic lower bound functions. Second, we develop a novel lower bound function for a group of sub-windows, in order to boost the efficiency of our solution. Furthermore, we extend our solution to support irregular-shaped queries. Experimental results on real data demonstrate the efficiency of our proposed methods. [ABSTRACT FROM AUTHOR]

With the development of location-based services (LBS), LBS users are generating more and more spatio-textual data, e.g., checkins and attraction reviews. Since a spatio-textual entity may have different representations, possibly due to GPS deviations or typographical errors, it calls for effective methods to integrate the spatio-textual data from different data sources. In this paper, we study the problem of top-$k$ spatio-textual similarity join (Topk-STJoin), which identifies the $k$ most similar pairs from two spatio-textual data sets. One big challenge in Topk-STJoin is to efficiently identify the top- $k$ similar pairs by considering both textual relevancy and spatial proximity. Traditional join algorithms that consider only one dimension (textual or spatial) are inefficient because they cannot utilize the pruning ability on the other dimension. To address this challenge, we propose a signature-based top-$k$ join framework. We first generate a spatio-textual signature set for each object such that if two objects are in the top- $k$ similar pairs, their signature sets must overlap. With this property, we can prune large numbers of dissimilar pairs without common signatures. We find that the order of accessing the signatures has a significant effect on the performance. So, we compute an upper bound for each signature and propose a best-first accessing method that preferentially accesses signatures with large upper bounds while those pairs with small upper bounds can be pruned. We prove the optimality of our best-first accessing method. Next, we optimize the spatio-textual signatures and propose progressive signatures to further improve the pruning power. Experimental results on real-world datasets show that our algorithm achieves high performance and good scalability, and significantly outperforms baseline approaches. [ABSTRACT FROM PUBLISHER]

The top-k dominating (TKD) query returns the k objects that dominate the maximum number of objects in a given dataset. It combines the advantages of skyline and top-k queries, and plays an important role in many decision support applications. Incomplete data exists in a wide spectrum of real datasets, due to device failure, privacy preservation, data loss, and so on. In this paper, for the first time, we carry out a systematic study of TKD queries on incomplete data, which involves the data having some missing dimensional value(s). We formalize this problem, and propose a suite of efficient algorithms for answering TKD queries over incomplete data. Our methods employ some novel techniques, such as upper bound score pruning, bitmap pruning, and partial score pruning, to boost query efficiency. Extensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness of our developed pruning heuristics and the performance of our presented algorithms. [ABSTRACT FROM AUTHOR]

Tweet streams provide a variety of real-life and real-time information on social events that dynamically change over time. Although social event detection has been actively studied, how to efficiently monitor evolving events from continuous tweet streams remains open and challenging. One common approach for event detection from text streams is to use single-pass incremental clustering. However, this approach does not track the evolution of events, nor does it address the issue of efficient monitoring in the presence of a large number of events. In this paper, we capture the dynamics of events using four event operations (create, absorb, split, and merge), which can be effectively used to monitor evolving events. Moreover, we propose a novel event indexing structure, called Multi-layer Inverted List (MIL), to manage dynamic event databases for the acceleration of large-scale event search and update. We thoroughly study the problem of nearest neighbour search using MIL based on upper bound pruning, along with incremental index maintenance. Extensive experiments have been conducted on a large-scale real-life tweet dataset. The results demonstrate the promising performance of our event indexing and monitoring methods on both efficiency and effectiveness. [ABSTRACT FROM PUBLISHER]

High utility sequential pattern mining has been considered as an important research problem and a number of relevant algorithms have been proposed for this topic. The main challenge of high utility sequential pattern mining is that, the search space is large and the efficiency of the solutions is directly affected by the degree at which they can eliminate the candidate patterns. Therefore, the efficiency of any high utility sequential pattern mining solution depends on its ability to reduce this big search space, and as a result, lower the computational complexity of calculating the utilities of the candidate patterns. In this paper, we propose efficient data structures and pruning technique which is based on Cumulated Rest of Match (CRoM) based upper bound. CRoM, by defining a tighter upper bound on the utility of the candidates, allows more conservative pruning before candidate pattern generation in comparison to the existing techniques. In addition, we have developed an efficient algorithm, High Utility Sequential Pattern Extraction (HuspExt), which calculates the utilities of the child patterns based on that of the parents’. Substantial experiments on both synthetic and real datasets from different domains show that, the proposed solution efficiently discovers high utility sequential patterns from large scale datasets with different data characteristics, under low utility thresholds. [ABSTRACT FROM AUTHOR]

Influence maximization, defined as finding a small subset of nodes that maximizes spread of influence in social networks, is NP-hard under both Independent Cascade (IC) and Linear Threshold (LT) models, where many greedy-based algorithms have been proposed with the best approximation guarantee. However, existing greedy-based algorithms are inefficient on large networks, as it demands heavy Monte-Carlo simulations of the spread functions for each node at the initial step [7]. In this paper, we establish new upper bounds to significantly reduce the number of Monte-Carlo simulations in greedy-based algorithms, especially at the initial step. We theoretically prove that the bound is tight and convergent when the summation of weights towards (or from) each node is less than 1. Based on the bound, we propose a new Upper Bound based Lazy Forward algorithm ( UBLF in short) for discovering the top-k influential nodes in social networks. We test and compare UBLF with prior greedy algorithms, especially CELF [30]. Experimental results show that UBLF reduces more than 95 percent Monte-Carlo simulations of CELF and achieves about 2\-10 times speedup when the seed set is small. [ABSTRACT FROM PUBLISHER]

With the explosion of GPS-enabled smartphones and social media platforms, geo-social networks are increasing as tools for businesses to promote their products or services. Influence maximization, which aims to maximize the expected spread of influence in the networks, has drawn increasing attention. However, most recent work tries to study influence maximization by only considering geographic distance, while ignoring the influence of users’ spatio-temporal behavior on information propagation or location promotion, which can often lead to poor results. To relieve this problem, we propose a Similarity-aware Influence Maximization (SIM) model to efficiently maximize the influence spread by taking the effect of users’ spatio-temporal behavior into account, which is more reasonable to describe the real information propagation. We first calculate the similarity between users according to their historical check-ins, and then we propose a Propagation to Consumption (PTC) model to capture both online and offline behaviors of users. Finally, we propose two greedy algorithms to efficiently maximize the influence spread. The extensive experiments over real datasets demonstrate the efficiency and effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The Earth Mover's Distance (EMD) is a robust similarity measure between two histograms (e.g., probability distributions). It has been extensively used in a wide range of applications, e.g., multimedia, data mining, computer vision, etc. As EMD is a computationally intensive operation, many efficient lower and upper bound functions of EMD have been developed. However, they provide no guarantee on the error. In this work, we study how to compute approximate EMD value with bounded error. First, we develop a parametric dual bound function for EMD, in order to offer sufficient trade-off points for optimization. After that, we propose an approximation framework that leverages on lower and upper bound functions to compute approximate EMD with error guarantee. Then, we present three solutions to solve our problem. Experimental results on real data demonstrate the efficiency and the effectiveness of our proposed solutions. [ABSTRACT FROM AUTHOR]

Efficient event stream dissemination is a challenging problem in large-scale Online Social Network (OSN) systems due to the costly inter-server communications caused by the per-user view data storage. To solve the problem, previous schemes mainly explore the structures of social graphs to reduce the inter-server traffic. Based on the observation of high cluster coefficients in OSNs, a state-of-the-art social piggyback scheme can save redundant messages by exploiting an intrinsic hub-structure in an OSN graph for message piggybacking. Essentially, finding the best hub-structure for piggybacking is equivalent to finding a variation of the densest sub-graph. The existing scheme computes the best hub-structure by iteratively removing the node with the minimum weighted degree. Such a scheme incurs a worst computation cost of $O(n^2)$ O (n 2) , making it not scalable to large-scale OSN graphs. Using alternative hub-structure instead of the best hub-structure can speed up the piggyback assignment. However, they greatly sacrifice the communication efficiency of the assignment schedule. Different from the existing designs, in this work, we propose a QuickPoint algorithm, which removes a fraction of nodes in each iteration in finding the best hub-structure. We mathematically prove that QuickPoint converges in $O(log_an) (a>1)$ O (l o g a n) (a > 1) iterations in finding the best hub-structure for efficient piggyback. We implement QuickPoint in parallel atop Pregel, a vertex-centric distributed graph processing platform. Comprehensive experiments using large-scale data from Twitter and Flickr show that our scheme is 38.8× more efficient compared to existing schemes. [ABSTRACT FROM AUTHOR]

Ride-sharing (RS) has great values in saving energy and alleviating traffic pressure. Existing studies can be improved for better efficiency. Therefore, we propose a new ride-sharing model, where each driver has a requirement that if the driver shares a ride with a rider, the shared route percentage (i.e., the ratio of the shared route's distance to the driver's total travel distance) exceeds an expectation rate of the driver, e.g., 0.8. We consider two variants of this problem. The first considers multiple drivers and multiple riders and aims to compute driver-rider pairs to maximize the overall shared route percentage (SRP). We model this problem as the maximum weighted bigraph matching problem, where the vertices are drivers and riders, edges are driver-rider pairs, and edge weights are driver-rider's SRP. However, it is rather expensive to compute the SRP values for large numbers of driver-rider pairs on road networks. To address this problem, we propose an efficient method to prune many unnecessary driver-rider pairs and avoid computing the SRP values for every pair. To improve the efficiency, we propose an approximate method with error bound guarantee. The basic idea is that we compute an upper bound and a lower bound for each driver-rider pair in constant time. Then, we estimate an upper bound and a lower bound of the graph matching. Next, we select some driver-rider pairs, compute their real shortest-route distance, and update the lower and upper bounds of the maximum graph matching. We repeat above steps until the ratio of the upper bound to the lower bound is not larger than a given approximate rate. The second considers multiple drivers and a single rider and aims to find the top-$k$ drivers for the rider with the largest SRP. We first prune a large number of drivers that cannot meet the SRP requirements. Then, we propose a best-first algorithm that progressively selects the drivers with high probability to be in the top- $k$ results and prunes the drivers that cannot be in the top- $k$ results. Extensive experiments on real-world datasets demonstrate the superiority of our method. [ABSTRACT FROM PUBLISHER]

Similarity join is a fundamental operation in data cleaning and integration. Existing similarity-join methods utilize the string similarity to quantify the relevance but neglect the knowledge behind the data, which plays an important role in understanding the data. Thanks to public knowledge bases, e.g., Freebase and Yago, we have an opportunity to use the knowledge to improve similarity join. To address this problem, we study knowledge-aware similarity join, which, given a knowledge hierarchy and two collections of objects (e.g., documents), finds all knowledge-aware similar object pairs. To the best of our knowledge, this is the first study on knowledge-aware similarity join. There are two main challenges. The first is how to quantify the knowledge-aware similarity. The second is how to efficiently identify the similar pairs. To address these challenges, we first propose a new similarity metric to quantify the knowledge-aware similarity using the knowledge hierarchy. We then devise a filter-and-verification framework to efficiently identify the similar pairs. We propose effective signature-based filtering techniques to prune large numbers of dissimilar pairs and develop efficient verification algorithms to verify the candidates that are not pruned in the filter step. Experimental results on real-world datasets show that our method significantly outperforms baseline algorithms in terms of both efficiency and effectiveness. [ABSTRACT FROM PUBLISHER]

Spatio-textual queries retrieve the most similar objects with respect to a given location and a keyword set. Existing studies mainly focus on how to efficiently find the top-k result set given a spatio-textual query. Nevertheless, in many application scenarios, users cannot precisely formulate their keywords and instead prefer to choose them from some candidate keyword sets. Moreover, in information browsing applications, it is useful to highlight the objects with the tags (keywords) under which the objects have high rankings. Driven by these applications, we propose a novel query paradigm, namely reverse keyword search for s patio-textual top-k queries ( \mathcal RSTQ ). It returns the keywords under which a target object will be a spatio-textual top-k result. To efficiently process the new query, we devise a novel hybrid index KcR-tree to store and summarize the spatial and textual information of objects. By accessing the high-level nodes of KcR-tree, we can estimate the rankings of the target object without accessing the actual objects. To further improve the performance, we propose three query optimization techniques, i.e., KcR*-tree, lazy upper-bound updating, and keyword set filtering. We also extend \mathcal RSTQ to allow the input location to be a spatial region instead of a point. Extensive experimental evaluation demonstrates the efficiency of our proposed query techniques in terms of both the computational cost and I/O cost. [ABSTRACT FROM PUBLISHER]

The discovery of regions of interest in large cities is an important challenge. We propose and investigate a novel query called the path nearby cluster (PNC) query that finds regions of potential interest (e.g., sightseeing places and commercial districts) with respect to a user-specified travel route. Given a set of spatial objects $O$ (e.g., POIs, geo-tagged photos, or geo-tagged tweets) and a query route $q$ , if a cluster $c$ has high spatial-object density and is spatially close to $q$ , it is returned by the query (a cluster is a circular region defined by a center and a radius). This query aims to bring important benefits to users in popular applications such as trip planning and location recommendation. Efficient computation of the PNC query faces two challenges: how to prune the search space during query processing, and how to identify clusters with high density effectively. To address these challenges, a novel collective search algorithm is developed. Conceptually, the search process is conducted in the spatial and density domains concurrently. In the spatial domain, network expansion is adopted, and a set of vertices are selected from the query route as expansion centers. In the density domain, clusters are sorted according to their density distributions and they are scanned from the maximum to the minimum. A pair of upper and lower bounds are defined to prune the search space in the two domains globally. The performance of the PNC query is studied in extensive experiments based on real and synthetic spatial data. [ABSTRACT FROM PUBLISHER]

Location-based services (LBS) enable mobile users to query points-of-interest (e.g., restaurants, cafes) on various features (e.g., price, quality, variety). In addition, users require accurate query results with up-to-date travel times. Lacking the monitoring infrastructure for road traffic, the LBS may obtain live travel times of routes from online route APIs in order to offer accurate results. Our goal is to reduce the number of requests issued by the LBS significantly while preserving accurate query results. First, we propose to exploit recent routes requested from route APIs to answer queries accurately. Then, we design effective lower/upper bounding techniques and ordering techniques to process queries efficiently. Also, we study parallel route requests to further reduce the query response time. Our experimental evaluation shows that our solution is three times more efficient than a competitor, and yet achieves high result accuracy (above 98 percent). [ABSTRACT FROM PUBLISHER]