检索结果-内蒙古大学图书馆

Pathquery Pregel: high-performance graph query with bulk synchronous processing

PATTERN ANALYSIS AND APPLICATIONS 2020年第3期23卷 1493-1504页

作者： Arsintescu, Bogdan Deo, Shardul Harris, Warren Google Inc 1600 Amphiteatre Pkwy Mountain View CA 94043 USA

High-performance graph query systems are a scalable way to mine information in Knowledge graphs, especially when the queries benefit from a high-level expressive query language. This paper presents techniques to algorithmically compile queries expressed in a high-level language (e.g., Datalog) into a directed acyclic graph query plan and details how these queries can be run on a Pregel graph vertex-centric compute system. Our solution, called Pathquery Pregel, creates plans for any conjunctive or disjunctive queries with aggregation and negation;we describe how the query execution extracts graph results optimally while avoiding many join operations where parallel map execution is permitted. We provide details of how we scaled this system out to execute large set of queries in parallel over the Google Knowledge graph, a graph of 70B edges, or facts;we describe our production experience with Pathquery Pregel.

关键词： Distributed graph compute Pregel graph query Bulk synchronous parallel computing graph database

来源：评论

学校读者我要写书评

暂无评论

An Efficient graph query Framework with Structural Recursion

引用

COMPUTER JOURNAL 2018年第1期61卷 144-157页

作者： Meng, Xiaodong Guo, Minyi Zhang, Jingyu Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai Peoples R China

The potential to promote market value by analysing graph-structured data is increasingly attracting businesses from a variety of industries, ranging from Internet companies to traditional enterprises. However, the query over large graphs easily and efficiently is still a critical problem in large scale distributed systems. Many proposed systems have to use low-level programming model, like Pregel, which requires a large amount of code optimization and maintenance work by developers. Although structural recursion has been studied as an efficient high-level programming model for graph transformations, it is not well exploited in practice to accelerate the parallel graph computing. To address the above problem, in this paper, we propose optimizations of structure recursion for distributed graphs to reduce the number of iterations during graph query processing in a distributed system. In order to improve query response time and throughput, subgraph based computation on structure recursive functions are used to replace typical vertex based evaluation approach. Meanwhile, we propose several redundancy rules to reduce graph size in parallel. We verify the performance of our system through evaluation on real datasets. The results show that, compared to the state-of-the-art approach (Tung and Hu (2015) Towards systematic parallelization of graph transformations over pregel, pp. 1-20. Springer), our algorithm achieves speedup over two times on query response time.

关键词： graph query structure recursion distributed graphs bulk semantics

来源：评论

学校读者我要写书评

暂无评论

Answering the Why-Not Questions of graph query Autocompletion 23rd

引用

23rd International Conference on Database Systems for Advanced Applications (DASFAA).

作者： Li, Guozhong Ng, Nathan Yi, Peipei Zhang, Zhiwei Choi, Byron Hong Kong Baptist Univ Dept Comp Sci Kowloon Tong Hong Kong Peoples R China

ISBN: (纸本)9783319914527;9783319914510

graph query autocompletion (gQAC) helps users formulate graph queries in a visual environment (a.k.a GUI). It takes a graph query that the user is formulating as input and generates a ranked list of query suggestions. Since it is impossible to accurately predict the user's target query, the current state-of-the-art of gQAC sometimes fails to produce useful suggestions. In such scenarios, it is natural for the user to ask why are useful suggestions not returned. In this paper, we address the why-not questions of gQAC. Specifically, given an intermediate query q, a target query qt, and a gQAC system X, the why-not questions of gQAC seek for the minimal refinement of the configuration of X, with respect to a penalty model, such that at least one useful suggestion towards qt appears in the returned suggestions. We propose a generic ranking function for existing gQAC systems. We propose a search algorithm for the why-not questions.

关键词： graph query query autocompletion Why-not questions

来源：评论

学校读者我要写书评

暂无评论

Q-graph: Preserving query Locality in Multi-query graph Processing 1

