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

Privacy-Preserving Planarity Testing of distributed graphs

TRANSACTIONS ON DATA PRIVACY 2019年第2期12卷 117-144页

作者： Barshap, Guy Tassa, Tamir Open Univ Israel Tel Aviv Israel Ben Gurion Univ Negev Beer Sheva Israel

We study the problem of privacy-preserving planarity testing of distributed graphs. The setting involves several parties that hold private graphs on the same set of vertices, and an external mediator that helps with performing the computations. Their goal is to test whether the union of their private graphs is planar, but in doing so each party wishes to deny from his peers any information on his own private edge set beyond what is implied by the final output of the computation. We present a privacy-preserving protocol for that purpose which is based on the Hanani-Tutte theorem. That theorem enables translating the planarity question into the question of whether a specific system of linear equations over the field F-2 is solvable. Our protocol uses a diverse cryptographic toolkit which includes techniques such as homomorphic encryption, oblivious Gaussian elimination, and private set intersection.

关键词： secure multiparty computation privacy-preserving distributed computations distributed graphs graph planarity

来源：评论

学校读者我要写书评

暂无评论

Privacy-Preserving Planarity Testing of distributed graphs 32nd

Privacy-Preserving Planarity Testing of Distributed Graphs

引用

32nd Annual IFIP WG 11.3 Conference on Data and Applications Security and Privacy (DBSec)

作者： Barshap, Guy Tassa, Tamir Open Univ Raanana Israel

ISBN: (纸本)9783319957296;9783319957289

We study the problem of privacy-preserving planarity testing of distributed graphs. The setting involves several parties that hold private graphs on the same set of vertices, and an external mediator that helps with performing the computations. Their goal is to test whether the union of their private graphs is planar, but in doing so each party wishes to deny from his peers any information on his own private edge set beyond what is implied by the final output of the computation. We present a privacy-preserving protocol for that purpose which is based on the Hanani-Tutte Theorem. That theorem enables translating the planarity question into the question of whether a specific system of linear equations over the field F-2 is solvable. Our protocol uses a diverse cryptographic toolkit which includes techniques such as homomorphic encryption, oblivious Gaussian elimination, and private set intersection. This is the first time that a solution to this problem is presented.

关键词： Secure multiparty computation Privacy-preserving distributed computations distributed graphs Graph planarity

来源：评论

学校读者我要写书评

暂无评论

Monitoring Properties of Large, distributed, Dynamic graphs 31

Monitoring Properties of Large, Distributed, Dynamic Graphs

引用

31st IEEE International Parallel and distributed Processing Symposium (IPDPS)

作者： Yehuda, Gal Keren, Daniel Akaria, Islam Technion Comp Sci Fac Haifa Israel Univ Haifa Comp Sci Dept Haifa Israel

ISBN: (纸本)9781538639146

The following is a very common question in numerous theoretical and application-related domains: given a graph G, does it satisfy some given property? For example, is G connected? Is its diameter smaller than a given threshold? Is its average degree larger than a certain threshold? Traditionally, algorithms to quickly answer such questions were developed for static and centralized graphs (i.e. G is stored in a central server and the list of its vertices and edges is static and quickly accessible). Later, as dictated by practical considerations, a great deal of attention was given to on-line algorithms for dynamic graphs (where vertices and edges can be added and deleted);the focus of research was to quickly decide whether the new graph still satisfies the given property. Today, a more difficult version of this problem, referred to as the distributed monitoring problem, is becoming increasingly important: large graphs are not only dynamic, but also distributed, that is, G is partitioned between a few servers, none of which "sees" G in its entirety. The question is how to define local conditions, such that as long as they hold on the local graphs, it is guaranteed that the desired property holds for the global G. Such local conditions are crucial for avoiding a huge communication overhead. While defining local conditions for linear properties (e.g. average degree) is relatively easy, they are considerably more difficult to derive for non-linear functions over graphs. We propose a solution and a general definition of solution optimality, and demonstrate how to apply it to two important graph properties-the spectral gap and the number of triangles. We also define an absolute lower bound on the communication overhead for distributed monitoring, and compare our algorithm to it, with excellent results. Last but not least, performance improves as the graph becomes larger and denser-that is, when distributing it is more important.

关键词： distributed graphs dynamic graphs monitoring

来源：评论

学校读者我要写书评

暂无评论

Efficient distributed path computation on RDF knowledge graphs using partial evaluation

引用

WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS 2022年第2期25卷 1005-1036页

作者： Mehmood, Qaiser Saleem, Muhammad Jha, Alokkumar D'Aquin, Mathieu NUI Galway Data Sci Inst Galway Ireland AKSW Leipzig Germany Stanford Univ Stanford CA 94305 USA

