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

Fast graph query processing with a low-cost index

VLDB JOURNAL 2011年第4期20卷 521-539页

作者： Cheng, James Ke, Yiping Fu, Ada Wai-Chee Yu, Jeffrey Xu Chinese Univ Hong Kong Dept Syst Engn & Engn Management Sha Tin Hong Kong Peoples R China Nanyang Technol Univ Sch Comp Engn Singapore Singapore Chinese Univ Hong Kong Dept Comp Sci & Engn Sha Tin Hong Kong Peoples R China

This paper studies the problem of processing supergraph queries, that is, given a database containing a set of graphs, find all the graphs in the database of which the query graph is a supergraph. Existing works usually construct an index and performs a filtering-and-verification process, which still requires many subgraph isomorphism testings. There are also significant overheads in both index construction and maintenance. In this paper, we design a graph querying system that achieves both fast indexing and efficient query processing. The index is constructed by a simple but fast method of extracting the commonality among the graphs, which does not involve any costly operation such as graph mining. Our query processing has two key techniques, direct inclusion and filtering. Direct inclusion allows partial query answers to be included directly without candidate verification. Our filtering technique further reduces the candidate set by operating on a much smaller projected database. Experimental results show that our method is significantly more efficient than the existing works in both indexing and query processing, and our index has a low maintenance cost.

关键词： graph query processing graph indexing Supergraph queries

来源：评论

学校读者我要写书评

暂无评论

Efficient query processing on graph Databases

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2009年第1期34卷 2-2:48页

作者： Cheng, James Ke, Yiping Ng, Wilfred Nanyang Technol Univ Sch Comp Engn Singapore Singapore Chinese Univ Hong Kong Dept Syst Engn & Management Hong Kong Hong Kong Peoples R China Hong Kong Univ Sci & Technol Clear Water Bay Hong Kong Peoples R China

We study the problem of processing subgraph queries on a database that consists of a set of graphs. The answer to a subgraph query is the set of graphs in the database that are supergraphs of the query. In this article, we propose an efficient index, FG*-index, to solve this problem. The cost of processing a subgraph query using most existing indexes mainly consists of two parts: the index probing cost and the candidate verification cost. Index probing is to find the query in the index, or to find the graphs from which we can generate a candidate answer set for the query. Candidate verification is to test whether each graph in the candidate set is indeed a supergraph of the query. We design FG*-index to minimize these two costs as follows. FG*-index consists of three components: the FG-index, the feature-index, and the FAQ-index. First, the FG-index employs the concept of Frequent subgraph (FG) to allow the set of queries that are FGs to be answered without candidate verification. We call this set of queries FG-queries. We can enlarge the set of FG-queries so that more queries can be answered without candidate verification;however, a larger set of FG-queries implies a larger FG-index and hence the index probing cost also increases. We propose the feature-index to reduce the index probing cost. The feature-index uses features to filter false results that are matched in the FG-index, so that we can quickly find the truly matching graphs for a query. For processing non-FG-queries, we propose the FAQ-index, which is dynamically constructed from the set of Frequently Asked non-FG-Queries (FAQs). Using the FAQ-index, verification is not required for processing FAQs and only a small number of candidates need to be verified for processing non-FG-queries that are not frequently asked. Finally, a comprehensive set of experiments verifies that query processing using FG*-index is up to orders of magnitude more efficient than state-of-the-art indexes and it is also more scalable

关键词： Algorithms Experimentation Performance graph databases graph indexing graph query processing frequent subgraphs

来源：评论

学校读者我要写书评

暂无评论

Worst-Case-Optimal Joins on graphs with Topological Relations 34

Worst-Case-Optimal Joins on Graphs with Topological Relation...

引用

34th ACM Web Conference, WWW 2025

作者： Fuentes-Sepúlveda, José Gómez-Brandón, Adrián Hogan, Aidan Irribarra-Cortés, Ayleen Navarro, Gonzalo Reutter, Juan Universidad de Concepción Concepción Chile Universidade da Coruña A Coruña Spain University of Chile Department of Computer Science Santiago Chile Pontificia Universidad Católica de Chile Santiago Chile Millennium Institute for Foundational Research on Data Chile Centro de Investigación TIC Spain

ISBN: (纸本)9798400712746

Spatial data play an important role in many applications built over knowledge graphs, and are frequently referenced in queries posed to public query services, such as that of Wikidata. querying for spatial data presents a significant challenge, as topological relations such as adjacent or contains imply inferred information, such as through the transitivity of the containment relation. However, despite all the recent advances in querying knowledge graphs, we still lack techniques specifically tailored for topological information. Applications looking to incorporate topological relations must either materialize the inferred relations, incurring high space and maintenance overheads, or query them with less efficient recursive algorithms, incurring high runtime overheads. In this paper we address the problem of leveraging topological information in knowledge graphs by designing efficient algorithms to process these queries. Our solution involves building a specific index that stores the topological information in a convenient compact form, and includes specialized algorithms that infer every possible relation from the basic topological facts in the graph. We show that, while using essentially the same space required to solve standard graph pattern queries, we can incorporate topological predicates, accounting for all the inferred information, all within worst-case-optimal time. We implement our scheme and show experimentally that it outperforms baseline solutions by a notable margin. © 2025 Copyright held by the owner/author(s).