Q-Graph: Preserving Query Locality in Multi-Query Graph Proc...

引用

1st ACM SIGMOD Joint International Workshop on graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA)

作者： Mayer, Christian Mayer, Ruben Grunert, Jonas Rothermel, Kurt Tariq, Muhammad Adnan Univ Stuttgart Inst Parallel & Distributed Syst Stuttgart Germany

ISBN: (纸本)9781450356954

Arising user-centric graph applications such as route planning and personalized social network analysis have initiated a shift of paradigms in modern graph processing systems towards multi-query analysis, i.e., processing multiple graph queries in parallel on a shared graph. These applications generate a dynamic number of localized queries around query hotspots such as popular urban areas. However, existing graph processing systems are not yet tailored towards these properties: The employed methods for graph partitioning and synchronization management disregard query locality and dynamism which leads to high query latency. To this end, we propose the system Q-graph for multi-query graph analysis that considers query locality on three levels. (i) The query-aware graph partitioning algorithm Q-cut maximizes query locality to reduce communication overhead. (ii) The method for synchronization management, called hybrid barrier synchronization, allows for full exploitation of local queries spanning only a subset of partitions. (iii) Both methods adapt at runtime to changing query workloads in order to maintain and exploit locality. Our experiments show that Q-cut reduces average query latency by up to 57 percent compared to static query-agnostic partitioning algorithms.

关键词： Distributed graph Processing graph query query-cut graph Partitioning Hybrid Barrier Synchronisation

来源：评论

学校读者我要写书评

暂无评论

QLiG: query Like a graph For Subgraph Matching 4

QLiG: Query Like a Graph For Subgraph Matching

引用

4th IEEE International Conference on Artificial Intelligence and Knowledge Engineering (AIKE)

作者： Purohit, Sumit Mackey, Patrick Zucker, Jeremy D. Bohra, Ankur Deshmukh, Rahul D. Chin, George Pacific Northwest Natl Lab Richland WA 99352 USA

ISBN: (纸本)9781665437363

A graph is a natural and flexible modeling approach to represent entities and relationships between them in the real world. A Knowledge graph (KG) is a specialized graph with formal and structured representations of facts, relationships, annotated with semantic descriptions. Subgraph matching is one of the fundamental graph problems to identify relationships, interactions, and activities of interest within a large graph. A query specification is a collection of abstract components, operations, and constraints to express a pattern. The specification can be implemented in different ways based on the underlying data model. Various graph query specifications have been developed over the years that has led to the development of different open-sourced and vendor-specific query languages. Such specifications are modeled as an extension of relational algebra used in relational query languages such as SQL. Such approaches do not inherently support graph queries. There is a need to represent graph queries in terms of graph-based components to expedite the query construction by non-database experts. We present a graph-based query approach QLiG (pronounced cleeg), to perform subgraph matching in a Labeled Property graph (LPG). QLiG provides required expressivity to represent a query graph in a natural way using high-level concepts such as path, structure, and constraints. We present the query specification, salient features, and a real-world use case to show functional examples.

关键词： property graph graph query query specification subgraph matching

来源：评论

学校读者我要写书评

暂无评论

Accelerating maximum biplex search over large bipartite graphs

引用

VLDB JOURNAL 2025年第1期34卷 1-24页

作者： Pan, Dong Zhou, Xu Luo, Wensheng Yang, Zhibang Liu, Qing Gao, Yunjun Li, Kenli Hunan Univ Coll Comp Sci & Elect Engn Changsha Peoples R China Zhejiang Univ Coll Comp Sci & Technol Zhejiang Peoples R China

