Asset Details
Do you wish to reserve the book?
Query Optimization for Dynamic Graphs
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
Query Optimization for Dynamic Graphs
Do you wish to request the book?
Query Optimization for Dynamic Graphs
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Paper
Query Optimization for Dynamic Graphs
2014
Overview
Given a query graph that represents a pattern of interest, the emerging pattern detection problem can be viewed as a continuous query problem on a dynamic graph. We present an incremental algorithm for continuous query processing on dynamic graphs. The algorithm is based on the concept of query decomposition; we decompose a query graph into smaller subgraphs and assemble the result of sub-queries to find complete matches with the specified query. The novelty of our work lies in using the subgraph distributional statistics collected from the dynamic graph to generate the decomposition. We introduce a \"Lazy Search\" algorithm where the search strategy is decided on a vertex-to-vertex basis depending on the likelihood of a match in the vertex neighborhood. We also propose a metric named \"Relative Selectivity\" that is used to select between different query decomposition strategies. Our experiments performed on real online news, network traffic stream and a synthetic social network benchmark demonstrate 10-100x speedups over competing approaches.
Publisher
Cornell University Library, arXiv.org
Subject