关键词： Geospatial graphs graph query processing topological graphs worst-case optimal joins

来源：评论

学校读者我要写书评

暂无评论

A method for improving graph queries processing using positional inverted index (P.I.I) idea in search engines and parallelization techniques

引用

Journal of Central South University 2016年第1期23卷 150-159页

作者： Hamed Dinari Hassan Naderi Web and Search Engines Laboratory School of Computer EngineeringIran University of Science and Technology

The idea of positional inverted index is exploited for indexing of graph database. The main idea is the use of hashing tables in order to prune a considerable portion of graph database that cannot contain the answer set. These tables are implemented using column-based techniques and are used to store graphs of database, frequent sub-graphs and the neighborhood of nodes. In order to exact checking of remaining graphs, the vertex invariant is used for isomorphism test which can be parallel implemented. The results of evaluation indicate that proposed method outperforms existing methods.

关键词： graph query processing frequent subgraph graph mining data mining positional inverted index

来源：评论

学校读者我要写书评

暂无评论

querying Knowledge graphs by Example Entity Tuples

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2015年第10期27卷 2797-2811页

作者： Jayaram, Nandish Khan, Arijit Li, Chengkai Yan, Xifeng Elmasri, Ramez Univ Texas Arlington Dept Comp Sci & Engn Arlington TX 76010 USA Swiss Fed Inst Technol Syst Grp Zurich Switzerland Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

We witness an unprecedented proliferation of knowledge graphs that record millions of entities and their relationships. While knowledge graphs are structure-flexible and content-rich, they are difficult to use. The challenge lies in the gap between their overwhelming complexity and the limited database knowledge of non-professional users. If writing structured queries over "simple" tables is difficult, complex graphs are only harder to query. As an initial step toward improving the usability of knowledge graphs, we propose to query such data by example entity tuples, without requiring users to form complex graph queries. Our system, graph query By Example (GQBE), automatically discovers a weighted hidden maximum query graph based on input query tuples, to capture a user's query intent. It then efficiently finds and ranks the top approximate matching answer graphs and answer tuples. We conducted experiments and user studies on the large Freebase and DBpedia datasets and observed appealing accuracy and efficiency. Our system provides a complementary approach to the existing keyword-based methods, facilitating user-friendly graph querying. To the best of our knowledge, there was no such proposal in the past in the context of graphs.

关键词： Knowledge graphs entity graphs query by example graph query processing

来源：评论

学校读者我要写书评

暂无评论

GRAIL: a scalable index for reachability queries in very large graphs

引用

VLDB JOURNAL 2012年第4期21卷 509-534页

作者： Yildirim, Hilmi Chaoji, Vineet Zaki, Mohammed J. Rensselaer Polytech Inst Troy NY 12180 USA Yahoo Labs Bangalore Karnataka India

Given a large directed graph, rapidly answering reachability queries between source and target nodes is an important problem. Existing methods for reachability tradeoff indexing time and space versus query time performance. However, the biggest limitation of existing methods is that they do not scale to very large real-world graphs. We present a simple yet scalable reachability index, called GRAIL, that is based on the idea of randomized interval labeling and that can effectively handle very large graphs. Based on an extensive set of experiments, we show that while more sophisticated methods work better on small graphs, GRAIL is the only index that can scale to millions of nodes and edges. GRAIL has linear indexing time and space, and the query time ranges from constant time to being linear in the graph order and size. Our reference C++ implementations are open source and available for download at http://***/p/grail/.

关键词： graph query processing Scalable graph indexing Reachability queries

来源：评论

学校读者我要写书评

暂无评论

Efficient access methods for very large distributed graph databases

引用

INFORMATION SCIENCES 2021年 573卷 65-81页

作者： Luaces, David Viqueira, Jose R. R. Cotos, Jose M. Flores, Julian C. Univ Santiago Compostela USC Comp Graph & Data Engn Grp COGRADE Ctr Singular Invest Tecnoloxias Intelixentes CiTI Santiago Spain