As a typical most-to-most connected quasi-biclique model, k-biplex allows nodes on each side of a fully connected subgraph to lose at most k connections. In this paper, we investigate the maximum k-biplex search problem to find a k-biplex with the maximum number of edges and prove that it is NP-hard and inapproximable. To solve this problem, we first define a new dense subgraph over a given bipartite graph, named (x, y)-core, based on which a core-based maximum k-biplex search (CMBS) framework is presented by introducing a core-based graph reduction technique. In addition, we design a bidirectional positioning strategy and propose a CMBS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {CMBS}<^>+$$\end{document} framework. After that, two exact algorithms, namely a maximum k-biplex search (MBPS) algorithm and a core-based symmetric search (CSS) algorithm, are developed to compute the maximum k-biplex in (x, y)-cores. In particular, MBPS integrates degree-based and 2-hop pruning strategies, and CSS explores symmetric BK branching and early termination strategies. To process large bipartite graphs more effectively, we further develop a heuristic fast search (HFS) algorithm and a FPGA-based parallel HFS (FP-HFS) algorithm, where a two-level parallel architecture at and inside the processing element (PE) is introduced to improve the pipeline. Moreover, a double buffering technique is utilized to overcome the resource limitation of FP-HFS and improve scalability. Extensive experiments conducted on 12 real datasets, as well as two synthetic datasets, demonstrate the efficiency and effectiveness of the proposed algorithms.

关键词： Bipartite graph graph query k-biplex FPGA Subgraph search

来源：评论

学校读者我要写书评

暂无评论

Scalable top-k query on information networks with hierarchical inheritance relations

引用

DISTRIBUTED AND PARALLEL DATABASES 2024年第1期42卷 1-30页

作者： Wu, Fubao Gao, Lixin Univ Massachusetts Amherst Dept Elect & Comp Engn Amherst MA 01003 USA

graph query, pattern mining and knowledge discovery become challenging on large-scale heterogeneous information networks (HINs). State-of-the-art techniques involving path propagation mainly focus on the inference of node labels, and neighborhood structures. However, entity links in the real world also contain rich hierarchical inheritance relations. For example, the vulnerability of a product version is likely to be inherited from its older versions. Taking advantage of the hierarchical inheritances can potentially improve the quality of query results. Motivated by this, we explore hierarchical inheritance relations between entities and formulate the problem of graph query on HINs with hierarchical inheritance relations. We propose a graph query search algorithm by decomposing the original query graph into multiple star queries and applying a star query algorithm to each star query. Candidates from each star query result are then constructed for the final top-k query answer to the original query. To efficiently obtain the graph query result from a large-scale HIN, we design a bound-based pruning technique by using the uniform cost search to prune the search spaces. We implement our algorithm in Spark graphX to test the effectiveness and efficiency on synthetic and real-world datasets. Compared with two state-of-the-art graph query algorithms, our algorithm can effectively obtain more accurate results and competitive performance.

关键词： Heterogeneous information network graph query Hierarchical inheritance relations

来源：评论

学校读者我要写书评

暂无评论

Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2024年第5期36卷 2151-2165页

作者： Cai, Taotao Lei, Qi Sheng, Quan Z. Cui, Ningning Yang, Shuiqiao Yang, Jian Zhang, Wei Emma Mahmood, Adnan Univ Southern Queensland Toowoomba 487535 Australia Macquarie Univ Sydney NSW 2000 Australia Changan Univ Xian 710064 Peoples R China Anhui Univ Hefei 230093 Anhui Peoples R China CSIRO DATA61 Eveleigh NSW 2015 Australia Univ Adelaide Adelaide 5005 Australia

Influence Maximization (IM), which aims to select a set of users from a social network to maximize the expected number of influenced users, has recently received significant attention for mass communication and commercial marketing. Existing research efforts dedicated to the IM problem depend on a strong assumption: the selected seed users are willing to spread the information after receiving benefits from a company or organization. In reality, however, some seed users may be reluctant to spread the information or need to be paid higher to be motivated. Furthermore, the existing IM works pay little attention to capture users' influence propagation in the future period. In this paper, we target a new research problem named, Reconnecting Top-ll Relationships (RT ll R) query, which aims to find ll number of previous existing relationships but being estranged later such that reconnecting these relationships will maximize the expected number of influenced users by the given group in a future period. We prove that the RT ll R problem is NP-hard. An efficient greedy algorithm is proposed to answer the RT ll R queries with the influence estimation technique and the well-chosen link prediction method to predict the near future network structure. We also design a pruning method to reduce unnecessary probing from candidate edges. Further, a carefully designed order-based algorithm is proposed to accelerate the RT ll R queries. Finally, we conduct extensive experiments on real-world datasets to demonstrate the effectiveness and efficiency of our proposed methods.

