ORCID Profile
0000-0002-2674-1638
Current Organisation
University of Technology Sydney
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Research Topics
In Research Link Australia (RLA), "Research Topics" refer to ANZSRC FOR and SEO codes. These topics are either sourced from ANZSRC FOR and SEO codes listed in researchers' related grants or generated by a large language model (LLM) based on their publications.
Top 5 Research Topics
ANZSRC Field of Research (FoR)
Information Systems | Database Management | Pattern Recognition and Data Mining | Medical and Health Sciences not elsewhere classified | Data models storage and indexing | Graph social and multimedia data | Global Information Systems | Data management and data science | Query processing and optimisation
ANZSRC Socio-Economic Objective (SEO)
Information Processing Services (incl. Data Entry and Capture) | Electronic Information Storage and Retrieval Services | Expanding Knowledge in the Information and Computing Sciences | Environmental Lifecycle Assessment | Road Public Transport |
Related Links
Publications
Categorical top-k spatial influence query
Publisher: Springer Science and Business Media LLC
Date: 03-2017
Summarizing Order Statistics over Data Streams with Duplicates
Publisher: IEEE
Date: 2007
Influence zone: Efficiently processing reverse k nearest neighbors queries
Publisher: IEEE
Date: 04-2011
When Hierarchy Meets 2-Hop-Labeling
Publisher: ACM
Date: 27-05-2018
Shortest-path queries on complex networks
Publisher: Association for Computing Machinery (ACM)
Date: 07-2022
Abstract: The shortest-path query, which returns the shortest path between two vertices, is a basic operation on complex networks and has numerous applications. To handle shortest-path queries, one option is to use traversal-based methods (e.g., breadth-first search) another option is to use extension-based methods, i.e., extending existing methods that use indexes to handle shortest-distance queries to support shortest-path queries. These two types of methods make different trade-offs in query time and space cost, but comprehensive studies of their performance on real-world graphs are lacking. Moreover, extension-based methods usually use extra attributes to extend the indexes, resulting in high space costs. To address these issues, we thoroughly compare the two types of methods mentioned above. We also propose a new extension-based approach, Monotonic Landmark Labeling (MLL), to reduce the required space cost while still guaranteeing query time. We compare the performance of different methods on ten large real-world graphs with up to 5.5 billion edges. The experimental results reveal the characteristics of various methods, allowing practitioners to select the appropriate method for a specific application.
Efficiently identify local frequent keyword co-occurrence patterns in geo-tagged Twitter stream
Publisher: ACM
Date: 03-07-2014
Probabilistic Top-k Dominating Query over Sliding Windows
Publisher: Springer Berlin Heidelberg
Date: 2013
Probabilistic skyline operator over sliding windows
Publisher: Elsevier BV
Date: 11-2013
Managing Uncertain Data: Probabilistic Approaches
Publisher: IEEE
Date: 07-2008
DOI: 10.1109/WAIM.2008.42
Correction: A survey of community search over big graphs
Publisher: Springer Science and Business Media LLC
Date: 11-11-2020
A Fast Order-Based Approach for Core Maintenance
Publisher: IEEE
Date: 04-2017
DOI: 10.1109/ICDE.2017.93
ESPM: Efficient Spatial Pattern Matching
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 06-2020
Probabilistic Threshold Range Aggregate Query Processing over Uncertain Data
Publisher: Springer Berlin Heidelberg
Date: 2009
Distance labeling: on parallelism, compression, and ordering
Publisher: Springer Science and Business Media LLC
Date: 31-08-2021
Efficient top-k similarity join processing over multi-valued objects
Publisher: Springer Science and Business Media LLC
Date: 07-02-2014
ESPM: Efficient Spatial Pattern Matching (Extended Abstract)
Publisher: IEEE
Date: 04-2020
Range Search on Uncertain Trajectories
Publisher: ACM
Date: 17-10-2015
Effectively indexing the multi-dimensional uncertain objects for range searching
Publisher: ACM
Date: 27-03-2012
When engagement meets similarity
Publisher: Association for Computing Machinery (ACM)
Date: 06-2017
Abstract: In this paper, we investigate the problem of ( k,r )-core which intends to find cohesive subgraphs on social networks considering both user engagement and similarity perspectives. In particular, we adopt the popular concept of k -core to guarantee the engagement of the users (vertices) in a group (subgraph) where each vertex in a ( k,r )-core connects to at least k other vertices. Meanwhile, we consider the pairwise similarity among users based on their attributes. Efficient algorithms are proposed to enumerate all maximal ( k,r )-cores and find the maximum ( k,r )-core, where both problems are shown to be NP-hard. Effective pruning techniques substantially reduce the search space of two algorithms. A novel ( k,k' )-core based ( k,r )-core size upper bound enhances performance of the maximum ( k,r )-core computation. We also devise effective search orders for two mining algorithms where search priorities for vertices are different. Comprehensive experiments on real-life data demonstrate that the maximal/maximum ( k,r )-cores enable us to find interesting cohesive subgraphs, and performance of two mining algorithms is effectively improved by proposed techniques.
Efficiently Answering Span-Reachability Queries in Large Temporal Graphs
Publisher: IEEE
Date: 04-2020
Temporal and Heterogeneous Graph Neural Network for Financial Time Series Prediction
Publisher: ACM
Date: 17-10-2022
AOT: Pushing the Efficiency Boundary of Main-Memory Triangle Listing
Publisher: Springer International Publishing
Date: 2020
Vertex priority based butterfly counting for large-scale bipartite networks
Publisher: Association for Computing Machinery (ACM)
Date: 06-2019
Abstract: Bipartite networks are of great importance in many real-world applications. In bipartite networks, butterfly (i.e., a complete 2 x 2 biclique) is the smallest non-trivial cohesive structure and plays a key role. In this paper, we study the problem of efficient counting the number of butterflies in bipartite networks. The most advanced techniques are based on enumerating wedges which is the dominant cost of counting butterflies. Nevertheless, the existing algorithms cannot efficiently handle large-scale bipartite networks. This becomes a bottleneck in large-scale applications. In this paper, instead of the existing layer-priority-based techniques, we propose a vertex-priority-based paradigm BFC-VP to enumerate much fewer wedges this leads to a significant improvement of the time complexity of the state-of-the-art algorithms. In addition, we present cache-aware strategies to further improve the time efficiency while theoretically retaining the time complexity of BFC-VP. Moreover, we also show that our proposed techniques can work efficiently in external and parallel contexts. Our extensive empirical studies demonstrate that the proposed techniques can speed up the state-of-the-art techniques by up to two orders of magnitude for the real datasets.
Distributed subgraph matching on timely dataflow
Publisher: Association for Computing Machinery (ACM)
Date: 06-2019
Abstract: Recently there emerge many distributed algorithms that aim at solving subgraph matching at scale. Existing algorithm-level comparisons failed to provide a systematic view of distributed subgraph matching mainly due to the intertwining of strategy and optimization. In this paper, we identify four strategies and three general-purpose optimizations from representative state-of-the-art algorithms. We implement the four strategies with the optimizations based on the common Timely dataflow system for systematic strategy-level comparison. Our implementation covers all representative algorithms. We conduct extensive experiments for both unlabelled matching and labelled matching to analyze the performance of distributed subgraph matching under various settings, which is finally summarized as a practical guide.
SKPS: Towards Efficient Processing of Spatial-Keyword Publish/Subscribe System
Publisher: Springer International Publishing
Date: 2016
SKYPE: Top-k Spatial-keyword Publish/Subscribe Over Sliding Window
Publisher: Association for Computing Machinery (ACM)
Date: 03-2016
Abstract: As the prevalence of social media and GPS-enabled devices, a massive amount of geo-textual data has been generated in a stream fashion, leading to a variety of applications such as location-based recommendation and information dissemination. In this paper, we investigate a novel real-time top- k monitoring problem over sliding window of streaming data that is, we continuously maintain the top-k most relevant geo-textual messages (e.g., geo-tagged tweets) for a large number of spatial-keyword subscriptions (e.g., registered users interested in local events ) simultaneously. To provide the most recent information under controllable memory cost, sliding window model is employed on the streaming geo-textual data. To the best of our knowledge, this is the first work to study top- k spatial-keyword publish/subscribe over sliding window. A novel system, called Skype (Top-k Spatial-keyword Publish/Subscribe), is proposed in this paper. In Skype, to continuously maintain top- k results for massive subscriptions, we devise a novel indexing structure upon subscriptions such that each incoming message can be immediately delivered on its arrival. Moreover, to reduce the expensive top- k re-evaluation cost triggered by message expiration, we develop a novel cost-based k-skyband technique to reduce the number of re-evaluations in a cost-effective way. Extensive experiments verify the great efficiency and effectiveness of our proposed techniques.
Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs
Publisher: IEEE
Date: 05-2022
An Efficient Exact Nearest Neighbor Search by Compounded Embedding
Publisher: Springer International Publishing
Date: 2018
Mitigating the Impact of Data Sampling on Social Media Analysis and Mining
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 04-2020
On Scalable Computation of Graph Eccentricities
Publisher: ACM
Date: 10-06-2022
SRS
Publisher: Association for Computing Machinery (ACM)
Date: 09-2014
Abstract: Nearest neighbor searches in high-dimensional space have many important applications in domains such as data mining, and multimedia databases. The problem is challenging due to the phenomenon called "curse of dimensionality". An alternative solution is to consider algorithms that returns a c -approximate nearest neighbor ( c -ANN) with guaranteed probabilities. Locality Sensitive Hashing (LSH) is among the most widely adopted method, and it achieves high efficiency both in theory and practice. However, it is known to require an extremely high amount of space for indexing, hence limiting its scalability. In this paper, we propose several surprisingly simple methods to answer c -ANN queries with theoretical guarantees requiring only a single tiny index. Our methods are highly flexible and support a variety of functionalities, such as finding the exact nearest neighbor with any given probability. In the experiment, our methods demonstrate superior performance against the state-of-the-art LSH-based methods, and scale up well to 1 billion high-dimensional points on a single commodity PC.
Answering reachability and K-reach queries on large graphs with label constraints
Publisher: Springer Science and Business Media LLC
Date: 28-08-2021
Span-reachability querying in large temporal graphs
Publisher: Springer Science and Business Media LLC
Date: 23-11-2021
Efficient progressive minimum k-core search
Publisher: Association for Computing Machinery (ACM)
Date: 11-2020
Abstract: As one of the most representative cohesive subgraph models, k -core model has recently received significant attention in the literature. In this paper, we investigate the problem of the minimum k -core search: given a graph G , an integer k and a set of query vertices Q = { q }, we aim to find the smallest k -core subgraph containing every query vertex q ϵ Q. It has been shown that this problem is NP-hard with a huge search space, and it is very challenging to find the optimal solution. There are several heuristic algorithms for this problem, but they rely on simple scoring functions and there is no guarantee as to the size of the resulting subgraph, compared with the optimal solution. Our empirical study also indicates that the size of their resulting subgraphs may be large in practice. In this paper, we develop an effective and efficient progressive algorithm, namely PSA , to provide a good trade-off between the quality of the result and the search time. Novel lower and upper bound techniques for the minimum k -core search are designed. Our extensive experiments on 12 real-life graphs demonstrate the effectiveness and efficiency of the new techniques.
Progressive Top-K Nearest Neighbors Search in Large Road Networks
Publisher: ACM
Date: 31-05-2020
Global Reinforcement of Social Networks: The Anchored Coreness Problem
Publisher: ACM
Date: 31-05-2020
EDMS: A System for Efficient Processing Distance-Aware Influence Maximization
Publisher: Springer International Publishing
Date: 2016
Efficient Graph Hierarchical Decomposition with User Engagement and Tie Strength
Publisher: Springer International Publishing
Date: 2020
DSKQ: A system for efficient processing of diversified spatial-keyword query
Publisher: Springer International Publishing
Date: 2017
Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees
Publisher: Association for Computing Machinery (ACM)
Date: 2020
Abstract: Computing the shortest path between two vertices is a fundamental problem in road networks that is applied in a wide variety of applications. To support efficient shortest path query processing, a plethora of index-based methods have been proposed in the literature, but few of them can support dynamic road networks commonly encountered in practice, as their corresponding index structures cannot be efficiently maintained when the input road network is dynamically updated. Motivated by this, we study the shortest path index maintenance problem on dynamic road networks in this paper. We adopt Contraction Hierarchies (CH) as our underlying shortest path computation method because of its outstanding overall performance in pre-processing time, space cost, and query processing time and aim to design efficient algorithms to maintain the index structure, shortcut index , of CH when the input road network is dynamically updated. To achieve this goal, we propose a shortcut-centric paradigm focusing on exploring a small number of shortcuts to maintain the shortcut index. Following this paradigm, we design an auxiliary data structure named SS-Graph and propose a shortcut weight propagation mechanism based on the SS-Graph. With them, we devise efficient algorithms to maintain the shortcut index in the streaming update and batch update scenarios with non-trivial theoretical guarantees. We experimentally evaluate our algorithms on real road networks and the results demonstrate that our approach achieves 2--3 orders of magnitude speedup compared to the state-of-the-art algorithm for the streaming update.
Scaling Up Distance Labeling on Graphs with Core-Periphery Properties
Publisher: ACM
Date: 31-05-0061
Efficient Matrix Factorization on Heterogeneous CPU-GPU Systems
Publisher: IEEE
Date: 04-2021
Effectively indexing the uncertain space
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 09-2010
DOI: 10.1109/TKDE.2010.77
Inverted Linear Quadtree: Efficient Top K Spatial Keyword Search
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 07-2016
Risk Guarantee Prediction in Networked-Loans
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 07-2020
Abstract: The guaranteed loan is a debt obligation promise that if one corporation gets trapped in risks, its guarantors will back the loan. When more and more companies involve, they subsequently form complex networks. Detecting and predicting risk guarantee in these networked-loans is important for the loan issuer. Therefore, in this paper, we propose a dynamic graph-based attention neural network for risk guarantee relationship prediction (DGANN). In particular, each guarantee is represented as an edge in dynamic loan networks, while companies are denoted as nodes. We present an attention-based graph neural network to encode the edges that preserve the financial status as well as network structures. The experimental result shows that DGANN could significantly improve the risk prediction accuracy in both the precision and recall compared with state-of-the-art baselines. We also conduct empirical studies to uncover the risk guarantee patterns from the learned attentional network features. The result provides an alternative way for loan risk management, which may inspire more work in the future.
Protecting Location Privacy in Spatial Crowdsourcing using Encrypted Data
Publisher: No publisher found
Date: 2017
Efficient Computation of Range Aggregates against Uncertain Location-Based Queries
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 07-2012
DOI: 10.1109/TKDE.2011.46
Selecting Stars: The k Most Representative Skyline Operator
Publisher: IEEE
Date: 04-2007
Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN
Publisher: Association for Computing Machinery (ACM)
Date: 08-2009
Abstract: In this paper, we study the problem of continuous monitoring of reverse k nearest neighbor queries. Existing continuous reverse nearest neighbor monitoring techniques are sensitive towards objects and queries movement. For ex le, the results of a query are to be recomputed whenever the query changes its location. We present a framework for continuous reverse k nearest neighbor queries by assigning each object and query with a rectangular safe region such that the expensive recomputation is not required as long as the query and objects remain in their respective safe regions. This significantly improves the computation cost. As a by-product, our framework also reduces the communication cost in client-server architectures because an object does not report its location to the server unless it leaves its safe region or the server sends a location update request. We also conduct a rigid cost analysis to guide an effective selection of such rectangular safe regions. The extensive experiments demonstrate that our techniques outperform the existing techniques by an order of magnitude in terms of computation cost and communication cost.
Distance-aware influence maximization in geo-social network
Publisher: IEEE
Date: 05-2016
Answering billion-scale label-constrained reachability queries within microsecond
Publisher: Association for Computing Machinery (ACM)
Date: 02-2020
Abstract: In this paper, we study the problem of label-constrained reachability (LCR) query which is fundamental in many applications with directed edge-label graphs. Although the classical reachability query (i.e., reachability query without label constraint) has been extensively studied, LCR query is much more challenging because the number of possible label constraint set is exponential to the size of the labels. We observe that the existing techniques for LCR queries only construct partial index for better scalability, and their worst query time is not guaranteed and could be the same as an online breadth-first search (BFS). In this paper, we propose novel label-constrained 2-hop indexing techniques with novel pruning rules and order strategies. It is shown that our worst query time could be bounded by the in-out index entry size. With all these techniques, comprehensive experiments show that our proposed methods significantly outperform the state-of-the-art technique in terms of query response time (up to 5 orders of magnitude speedup), index size and index construction time. In particular, our proposed method can answer LCR queries within microsecond over billion-scale graphs in a single machine.
Eccentricities on small-world networks
Publisher: Springer Science and Business Media LLC
Date: 28-08-2019
Pareto-optimal Community Search on Large Bipartite Graphs
Publisher: ACM
Date: 26-10-2021
Predicting open source programming language repository file survivability from forking data
Publisher: ACM
Date: 20-08-2019
Efficient shortest path counting on large road networks
Publisher: Association for Computing Machinery (ACM)
Date: 06-2022
Abstract: The shortest path distance and related concepts lay the foundations of many real-world applications in road network analysis. The shortest path count has drawn much research attention in academia, not only as a closeness metric accompanying the shorted distance but also serving as a building block of centrality computation. This paper aims to improve the efficiency of counting the shortest paths between two query vertices on a large road network. We propose a novel index solution by organizing all vertices in a tree structure and propose several optimizations to speed up the index construction. We conduct extensive experiments on 14 real-world networks. Compared with the state-of-the-art solution, we achieve much higher efficiency on both query processing and index construction with a more compact index.
Efficient Learning-based Community-Preserving Graph Generation
Publisher: IEEE
Date: 05-2022
Identifying Top k Dominating Objects over Uncertain Data
Publisher: Springer International Publishing
Date: 2014
GoGNN: Graph of Graphs Neural Network for Predicting Structured Entity Interactions
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 07-2020
Abstract: Entity interaction prediction is essential in many important applications such as chemistry, biology, material science, and medical science. The problem becomes quite challenging when each entity is represented by a complex structure, namely structured entity, because two types of graphs are involved: local graphs for structured entities and a global graph to capture the interactions between structured entities. We observe that existing works on structured entity interaction prediction cannot properly exploit the unique graph of graphs model. In this paper, we propose a Graph of Graphs Neural Network, namely GoGNN, which extracts the features in both structured entity graphs and the entity interaction graph in a hierarchical way. We also propose the dual-attention mechanism that enables the model to preserve the neighbor importance in both levels of graphs. Extensive experiments on real-world datasets show that GoGNN outperforms the state-of-the-art methods on two representative structured entity interaction prediction tasks: chemical-chemical interaction prediction and drug-drug interaction prediction. Our code is available at Github.
NOVA: A Novel and Efficient Framework for Finding Subgraph Isomorphism Mappings in Large Graphs
Publisher: Springer Berlin Heidelberg
Date: 2010
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 08-2020
Group-based Fraud Detection Network on e-Commerce Platforms
Publisher: ACM
Date: 04-08-2023
Efficient Maximal Spatial Clique Enumeration
Publisher: IEEE
Date: 04-2019
Discovering Cliques in Signed Networks Based on Balance Theory
Publisher: Springer International Publishing
Date: 2020
Efficient Identification of Local Keyword Patterns in Microblogging Platforms
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 10-2016
I/O Efficient Approximate Nearest Neighbour Search based on Learned Functions
Publisher: IEEE
Date: 04-2020
High-Dimensional Similarity Query Processing for Data Science
Publisher: ACM
Date: 14-08-2021
I/O Efficient Core Graph Decomposition: Application to Degeneracy Ordering
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2019
Binarized graph neural network
Publisher: Springer Science and Business Media LLC
Date: 08-04-2021
DLQ: A System for Label-Constrained Reachability Queries on Dynamic Graphs
Publisher: ACM
Date: 26-10-2021
Knowledge Graph-based Event Embedding Framework for Financial Quantitative Investments
Publisher: ACM
Date: 25-07-2020
Skyline probability over uncertain preferences
Publisher: ACM
Date: 18-03-2013
Maximum and top-k diversified biclique search at scale
Publisher: Springer Science and Business Media LLC
Date: 18-04-2022
DOI: 10.1007/S00778-021-00681-6
Abstract: Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fundamental problem with a wide spectrum of applications in different domains, such as E-Commerce, social analysis, web services, and bioinformatics. Unfortunately, due to the difficulty of the problem in graph theory, no practical solution has been proposed to solve the issue in large-scale real-world datasets. Existing techniques for maximum clique search on a general graph cannot be applied because the search objective of maximum biclique search is two-dimensional, i.e., we have to consider the size of both parts of the biclique simultaneously. In this paper, we ide the problem into several subproblems each of which is specified using two parameters. These subproblems are derived in a progressive manner, and in each subproblem, we can restrict the search in a very small part of the original bipartite graph. We prove that a logarithmic number of subproblems is enough to guarantee the algorithm correctness. To minimize the computational cost, we show how to reduce significantly the bipartite graph size for each subproblem while preserving the maximum biclique satisfying certain constraints by exploring the properties of one-hop and two-hop neighbors for each vertex. Furthermore, we study the ersified top- k biclique search problem which aims to find k maximal bicliques that cover the most edges in total. The basic idea is to repeatedly find the maximum biclique in the bipartite graph and remove it from the bipartite graph k times. We design an efficient algorithm that considers to share the computation cost among the k results, based on the idea of deriving the same subproblems of different results. We further propose two optimizations to accelerate the computation by pruning the search space with size constraint and refining the candidates in a lazy manner. We use several real datasets from various application domains, one of which contains over 300 million vertices and 1.3 billion edges, to demonstrate the high efficiency and scalability of our proposed solution. It is reported that 50% improvement on recall can be achieved after applying our method in Alibaba Group to identify the fraudulent transactions in their e-commerce networks. This further demonstrates the usefulness of our techniques in practice.
SLICE: Reviving regions-based pruning for reverse k nearest neighbors queries
Publisher: IEEE
Date: 03-2014
Discovering Significant Communities on Bipartite Graphs: An Index-based Approach
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2021
A safe zone based approach for monitoring moving skyline queries
Publisher: ACM
Date: 18-03-2013
EI-LSH: An early-termination driven I/O efficient incremental c-approximate nearest neighbor search
Publisher: Springer Science and Business Media LLC
Date: 30-09-2020
Exploring Finer Granularity within the Cores: Efficient (k,p)-Core Computation
Publisher: IEEE
Date: 04-2020
A Synopsis Based Approach for Itemset Frequency Estimation over Massive Multi-Transaction Stream
Publisher: Association for Computing Machinery (ACM)
Date: 21-07-2021
DOI: 10.1145/3465238
Abstract: The streams where multiple transactions are associated with the same key are prevalent in practice, e.g., a customer has multiple shopping records arriving at different time. Itemset frequency estimation on such streams is very challenging since s ling based methods, such as the popularly used reservoir s ling, cannot be used. In this article, we propose a novel k -Minimum Value (KMV) synopsis based method to estimate the frequency of itemsets over multi-transaction streams. First, we extract the KMV synopses for each item from the stream. Then, we propose a novel estimator to estimate the frequency of an itemset over the KMV synopses. Comparing to the existing estimator, our method is not only more accurate and efficient to calculate but also follows the downward-closure property. These properties enable the incorporation of our new estimator with existing frequent itemset mining (FIM) algorithm (e.g., FP-Growth) to mine frequent itemsets over multi-transaction streams. To demonstrate this, we implement a KMV synopsis based FIM algorithm by integrating our estimator into existing FIM algorithms, and we prove it is capable of guaranteeing the accuracy of FIM with a bounded size of KMV synopsis. Experimental results on massive streams show our estimator can significantly improve on the accuracy for both estimating itemset frequency and FIM compared to the existing estimators.
Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks
Publisher: Springer Science and Business Media LLC
Date: 15-05-2012
Efficient Community Search with Size Constraint
Publisher: IEEE
Date: 04-2021
Efficient and Effective Community Search on Large-scale Bipartite Graphs
Publisher: IEEE
Date: 04-2021
Duplicate-Insensitive Order Statistics Computation over Data Streams
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 04-2010
DOI: 10.1109/TKDE.2009.68
Finding Top k Most Influential Spatial Facilities over Uncertain Objects
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 12-2015
Exacting Eccentricity for Small-World Networks
Publisher: IEEE
Date: 04-2018
AP-Tree: Efficiently support continuous spatial-keyword queries over stream
Publisher: IEEE
Date: 04-2015
A Cohesive Structure Based Bipartite Graph Analytics System
Publisher: ACM
Date: 26-10-2021
Efficient probabilistic supergraph search
Publisher: IEEE
Date: 05-2016
Maintaining Boolean Top-K Spatial Temporal Results in Publish-Subscribe Systems
Publisher: Springer International Publishing
Date: 2018
Accelerate MaxBRkNN Search by kNN Estimation
Publisher: IEEE
Date: 04-2019
Leveraging set relations in exact set similarity join
Publisher: Association for Computing Machinery (ACM)
Date: 05-2017
Abstract: Exact set similarity join, which finds all the similar set pairs from two collections of sets, is a fundamental problem with a wide range of applications. The existing solutions for set similarity join follow a filtering-verification framework, which generates a list of candidate pairs through scanning indexes in the filtering phase, and reports those similar pairs in the verification phase. Though much research has been conducted on this problem, set relations, which we find out is quite effective on improving the algorithm efficiency through computational cost sharing, have never been studied. Therefore, in this paper, instead of considering each set in idually, we explore the set relations in different levels to reduce the overall computational costs. First, it has been shown that most of the computational time is spent on the filtering phase, which can be quadratic to the number of sets in the worst case for the existing solutions. Thus we explore index-level set relations to reduce the filtering cost to be linear to the size of the input while keeping the same filtering power. We achieve this by grouping related sets into blocks in the index and skipping useless index probes in joins. Second, we explore answer-level set relations to further improve the algorithm based on the intuition that if two sets are similar, their answers may have a large overlap. We derive an algorithm which incrementally generates the answer of one set from an already computed answer of another similar set rather than compute the answer from scratch to reduce the computational cost. Finally, we conduct extensive performance studies using 21 real datasets with various data properties from a wide range of domains. The experimental results demonstrate that our algorithm outperforms all the existing algorithms across all datasets and can achieve more than an order of magnitude speedup against the state- of-the-art algorithms.
Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates
Publisher: ACM
Date: 27-05-2015
Finding Maximal Stable Cores in Social Networks
Publisher: Springer International Publishing
Date: 2018
Maximum biclique search at billion scale
Publisher: Association for Computing Machinery (ACM)
Date: 05-2020
Abstract: Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fundamental problem with a wide spectrum of applications in different domains, such as E-Commerce, social analysis, web services, and bioinformatics. Unfortunately, due to the difficulty of the problem in graph theory, no practical solution has been proposed to solve the issue in large-scale real-world datasets. Existing techniques for maximum clique search on a general graph cannot be applied because the search objective of maximum biclique search is two-dimensional, i.e., we have to consider the size of both parts of the biclique simultaneously. In this paper, we ide the problem into several subproblems each of which is specified using two parameters. These subproblems are derived in a progressive manner, and in each subproblem we can restrict the search in a very small part of the original bipartite graph. We prove that a logarithmic number of subproblems is enough to guarantee the algorithm correctness. To minimize the computational cost, we show how to reduce significantly the bipartite graph size for each subproblem while preserving the maximum biclique satisfying certain constraints by exploring the properties of one-hop and two-hop neighbors for each vertex. We use several real datasets from various application domains, one of which contains over 300 million vertices and 1.3 billion edges, to demonstrate the high efficiency and scalability of our proposed solution. It is reported that 50% improvement on recall can be achieved after applying our method in Alibaba Group to identify the fraudulent transactions in their e-commerce networks. This further demonstrates the usefulness of our techniques in practice.
Denoising Variational Graph of Graphs Auto-Encoder for Predicting Structured Entity Interactions
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2023
Efficient structural graph clustering: an index-based approach
Publisher: Springer Science and Business Media LLC
Date: 08-05-2019
Real-time constrained cycle detection in large dynamic graphs
Publisher: Association for Computing Machinery (ACM)
Date: 08-2018
Abstract: As graph data is prevalent for an increasing number of Internet applications, continuously monitoring structural patterns in dynamic graphs in order to generate real-time alerts and trigger prompt actions becomes critical for many applications. In this paper, we present a new system GraphS to efficiently detect constrained cycles in a dynamic graph, which is changing constantly, and return the satisfying cycles in real-time. A hot point based index is built and efficiently maintained for each query so as to greatly speed-up query time and achieve high system throughput. The GraphS system is developed at Alibaba to actively monitor various online fraudulent activities based on cycle detection. For a dynamic graph with hundreds of millions of edges and vertices, the system is capable to cope with a peak rate of tens of thousands of edge updates per second and find all the cycles with predefined constraints with a 99.9% latency of 20 milliseconds.
Top-k spatial-keyword publish/subscribe over sliding window
Publisher: Springer Science and Business Media LLC
Date: 11-01-2017
Hierarchical Core Decomposition in Parallel: From Construction to Subgraph Search
Publisher: IEEE
Date: 05-2022
TT-Join: Efficient Set Containment Join
Publisher: IEEE
Date: 04-2017
Efficiently processing snapshot and continuous reverse k nearest neighbors queries
Publisher: Springer Science and Business Media LLC
Date: 10-02-2012
Cost optimization based on influence and user preference
Publisher: Springer Science and Business Media LLC
Date: 2019
Discovering Strong Communities with User Engagement and Tie Strength
Publisher: Springer International Publishing
Date: 2018
Ranking uncertain sky: The probabilistic top-k skyline operator
Publisher: Elsevier BV
Date: 07-2011
AP-Tree: efficiently support location-aware Publish/Subscribe
Publisher: Springer Science and Business Media LLC
Date: 05-10-2015
Reverse k nearest neighbors queries and spatial reverse top-k queries
Publisher: Springer Science and Business Media LLC
Date: 05-11-2017
Efficient label-constrained shortest path queries on road networks
Publisher: Association for Computing Machinery (ACM)
Date: 11-2021
Abstract: Computing the shortest path between two vertices is a fundamental problem in road networks. Most of the existing works assume that the edges in the road networks have no labels, but in many real applications, the edges have labels and label constraints may be placed on the edges appearing on a valid shortest path. Hence, we study the label-constrained shortest path queries in this paper. In order to process such queries efficiently, we adopt an index-based approach and propose a novel index structure, LSD-Index, based on tree decomposition. With LSD-Index, we design an efficient query processing algorithm with good performance guarantees. Moreover, we also propose an algorithm to construct LSD-Index and further improve the efficiency of index construction by exploiting the parallel computing techniques. We conduct extensive performance studies using large real road networks including the whole USA road network. Compared with the state-of-the-art approach, the experimental results demonstrate that our algorithm not only achieves up to 2 orders of magnitude speedup in query processing time but also consumes much less index space. Meanwhile, the indexing time is also competitive, especially that for the parallel index construction algorithm.
Selectivity estimation on set containment search
Publisher: Springer International Publishing
Date: 2019
Efficient Reinforcement of Bipartite Networks at Billion Scale
Publisher: IEEE
Date: 05-2022
DPTL+: Efficient Parallel Triangle Listing on Batch-Dynamic Graphs
Publisher: IEEE
Date: 04-2021
Efficient and High-Quality Seeded Graph Matching: Employing Higher-order Structural Information
Publisher: Association for Computing Machinery (ACM)
Date: 03-05-2021
DOI: 10.1145/3442340
Abstract: Driven by many real applications, we study the problem of seeded graph matching. Given two graphs and , and a small set of pre-matched node pairs where and , the problem is to identify a matching between and growing from , such that each pair in the matching corresponds to the same underlying entity. Recent studies on efficient and effective seeded graph matching have drawn a great deal of attention and many popular methods are largely based on exploring the similarity between local structures to identify matching pairs. While these recent techniques work provably well on random graphs, their accuracy is low over many real networks. In this work, we propose to utilize higher-order neighboring information to improve the matching accuracy and efficiency. As a result, a new framework of seeded graph matching is proposed, which employs Personalized PageRank (PPR) to quantify the matching score of each node pair. To further boost the matching accuracy, we propose a novel postponing strategy, which postpones the selection of pairs that have competitors with similar matching scores. We show that the postpone strategy indeed significantly improves the matching accuracy. To improve the scalability of matching large graphs, we also propose efficient approximation techniques based on algorithms for computing PPR heavy hitters. Our comprehensive experimental studies on large-scale real datasets demonstrate that, compared with state-of-the-art approaches, our framework not only increases the precision and recall both by a significant margin but also achieves speed-up up to more than one order of magnitude.
Editor’s Note
Publisher: Springer Science and Business Media LLC
Date: 24-02-2022
Neural Subgraph Counting with Wasserstein Estimator
Publisher: ACM
Date: 10-06-2022
Efficient set containment join
Publisher: Springer Science and Business Media LLC
Date: 11-05-2018
Efficient Distance-Aware Influence Maximization in Geo-Social Networks
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 03-2017
Efficiently Reinforcing Social Networks over User Engagement and Tie Strength
Publisher: IEEE
Date: 04-2018
Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching
Publisher: IEEE
Date: 05-2022
Discovering fortress-like cohesive subgraphs
Publisher: Springer Science and Business Media LLC
Date: 24-11-2021
Computing K-Cores in Large Uncertain Graphs: An Index-based Optimal Approach
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2020
I-LSH: I/O Efficient c-Approximate Nearest Neighbor Search in High-Dimensional Space
Publisher: IEEE
Date: 04-2019
Gb-KMV: An augmented KMV sketch for approximate containment similarity search
Publisher: IEEE
Date: 04-2019
Efficient Construction of Safe Regions for Moving kNN Queries over Dynamic Datasets
Publisher: Springer Berlin Heidelberg
Date: 2009
T3S: Effective Representation Learning for Trajectory Similarity Computation
Publisher: IEEE
Date: 04-2021
Database Systems for Advanced Applications
Publisher: Springer International Publishing
Date: 2019
Influence based cost optimization on user preference
Publisher: IEEE
Date: 05-2016
Bring Order into the Samples: A Novel Scalable Method for Influence Maximization
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 02-2017
Optimal enumeration
Publisher: Association for Computing Machinery (ACM)
Date: 2015
Abstract: Driven by many real applications, graph pattern matching has attracted a great deal of attention recently. Consider that a twig-pattern matching may result in an extremely large number of matches in a graph this may not only confuse users by providing too many results but also lead to high computational costs. In this paper, we study the problem of top- k tree pattern matching that is, given a rooted tree T , compute its top- k matches in a directed graph G based on the twig-pattern matching semantics. We firstly present a novel and optimal enumeration paradigm based on the principle of Lawler's procedure. We show that our enumeration algorithm runs in O ( n T + log k ) time in each round where n T is the number of nodes in T. Considering that the time complexity to output a match of T is O ( n T ) and n T ≥ log k in practice, our enumeration technique is optimal. Moreover, the cost of generating top-1 match of T in our algorithm is O ( m R ) where m R is the number of edges in the transitive closure of a data graph G involving all relevant nodes to T. O ( m R ) is also optimal in the worst case without pre-knowledge of G. Consequently, our algorithm is optimal with the running time O ( m R + k ( n T + log k )) in contrast to the time complexity O ( m R log k + kn T (log k + d T )) of the existing technique where d T is the maximal node degree in T. Secondly, a novel priority based access technique is proposed, which greatly reduces the number of edges accessed and results in a significant performance improvement. Finally, we apply our techniques to the general form of top- k graph pattern matching problem (i.e., query is a graph) to improve the existing techniques. Comprehensive empirical studies demonstrate that our techniques may improve the existing techniques by orders of magnitude.
AVR-tree: Speeding up the NN and ANN queries on location data
Publisher: Springer Berlin Heidelberg
Date: 2013
Probabilistic n-of-N skyline computation over uncertain data streams
Publisher: Springer Science and Business Media LLC
Date: 10-07-2015
Selecting the Optimal Groups
Publisher: ACM
Date: 03-11-2019
TMN: Trajectory Matching Networks for Predicting Similarity
Publisher: IEEE
Date: 05-2022
Quantile-based KNN over multi-valued objects
Publisher: IEEE
Date: 2010
Reachability Labeling for Distributed Graphs
Publisher: IEEE
Date: 05-2022
Enumerating k-Vertex Connected Components in Large Graphs
Publisher: IEEE
Date: 04-2019
Index-Based Optimal Algorithm for Computing K-Cores in Large Uncertain Graphs
Publisher: IEEE
Date: 04-2019
Efficient Bitruss Decomposition for Large-scale Bipartite Graphs
Publisher: IEEE
Date: 04-2020
Probabilistic k-Skyband Operator over Sliding Windows
Publisher: Springer Berlin Heidelberg
Date: 2013
Finding the Best k in Core Decomposition: A Time and Space Optimal Solution
Publisher: IEEE
Date: 04-2020
Bring order into the samples: A novel scalable method for influence maximization (Extended abstract)
Publisher: IEEE
Date: 04-2017
DOI: 10.1109/ICDE.2017.34
Hurricane in Bipartite Graphs: The Lethal Nodes of Butterflies
Publisher: ACM
Date: 07-07-2020
General spatial skyline operator
Publisher: Springer Berlin Heidelberg
Date: 2012
Top-k Similarity Join over Multi-valued Objects
Publisher: Springer Berlin Heidelberg
Date: 2012
Probabilistic n-of-N skyline computation over uncertain data streams
Publisher: Springer Berlin Heidelberg
Date: 2013
On querying historical k-cores
Publisher: Association for Computing Machinery (ACM)
Date: 07-2021
Abstract: Many real-world relationships between entities can be modeled as temporal graphs, where each edge is associated with a timest or a time interval representing its occurrence. K -core is a fundamental model used to capture cohesive subgraphs in a simple graph and have drawn much research attention over the last decade. Despite widespread research, none of the existing works support the efficient querying of historical k -cores in temporal graphs. In this paper, given an integer k and a time window, we study the problem of computing all k -cores in the graph snapshot over the time window. We propose an index-based solution and several pruning strategies to reduce the index size. We also design a novel algorithm to construct this index, whose running time is linear to the final index size. Lastly, we conducted extensive experiments on several real-world temporal graphs to show the high effectiveness of our index-based solution.
Distributed Streaming Set Similarity Join
Publisher: IEEE
Date: 04-2020
Towards Real-Time Counting Shortest Cycles on Dynamic Graphs: A Hub Labeling Approach
Publisher: IEEE
Date: 05-2022
Scalable distributed subgraph enumeration
Publisher: Association for Computing Machinery (ACM)
Date: 11-2016
Abstract: Subgraph enumeration aims to find all the subgraphs of a large data graph that are isomorphic to a given pattern graph. As the subgraph isomorphism operation is computationally intensive, researchers have recently focused on solving this problem in distributed environments, such as MapReduce and Pregel. Among them, the state-of-the-art algorithm, Twin TwigJoin, is proven to be instance optimal based on a left-deep join framework. However, it is still not scalable to large graphs because of the constraints in the left-deep join framework and that each decomposed component (join unit) must be a star. In this paper, we propose SEED - a scalable sub-graph enumeration approach in the distributed environment. Compared to Twin TwigJoin, SEED returns optimal solution in a generalized join framework without the constraints in Twin TwigJoin. We use both star and clique as the join units, and design an effective distributed graph storage mechanism to support such an extension. We develop a comprehensive cost model, that estimates the number of matches of any given pattern graph by considering power-law degree distribution in the data graph. We then generalize the left-deep join framework and develop a dynamic-programming algorithm to compute an optimal bushy join plan. We also consider overlaps among the join units. Finally, we propose clique compression to further improve the algorithm by reducing the number of the intermediate results. Extensive performance studies are conducted on several real graphs, one containing billions of edges. The results demonstrate that our algorithm outperforms all other state-of-the-art algorithms by more than one order of magnitude.
Towards bridging theory and practice
Publisher: Association for Computing Machinery (ACM)
Date: 09-12-2019
Abstract: Graph is a ubiquitous structure representing entities and their relationships applied in many areas such as social networks, web graphs, and biological networks. One of the fundamental tasks in graph analytics is to investigate the relations between two vertices (e.g., users, items and entities) such as how a vertex A influences another vertex B , or to what extent A and B are similar to each other, based on the graph topology structure. For this purpose, we study the problem of hop-constrained s-t simple path enumeration in this paper, which aims to list all simple paths from a source vertex s to a target vertex t with hop-constraint k. We first propose a polynomial delay algorithm, namely BC-DFS, based on barrier-based pruning technique. Then a join-oriented algorithm, namely JOIN, is designed to further enhance the query response time. On the theoretical side, BC-DFS is a polynomial delay algorithm with O ( km ) time per output where m is the number of edges in the graph. This time complexity is the same as the best known theoretical result for the polynomial delay algorithms of this problem. On the practical side, our comprehensive experiments on 15 real-life networks demonstrate the superior performance of the BC-DFS algorithm compared to the state-of-the-art techniques. It is also reported that the JOIN algorithm can further significantly enhance the query response time.
GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction
Publisher: IEEE
Date: 05-2022
Efficient general spatial skyline computation
Publisher: Springer Science and Business Media LLC
Date: 08-09-2013
Consensus-Based Ranking of Multivalued Objects: A Generalized Borda Count Approach
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2014
Efficient Probabilistic Supergraph Search
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 04-2016
Efficient Matrix Sketching over Distributed Data
Publisher: ACM
Date: 09-05-2017
Leveraging set relations in exact and dynamic set similarity join
Publisher: Springer Science and Business Media LLC
Date: 11-12-2019
Probabilistic skyline operator over sliding windows
Publisher: IEEE
Date: 03-2009
DOI: 10.1109/ICDE.2009.83
When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries on road networks
Publisher: Springer Science and Business Media LLC
Date: 15-03-2023
Efficient rank based KNN query processing over uncertain data
Publisher: IEEE
Date: 2010
Efficient processing of k-regret minimization queries with theoretical guarantees
Publisher: Elsevier BV
Date: 03-2022
Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs
Publisher: Springer Science and Business Media LLC
Date: 20-03-2021
Efficient subhypergraph matching based on hyperedge features
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2022
Aggregate Computation over Data Streams
Publisher: Springer Berlin Heidelberg
Date: 2008
Similarity query processing for high-dimensional data
Publisher: Association for Computing Machinery (ACM)
Date: 08-2020
Abstract: Similarity query processing has been an active research topic for several decades. It is an essential procedure in a wide range of applications. Recently, embedding and auto-encoding methods as well as pre-trained models have gained popularity. They basically deal with high-dimensional data, and this trend brings new opportunities and challenges to similarity query processing for high-dimensional data. Meanwhile, new techniques have emerged to tackle this long-standing problem theoretically and empirically. In this tutorial, we summarize existing solutions, especially recent advancements from both database (DB) and machine learning (ML) communities, and analyze their strengths and weaknesses. We review exact and approximate methods such as cover tree, locality sensitive hashing, product quantization, and proximity graphs. We also discuss the selectivity estimation problem and show how researchers are bringing in state-of-the-art ML techniques to address the problem. By highlighting the strong connections between DB and ML, we hope that this tutorial provides an impetus towards new ML for DB solutions and vice versa.
OLAK
Publisher: Association for Computing Machinery (ACM)
Date: 02-2017
Abstract: In this paper, we study the problem of the anchored k -core. Given a graph G , an integer k and a budget b , we aim to identify b vertices in G so that we can determine the largest induced subgraph J in which every vertex, except the b vertices, has at least k neighbors in J . This problem was introduced by Bhawalkar and Kleinberg e t al. in the context of user engagement in social networks, where a user may leave a community if he/she has less than k friends engaged. The problem has been shown to be NP-hard and inapproximable. A polynomial-time algorithm for graphs with bounded tree-width has been proposed. However, this assumption usually does not hold in real-life graphs, and their techniques cannot be extended to handle general graphs. Motivated by this, we propose an efficient algorithm, namely u o /u nion- u l /u ayer based u a /u nchored u k /u -core (OLAK), for the anchored k -core problem on large scale graphs. To facilitate computation of the anchored k -core, we design an onion layer structure, which is generated by a simple onion-peeling-like algorithm against a small set of vertices in the graph. We show that computation of the best anchor can simply be conducted upon the vertices on the onion layers , which significantly reduces the search space. Based on the well-organized layer structure, we develop efficient candidates exploration, early termination and pruning techniques to further speed up computation. Comprehensive experiments on 10 real-life graphs demonstrate the effectiveness and efficiency of our proposed methods.
Taming verification hardness
Publisher: Association for Computing Machinery (ACM)
Date: 08-2008
Abstract: Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop efficient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of filtering -and- verification to reduce the precise computation costs consequently various novel feature-based indexes have been developed. While the existing techniques work well for small query graphs, the verification phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we firstly propose a novel and efficient algorithm for testing subgraph isomorphism, QuickSI. Secondly, we develop a new feature-based index technique to accommodate QuickSI in the filtering phase. Our extensive experiments on real and synthetic data demonstrate the efficiency and scalability of the proposed techniques, which significantly improve the existing techniques.
I/O Efficient Algorithm for c-Approximate Furthest Neighbor Search in High-Dimensional Space
Publisher: Springer International Publishing
Date: 2020
Cohesive Subgraph Discovery Over Uncertain Bipartite Graphs
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 11-2023
Continuous monitoring of moving skyline and top-k queries
Publisher: Springer Science and Business Media LLC
Date: 11-10-2022
Efficient structural graph clustering
Publisher: Association for Computing Machinery (ACM)
Date: 11-2017
Abstract: Graph clustering is a fundamental problem widely experienced across many industries. The structural graph clustering (SCAN) method obtains not only clusters but also hubs and outliers. However, the clustering results closely depend on two sensitive parameters, ϵ and μ, while the optimal parameter setting depends on different graph properties and various user requirements. Moreover, all existing SCAN solutions need to scan at least the whole graph, even if only a small number of vertices belong to clusters. In this paper we propose an index-based method for SCAN. Based on our index, we cluster the graph for any ϵ and μ in O (Σ c ϵℂ | E C |) time, where ℂ is the result set of all clusters and | E C | is the number of edges in a specific cluster C. In other words, the time expended to compute structural clustering depends only on the result size, not on the size of the original graph. Our index's space complexity is bounded by O ( m ), where m is the number of edges in the graph. To handle dynamic graph updates, we propose algorithms and several optimization techniques for maintaining our index. We conduct extensive experiments to practically evaluate the performance of all our proposed algorithms on 10 real-world networks, one of which contains more than 1 billion edges. The experimental results demonstrate that our approaches significantly outperform existing solutions.
Anchored coreness: efficient reinforcement of social networks
Publisher: Springer Science and Business Media LLC
Date: 31-05-2022
Efficient community discovery with user engagement and similarity
Publisher: Springer Science and Business Media LLC
Date: 26-10-2019
I/O efficient Core Graph Decomposition at web scale
Publisher: IEEE
Date: 05-2016
Scaling Distance Labeling on Small-World Networks
Publisher: ACM
Date: 25-06-2019
Connected substructure similarity search
Publisher: ACM
Date: 06-06-2010
Stochastic skylines
Publisher: Association for Computing Machinery (ACM)
Date: 05-2012
Abstract: In many applications involving multiple criteria optimal decision making, users may often want to make a personal trade-off among all optimal solutions for selecting one object that fits best their personal needs. As a key feature, the skyline in a multidimensional space provides the minimum set of candidates for such purposes by removing all points not preferred by any (monotonic) utility/scoring functions that is, the skyline removes all objects not preferred by any user no matter how their preferences vary. Driven by many recent applications with uncertain data, the probabilistic skyline model is proposed to retrieve uncertain objects based on skyline probabilities. Nevertheless, skyline probabilities cannot capture the preferences of monotonic utility functions. Motivated by this, in this article we propose a novel skyline operator, namely stochastic skylines. In the light of the expected utility principle, stochastic skylines guarantee to provide the minimum set of candidates to optimal solutions over a family of utility functions. We first propose the lskyline operator based on the lower orthant orders . lskyline guarantees to provide the minimum set of candidates to the optimal solutions for the family of monotonic multiplicative utility functions. While lskyline works very effectively for the family of multiplicative functions, it may miss optimal solutions for other utility /scoring functions (e.g., linear functions). To resolve this, we also propose a general stochastic skyline operator, gskyline , based on the usual orders . gskyline provides the minimum candidate set to the optimal solutions for all monotonic functions. For the first time regarding the existing literature, we investigate the complexities of determining a stochastic order between two uncertain objects whose probability distributions are described discretely . We firstly show that determining the lower orthant order is NP-complete with respect to the dimensionality consequently the problem of computing lskyline is NP-complete. We also show an interesting result as follows. While the usual order involves more complicated geometric forms than the lower orthant order, the usual order may be determined in polynomial time regarding all the inputs, including the dimensionality this implies that gskyline can be computed in polynomial time. A general framework is developed for efficiently and effectively retrieving lskyline and gskyline from a set of uncertain objects, respectively, together with efficient and effective filtering techniques. Novel and efficient verification algorithms are developed to efficiently compute lskyline over multidimensional uncertain data, which run in polynomial time if the dimensionality is fixed, and to efficiently compute gskyline in polynomial time regarding all inputs. We also show, by theoretical analysis and experiments, that the sizes of lskyline and gskyline are both quite similar to that of conventional skyline over certain data. Comprehensive experiments demonstrate that our techniques are efficient and scalable regarding both CPU and IO costs.
Hierarchical Decomposition of Big Graphs
Publisher: IEEE
Date: 04-2019
Similarity search on supergraph containment
Publisher: IEEE
Date: 2010
Efficient Computation of Cohesive Subgraphs in Uncertain Bipartite Graphs
Publisher: IEEE
Date: 05-2022
Finding Critical Users in Social Communities: The Collapsed Core and Truss Problems
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2020
Graph Neural Network for Fraud Detection via Spatial-Temporal Attention
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 08-2022
Diversified Spatial Keyword Search On Road Networks
Publisher: No publisher found
Date: 2014
A survey of community search over big graphs
Publisher: Springer Science and Business Media LLC
Date: 20-07-2019
Spatial Keyword Range Search on Trajectories
Publisher: Springer International Publishing
Date: 2015
Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations
Publisher: Association for Computing Machinery (ACM)
Date: 10-2014
Abstract: In this paper, we investigate the selectivity estimation problem for streaming spatio-textual data, which arises in many social network and geo-location applications. Specifically, given a set of continuously and rapidly arriving spatio-textual objects, each of which is described by a geo-location and a short text, we aim to accurately estimate the cardinality of a spatial keyword query on objects seen so far, where a spatial keyword query consists of a search region and a set of query keywords. To the best of our knowledge, this is the first work to address this important problem. We first extend two existing techniques to solve this problem, and show their limitations. Inspired by two key observations on the "locality" of the correlations among query keywords, we propose a local correlation based method by utilizing an augmented adaptive space partition tree ( A 2 SP -tree for short) to approximately learn a local Bayesian network on-the-fly for a given query and estimate its selectivity. A novel local boosting approach is presented to further enhance the learning accuracy of local Bayesian networks. Our comprehensive experiments on real-life datasets demonstrate the superior performance of the local correlation based algorithm in terms of estimation accuracy compared to other competitors.
ScaleG: A Distributed Disk-based System for Vertex-centric Graph Processing
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2021
Selectivity Estimation on Set Containment Search
Publisher: Springer Science and Business Media LLC
Date: 09-2019
DOI: 10.1007/S41019-019-00104-1
Abstract: In this paper, we study the problem of selectivity estimation on set containment search. Given a query record Q and a record dataset $${\\mathcal {S}}$$ S , we aim to accurately and efficiently estimate the selectivity of set containment search of query Q over $${\\mathcal {S}}$$ S . We first extend existing distinct value estimating techniques to solve this problem and develop an inverted list and G-KMV sketch-based approach IL-GKMV . We analyze that the performance of IL-GKMV degrades with the increase in vocabulary size. Motivated by limitations of existing techniques and the inherent challenges of the problem, we resort to developing effective and efficient s ling approaches and propose an ordered trie structure-based s ling approach named OT-S ling . OT-S ling partitions records based on element frequency and occurrence patterns and is significantly more accurate compared with simple random s ling method and IL-GKMV . To further enhance the performance, a ide-and-conquer-based s ling approach, DC-S ling , is presented with an inclusion/exclusion prefix to explore the pruning opportunities. Meanwhile, we consider weighted set containment selectivity estimation and devise stratified random s ling approach named StrRS . We theoretically analyze the proposed techniques regarding various accuracy estimators. Our comprehensive experiments on nine real datasets verify the effectiveness and efficiency of our proposed techniques.
A novel multi-segment feature fusion based fault classification approach for rotating machinery
Publisher: Elsevier BV
Date: 05-2019
Stable Community Detection in Signed Social Networks
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 10-2021
Scaling Up k-Clique Densest Subgraph Detection
Publisher: Association for Computing Machinery (ACM)
Date: 26-05-2023
DOI: 10.1145/3588923
Abstract: In this paper, we study the k-clique densest subgraph problem, which detects the subgraph that maximizes the ratio between the number of k-cliques and the number of vertices in it. The problem has been extensively studied in the literature and has many applications in a wide range of fields such as biology and finance. Existing solutions rely heavily on repeatedly computing all the k-cliques, which are not scalable to handle large k values on large-scale graphs. In this paper, by adapting the idea of "pivoting", we propose the SCT*-Index to compactly organize the k-cliques. Based on the SCT*-Index, our SCTL algorithm can directly obtain the k-cliques from the index and efficiently achieve near-optimal approximation. To further improve SCTL, we propose SCTL* that includes novel graph reductions and batch-processing optimizations to reduce the search space and decrease the number of visited k-cliques, respectively. As evaluated in our experiments, SCTL* significantly outperform existing approaches by up to two orders of magnitude. In addition, we propose a s ling-based approximate algorithm that can provide reasonable approximations for any k value on billion-scale graphs. Extensive experiments on 12 real-world graphs validate both the efficiency and effectiveness of the proposed techniques.
Inverted linear quadtree: Efficient top k spatial keyword search
Publisher: IEEE
Date: 04-2013
SimFusion+: extending simfusion towards efficient estimation on large and dynamic networks
Publisher: ACM
Date: 12-08-2012
General graph generators: experiments, analyses, and improvements
Publisher: Springer Science and Business Media LLC
Date: 07-10-2021
Exploring cohesive subgraphs with vertex engagement and tie strength in bipartite graphs
Publisher: Elsevier BV
Date: 09-2021
Efficient Hop-constrained s-t Simple Path Enumeration
Publisher: Springer Science and Business Media LLC
Date: 08-05-2021
Efficient Probabilistic K-Core Computation on Uncertain Graphs
Publisher: IEEE
Date: 04-2018
Online Product Quantization
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2018
Stochastic skyline operator
Publisher: IEEE
Date: 04-2011
BMC: An efficient method to evaluate probabilistic reachability queries
Publisher: Springer Berlin Heidelberg
Date: 2011
Space-efficient Relative Error Order Sketch over Data Streams
Publisher: IEEE
Date: 2006
Effectively Indexing the Multidimensional Uncertain Objects
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 03-2014
DOI: 10.1109/TKDE.2013.21
Threshold-based probabilistic top-k dominating queries
Publisher: Springer Science and Business Media LLC
Date: 04-09-2010
Anti-Money Laundering by Group-Aware Deep Graph Learning
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2023
Finding top k most influential spatial facilities over uncertain objects
Publisher: ACM
Date: 29-10-2012
Applying a Systematic Literature Review and Content Analysis Method to Analyse Open Source Developers’ Forking Motivation Interpretation, Categories and Consequences
Publisher: Australian Journal of Information Systems
Date: 16-06-2020
Abstract: In open source (OS) environments, forking is a powerful social collaborative technique that creates a social coding community and increases code visibility but it has not been adopted by OS software (OSS) developers. This paper investigates OS forking ergence using contextual frameworks (systematic literature review and content analysis) to analyse OSS developer forking motivation, interpretation, categorisation and consequences. We identified five theoretical forking patterns: 1) forking can revive original project health 2) few effective frameworks exist to describe project-to-project developer migration 3) there is a literature on social forking community behaviour 4) poor guidance is a threat to forking and 5) most research uses mixed methods. We introduce guidelines for OSS communities to reduce organisational barriers to developer motivation and highlight the important of understanding developer forking. The challenge remains to analyse forking and sustainability from a social community perspective, particularly how programming language, file repositories and developer interest can predict forking motivation and behaviour for both novice OSS developers or experienced developers who want to improve forking performance.
Uncertain Location Based Range Aggregates in a Multi-dimensional Space
Publisher: IEEE
Date: 03-2009
Fully dynamic depth-first search in directed graphs
Publisher: Association for Computing Machinery (ACM)
Date: 10-2019
Abstract: Depth-first search (DFS) is a fundamental and important algorithm in graph analysis. It is the basis of many graph algorithms such as computing strongly connected components, testing planarity, and detecting biconnected components. The result of a DFS is normally shown as a DFS-Tree. Given the frequent updates in many real-world graphs (e.g., social networks and communication networks), we study the problem of DFS-Tree maintenance in dynamic directed graphs. In the literature, most works focus on the DFS-Tree maintenance problem in undirected graphs and directed acyclic graphs. However, their methods cannot easily be applied in the case of general directed graphs. Motivated by this, we propose a framework and corresponding algorithms for both edge insertion and deletion in general directed graphs. We further give several optimizations to speed up the algorithms. We conduct extensive experiments on 12 real-world datasets to show the efficiency of our proposed algorithms.
Related Organisations
Related Funding Activities
Discovery Early Career Researcher Award - Grant ID: DE140100679
Start Date: 2014
End Date: 12-2016
Amount: $395,220.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP230101445
Start Date: 2023
End Date: 12-2025
Amount: $495,000.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP130103245
Start Date: 2013
End Date: 12-2016
Amount: $335,000.00
Funder: Australian Research Council
View Funded ActivityARC Future Fellowships - Grant ID: FT170100128
Start Date: 12-2017
End Date: 12-2021
Amount: $816,000.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP210101393
Start Date: 2021
End Date: 12-2023
Amount: $510,000.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP180103096
Start Date: 2018
End Date: 12-2020
Amount: $407,947.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP110104880
Start Date: 2011
End Date: 05-2014
Amount: $260,692.00
Funder: Australian Research Council
View Funded ActivityLinkage Projects - Grant ID: LP210301046
Start Date: 10-2023
End Date: 10-2026
Amount: $313,212.00
Funder: Australian Research Council
View Funded Activity