A key property of Linked Data is the representation and publication of data as interconnected labelled graphs where different resources linked to each other form a network of meaningful information. Searching these important relationships between resources - within single or distributed graphs - can be reduced to a pathfinding or navigation problem, i.e., looking for chains of intermediate nodes. SPARQL1.1, the current standard query language for RDF-based Linked Data defines a construct - called Property Paths (PPs) - to navigate between entities within a single graph. Since Linked Data technologies are naturally aimed at decentralised scenarios, there are many cases where centralising this data is not feasible or even not possible for querying purposes. To address these problems, we propose a SPARQL PP-based graph processing approach - dubbed DpcLD - where users can execute SPARQL PP queries and find paths distributed across multiple, connected graphs exposed as SPARQL endpoints. To execute the distributed path queries we implemented an index-free, cache-based query engine that communicates with a shared algorithm running on each remote endpoint, and computes the distributed paths. In this paper, we highlight the way in which this approach exploits and aggregates partial paths, within a distributed environment, to produce complete results. We perform extensive experiments to demonstrate the performance of our approach on two datasets: One representing 10 million triples from the DBPedia SPARQL benchmark, and another full benchmark dataset corresponding to 124 million triples. We also perform a scalability test of our approach using real-world genomics datasets distributed across multiple endpoints. We compare our distributed approach with other distributed and centralized pathfinding approaches, showing that it outperforms other distributed approaches by orders of magnitude, and provides a good trade-off for cases when the data cannot be centralised.

关键词： distributed graphs Reachability Federated paths Graph traversal Path caching Path query RDF SPARQL 1 1 Property path

来源：评论

学校读者我要写书评

暂无评论

A Survey on distributed Graph Pattern Matching in Massive graphs

引用

ACM COMPUTING SURVEYS 2021年第2期54卷 36-36页

作者： Bouhenni, Sarra Yahiaoui, Said Nouali-Taboudjemat, Nadia Kheddouci, Hamamache Ecole Natl Super Informat BP M68 Oued Smar 16309 Algeria Univ Lyon 1 Univ Lyon LIRIS CNRS F-69622 Villeurbanne France Ctr Rech Informat Sci & Tech CERIST Ben Aknoun 16030 Algeria

Besides its NP-completeness, the strict constraints of subgraph isomorphism are making it impractical for graph pattern matching (GPM) in the context of big data. As a result, relaxed GPM models have emerged as they yield interesting results in a polynomial time. However, massive graphs generated by mostly social networks require a distributed storing and processing of the data over multiple machines, thus, requiring GPM to be revised by adopting new paradigms of big graphs processing, e.g., Think-Like-A-Vertex and its derivatives. This article discusses and proposes a classification of distributed GPM approaches with a narrow focus on the relaxed models.

关键词： Graph pattern matching distributed graphs graph simulation subgraph isomorphism

来源：评论

学校读者我要写书评

暂无评论

DIGDUG: Scalable Separable Dense Graph Pruning and Join Operations in MapReduce

引用

IEEE TRANSACTIONS ON BIG DATA 2021年第6期7卷 930-951页

作者： Shukla, Manu Dharme, Dinesh Ramnarain, Pallavi Santos, Ray Dos Lu, Chang-Tien Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA Omnisci Corp Palo Alto CA 94306 USA US Army Labs ERDC GRL Alexandria VA 22315 USA

Linking topics to specific experts in technical documents and finding connections between experts are crucial for detecting the evolution of emerging topics and the relationships between their influencers in state-of-the-art research. Current techniques that make such connections are limited to similarity measures. Methods based on weights such as TF-IDF and frequency to identify important topics and self joins between topics and experts are generally utilized to identify connections between experts. However, such approaches are inadequate for identifying emerging keywords and experts since the most useful terms in technical documents tend to be infrequent and concentrated in just a few documents. This makes connecting experts through joins on large dense graphs challenging. In this article, we present DIGDUG, a framework that identifies emerging topics by applying graph operations to technical terms. The framework identifies connections between authors of patents and journal papers by performing joins on connected topics and topics associated with the authors at scale. The problem of scaling the graph operations for topics and experts is solved through dense graph pruning and graph joins categorized under their own scalable separable dense graph class. Experiments were performed on technical domains to validate the utility of the connections between interests and experts. Comparing our graph join and pruning technique against multiple graph and join methods in MapReduce revealed a significant improvement in performance using our approach.

关键词： Big Data Social networking (online) Patents Joining processes Iterative methods Data mining Organizations Big data distributed graphs MapReduce graph joins

来源：评论

学校读者我要写书评

暂无评论

A Scalable Approach for Dynamic Evacuation Routing in Large Smart Buildings 5

A Scalable Approach for Dynamic Evacuation Routing in Large ...

引用

5th IEEE International Conference on Smart Computing (SMARTCOMP)