关键词： Evolving networks graph query influence maximization link prediction

来源：评论

学校读者我要写书评

暂无评论

Locality-Preserving graph Traversal With Split Live Migration

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2024年第10期35卷 1810-1825页

作者： Chen, Rong Wei, Xingda Xiating, Xie Chen, Haibo Shanghai Jiao Tong Univ Inst Parallel & Distributed Syst Shanghai 200240 Peoples R China Engn Res Ctr Domain Specif Operating Syst MOE Shanghai 200240 Peoples R China Chinese Acad Sci Key Lab Syst Software Beijing 100045 Peoples R China

graph models many real-world data like social, transportation, biology, and communication data. Hence, graph traversal including multi-hop or graph-walking queries has been the key operation atop graph stores. However, since different graph traversals may touch different sets of vertices, it is hard or even impossible to have a one-size-fits-all graph partitioning algorithm that preserves access locality for various graph traversal workloads. Meanwhile, prior shard-based migration faces a dilemma such that coarse-grained migration may incur more migration overhead over increased locality benefits, while fine-grained migration usually requires excessive metadata and incurs non-trivial maintenance costs. We present Pragh, an efficient locality-preserving live graph migration scheme for graph stores in the form of key-value pairs. The key idea of Pragh is a split migration model that only migrates values physically while retaining keys in the initial location. This allows fine-grained migration while avoiding the need to maintain excessive metadata. Pragh integrates an RDMA-friendly location cache from DrTM-KV to provide fully-localized access to migrated data and further makes a novel reuse of the cache replacement policy for lightweight monitoring. Pragh further supports evolving graphs through a check-and-forward mechanism to resolve the conflict between updates and migration of graph data. Evaluations on an 8-node RDMA-capable cluster (100 Gbps) using a representative graph traversal benchmark show that Pragh can increase the throughput by up to 19x and decrease the median latency by up to 94%, thanks to split live migration that eliminates 97% remote accesses. A port of split live migration to Wukong shows up to 2.53x throughput improvement on representative workloads like LUBM-10240, thanks to a reduction of 88% remote accesses. This further confirms the effectiveness and generality of Pragh. Finally, though Pragh focuses on RDMA-based graph traversal, we show it

关键词： Throughput Distributed databases Metadata Monitoring Social networking (online) Protocols Production graph query graph traversal live migration locality preserving RDMA split migration

来源：评论

学校读者我要写书评

暂无评论

Stable Subgraph Isomorphism Search in Temporal Networks

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第6期35卷 6405-6420页

作者： Zhang, Qi Li, Rong-Hua Qin, Hongchao Wang, Guoren Zhang, Zhiwei Yuan, Ye Beijing Inst Technol Sch Comp Sci & Technol Beijing 100081 Peoples R China

In this paper, we study a new problem of seeking stable subgraph isomorphisms for a query graph in a temporal graph. To solve our problem, we first develop a pruning-based search algorithm using several new pruning tricks to prune the unpromising matching results during the search procedure. To further improve the efficiency, we propose a novel index structure called BCCIndex, based on an idea of bi-connected component decomposition of the query graph, which can efficiently support the stable subgraph isomorphism search. Equipped with the BCCIndex, we present an efficient query processing algorithm based on a carefully designed tree join technique. We conduct extensive experiments to evaluate our algorithms on four large real-life datasets, and the results demonstrate the efficiency and effectiveness of our algorithms.

关键词： query processing Search problems Indexes graph query temporal graphs subgraph isomorphism search

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：