مورد إلكتروني
Reuse Techniques for Efficiently Evaluating a Sequence of Iterative Graph Queries
| العنوان: | Reuse Techniques for Efficiently Evaluating a Sequence of Iterative Graph Queries |
|---|---|
| المؤلفون: | Jiang, Xiaolin |
| بيانات النشر: | eScholarship, University of California 2023-01-01 |
| تفاصيل مُضافة: | Gupta, Rajiv1 Jiang, Xiaolin |
| نوع الوثيقة: | Electronic Resource |
| مستخلص: | Graph analytics is employed in many domains (e.g., social networks, web graphs) to uncover insights by analyzing high volumes of connected data. Real world graphs are often large and iterative graph analytics requires repeated passes over the graph till the algorithm converges to a stable solution. As a result, iterative graph queries are expensive to evaluate. Thus, there has been a great deal of interest in developing scalable and efficient graph analytics systems for various platforms (e.g., GPUs, multicore servers, clusters). While much of the research has focused on developing algorithms for efficiently evaluating a single global graph query, in practice we may be faced with a sequence of queries. This research develops two platform independent complimentary reuse based approaches, value reuse and graph structure reuse, that collect information from executing a small number of queries and then use this information to speedup the evaluation of all future queries.The first approach is based on the observation that, due to their global nature, vertex specific graph queries present an opportunity for sharing work across queries. To take advantage of this opportunity, we have developed the VRGQ framework that accelerates the vi evaluation of a stream of queries via coarse-grained value reuse. In particular, the results of queries for a small set of source vertices are reused to speedup the evaluation of all future queries. We present a two step algorithm that in its first step initializes the query result based upon value reuse and then in the second step iteratively evaluates the query to convergence. The reused results for a small number of queries are held in a reuse table. Our experiments with best reuse configurations on four power law graphs and thousands of graph queries of five kinds yielded average speedups of 143×, 13.2×, 6.89×, 1.43×, and 1.18×. We have also extended the above approach to evaluation of queries over streaming graphs and simultaneous evalua |
| مصطلحات الفهرس: | Computer science, publication |
| URL: | |
| الإتاحة: | Open access content. Open access content public |
| ملاحظة: | application/pdf English |
| أرقام أخرى: | CDLER oai:escholarship.org:ark:/13030/qt2kg3z67h qt2kg3z67h https://escholarship.org/uc/item/2kg3z67hTest https://escholarship.orgTest/ 1410329236 |
| المصدر المساهم: | UC MASS DIGITIZATION From OAIster®, provided by the OCLC Cooperative. |
| رقم الانضمام: | edsoai.on1410329236 |
| قاعدة البيانات: | OAIster |
| الوصف غير متاح. |