Subgraph searching is an essential problem in graph databases, but it is also challenging due to the involved subgraph isomorphism NP-Complete sub-problem. Filter-Then-Verify (FTV) methods mitigate performance overheads by using an index to prune out graphs that do not fit the query in a filtering stage, reducing the number of subgraph isomorphism evaluations in a subsequent verification stage. Subgraph searching has to be applied to very large databases (tens of millions of graphs) in real applications such as molecular substructure searching. Previous surveys have identified the FTV solutions graphGrepSX (GGSX) and CT-Index as the best ones for large databases (thousands of graphs), however they cannot reach reasonable performance on very large ones (tens of millions graphs). This paper proposes a generic approach for the distributed implementation of FTV solutions. Besides, three previous methods that improve the performance of GGSX and CT-Index are adapted to be executed in clusters. The evaluation shows how the achieved solutions provide a great performance improvement (between 70% and 90% of filtering time reduction) in a centralized configuration and how they may be used to achieve efficient subgraph searching over very large databases in cluster configurations. (c) 2021 The Authors. Published by Elsevier Inc. This is an open access article under the CC BYNC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： graph databases Subgraph search graph query processing graph indexing Subgraph isomorphism Large scale processing

来源：评论

学校读者我要写书评

暂无评论

Efficient single-pair all-shortest-path query processing for massive dynamic networks

引用

INFORMATION SCIENCES 2021年 546卷 1306-1327页

作者： Baek, Sun Geol Lee, Sungkil Eom, Young Ik Sungkyunkwan Univ Dept Elect & Comp Engn Suwon South Korea Sungkyunkwan Univ Coll Comp Suwon South Korea

The single-pair all-shortest-path problem is to find all possible shortest paths, given a single source-destination pair in a graph. Due to the lack of efficient algorithms for single-pair all-shortest-path problem, many applications used diverse types of modifications to the existing shortest-path algorithms such as Dijkstra's algorithm. Such approaches can facilitate the analysis of medium-sized static networks, but the heavy computational cost impedes their use for massive and dynamic real-world networks. In this paper, we present a novel single-pair all-shortest-path algorithm, which performs well on massive networks as well as dynamic networks. The efficiency of our algorithm stems from novel 2-hop label-based query processing on large-size networks. For dynamic networks, we also demonstrate how to incrementally maintain all shortest paths in 2-hop labels, which allows our algorithm to handle the topological changes of dynamic networks such as insertion or deletion of edges. We carried out experiments on real-world large datasets, and the results confirms the effectiveness of our algorithms for the single-pair all-shortest-path computation and the incremental maintenance of 2-hop labels. (C) 2020 Elsevier Inc. All rights reserved.

关键词： graph query processing All shortest paths Incremental maintenance

来源：评论

学校读者我要写书评

暂无评论

querying a graph database - language selection and performance considerations

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第1期82卷 45-68页

作者： Holzschuher, Florian Peinl, Rene Hof Univ Iisys D-95028 Hof Germany

NoSQL and especially graph databases are constantly gaining popularity among developers as they promise to deliver superior performance when handling highly interconnected data compared to relational databases. Apache Shindig is the reference implementation for OpenSocial with a highly interconnected data model. However, it had a relational database as back-end. In this paper we describe our experiences with the graph database Neo4j as back-end and compare Cypher, Gremlin and Java as alternatives for querying data with MySQL. We consider performance as well as usability from a developer's perspective. Our results show that Cypher is a good query language in terms of code readability and has a moderate overhead for most queries (20-200%). However, it has to be supplemented with "stored procedures" to make up for some performance deficits in pattern matching queries (>1000%). The RESTful API is unusable slow, whereas our WebSocket connection performs significantly better (>650%). (C) 2015 Elsevier Inc. All rights reserved.

关键词： graph databases Neo4j graph query processing Benchmarks Performance optimization WebSocket

来源：评论

学校读者我要写书评

暂无评论

Top-k Durable graph Pattern Queries on Temporal graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2019年第1期31卷 181-194页

作者： Semertzidis, Konstantinos Pitoura, Evaggelia Univ Ioannina Dept Comp Sci & Engn Ioannina 45500 Greece

graphs offer a natural model for the relationships and interactions among entities, such as those occurring among users in social and cooperation networks, and proteins in biological networks. Since most such networks are dynamic, to capture their evolution over time, we assume a sequence of graph snapshots where each graph snapshot represents the state of the network at a different time instance. Given this sequence, we seek to find the top-k most durable matches of an input graph pattern query, that is, the matches that exist for the longest period of time. The straightforward way to address this problem is to apply a state-of-the-art graph pattern matching algorithm at each snapshot and then aggregate the results. However, for large networks and long sequences, this approach is computationally expensive, since all matches have to be generated at each snapshot, including those appearing only once. We propose a new approach that uses a compact representation of the sequence of graph snapshots, appropriate time indexes to prune the search space, and strategies to determine the duration of the seeking matches. Finally, we present experiments with real datasets that illustrate the efficiency and effectiveness of our approach.

关键词： graph pattern temporal graph graph query processing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：