作者： Van-Quyet Nguyen Huu-Duy Nguyen Quyet-Thang Huynh Venkatasubramanian, Nalini Kim, Kyungbaek Chonnam Natl Univ Dept Elect & Comp Engn Gwangju South Korea Hung Yen Univ Technol & Educ Fac Informat Technol Hai Duong Vietnam Hanoi Univ Sci & Technol Hanoi Vietnam Univ Calif Irvine Dept Comp Sci Irvine CA USA

ISBN: (纸本)9781728116891

This paper considers the problem of dynamic evacuation routing in large smart buildings. We investigate a scalable routing approach which not only generates effective routes for evacuees but also quickly updates routes as the disaster status and building conditions could change during the evacuation time. We first design a flexible and scalable evacuation system for large smart buildings with multiple levels of computational support. Given such a system, we develop a novel distributed algorithm for finding effective evacuation routes dynamically by using an LCDT (Length-Capacity-Density-Trustiness) weighted graph model, which is built upon the current disaster information and building conditions. Finally, we propose a caching strategy which expedites dynamic route generation with the current effective route part(s) in order to improve the performance of dynamic evacuation in large buildings. To validate our approach, we test the proposed algorithm with our implementation of an evacuation simulator and compare the results with other approaches. Experimental results show that our approach outperforms other ones in the aspect of the evacuation time reduction and the maximum number of people being evacuated in each time span.

关键词： Dynamic Evacuation Routing Emergence Evacuation Systems Evacuation Simulator distributed graphs

来源：评论

学校读者我要写书评

暂无评论

Parallel and scalable combinatorial string algorithms on distributed memory systems

Parallel and scalable combinatorial string algorithms on dis...

引用

作者： Flick, Patrick Georgia Institute of Technology

学位级别：博士

Methods for processing and analyzing DNA and genomic data are built upon combinatorial graph and string algorithms. The advent of high-throughput DNA sequencing is enabling the generation of billions of reads per experiment. Classical and sequential algorithms can no longer deal with these growing data sizes - which for the last 10 years have greatly out-paced advances in processor speeds. Processing and analyzing state-of-the-art genomic data sets require the design of scalable and efficient parallel algorithms and the use of large computing clusters. Suffix arrays and trees are fundamental string data structures, which lie at the foundation of many string algorithms, with important applications in text processing, information retrieval, and computational biology. Conversely, the parallel construction of these indices is an actively studied problem. However, prior approaches lacked good worst-case run-time guarantees and exhibit poor scaling and overall performance. In this work, we present our distributed-memory parallel algorithms for indexing large datasets, including algorithms for the distributed construction of suffix arrays, LCP arrays, and suffix trees. We formulate a generalized version of the All-Nearest-Smaller-Values problem, provide an optimal distributed solution, and apply it to the distributed construction of suffix trees - yielding a work-optimal parallel algorithm. Our algorithms for distributed suffix array and suffix tree construction improve the state-of-the-art by simultaneously improving worst-case run-time bounds and achieving superior practical performance. Next, we introduce a novel distributed string index, the distributed Enhanced Suffix Array (DESA) - based on the suffix and LCP arrays, the DESA consists of these and additional distributed data structures. The DESA is designed to allow efficient pattern search queries in distributed memory while requiring at most O(n/p) memory per process. We present efficient distributed-memory paralle

关键词： distributed memory Suffix array Suffix tree Enhanced suffix arrays De Bruijn graphs distributed graphs Connected components

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Enabling lock-free concurrent workers over temporal graphs composed of multiple time-series 18

Enabling lock-free concurrent workers over temporal graphs c...

引用

33rd Annual ACM Symposium on Applied Computing (ACM SAC)

作者： Fouquet, Francois Hartmann, Thomas Mosser, Sebastien Cordy, Maxime Univ Luxembourg SnT Luxembourg Luxembourg Univ Cote dAzur I3S Nice France

ISBN: (纸本)9781450351911

Time series are commonly used to store temporal data, e.g., sensor measurements. However, when it comes to complex analytics and learning tasks, these measurements have to be combined with structural context data. Temporal graphs, connecting multiple time-series, have proven to be very suitable to organize such data and ultimately empower analytic algorithms. Computationally intensive tasks often need to be distributed and parallelized among different workers. For tasks that cannot be split into independent parts, several workers have to concurrently read and update these shared temporal graphs. This leads to inconsistency risks, especially in the case of frequent updates. distributed locks can mitigate these risks but come with a very high-performance cost. In this paper, we present a lock-free approach allowing to concurrently modify temporal graphs. Our approach is based on a composition operator able to do online reconciliation of concurrent modifications of temporal graphs. We evaluate the efficiency and scalability of our approach compared to lock-based approaches.

关键词： distributed computing Time-Series distributed graphs Temporal graphs Data analytics Lock-free workers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：