PRAGUE: towards blending practical visual subgraph query formulation and query processing
In a previous paper, we laid out the vision of a novel graph query processing paradigm where instead of processing a visual query graph after its construction, it interleaves visual query formulation and processing by exploiting the latency offered by the GUI to filter irrelevant matches and prefetc...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/99467 http://hdl.handle.net/10220/12884 |
| _version_ | 1826117586256920576 |
|---|---|
| author | Bhowmick, Sourav S. Jin, Changjiu Choi, Byron Zhou, Shuigeng |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Bhowmick, Sourav S. Jin, Changjiu Choi, Byron Zhou, Shuigeng |
| author_sort | Bhowmick, Sourav S. |
| collection | NTU |
| description | In a previous paper, we laid out the vision of a novel graph query processing paradigm where instead of processing a visual query graph after its construction, it interleaves visual query formulation and processing by exploiting the latency offered by the GUI to filter irrelevant matches and prefetch partial query results [8]. Our first attempt at implementing this vision, called GBLENDER [8], shows significant improvement in system response time (SRT) for sub graph containment queries. However, GBLENDER suffers from two key drawbacks, namely inability to handle visual sub graph similarity queries and inefficient support for visual query modification, limiting its usage in practical environment. In this paper, we propose a novel algorithm called PRAGUE (Practical visu Al Graph QUery Blender), that addresses these limitations by exploiting a novel data structure called spindle-shaped graphs (SPIG). A SPIG succinctly records various information related to the set of super graphs of a newly added edge in the visual query fragment. Specifically, PRAGUE realizes a unified visual framework to support SPIG-based processing of modification-efficient sub graph containment and similarity queries. Extensive experiments on real-world and synthetic datasets demonstrate effectiveness of PRAGUE. |
| first_indexed | 2024-10-01T04:29:43Z |
| format | Conference Paper |
| id | ntu-10356/99467 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:29:43Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/994672020-05-28T07:18:31Z PRAGUE: towards blending practical visual subgraph query formulation and query processing Bhowmick, Sourav S. Jin, Changjiu Choi, Byron Zhou, Shuigeng School of Computer Engineering IEEE International Conference on Data Engineering (28th : 2012 : Washington, D. C., US) In a previous paper, we laid out the vision of a novel graph query processing paradigm where instead of processing a visual query graph after its construction, it interleaves visual query formulation and processing by exploiting the latency offered by the GUI to filter irrelevant matches and prefetch partial query results [8]. Our first attempt at implementing this vision, called GBLENDER [8], shows significant improvement in system response time (SRT) for sub graph containment queries. However, GBLENDER suffers from two key drawbacks, namely inability to handle visual sub graph similarity queries and inefficient support for visual query modification, limiting its usage in practical environment. In this paper, we propose a novel algorithm called PRAGUE (Practical visu Al Graph QUery Blender), that addresses these limitations by exploiting a novel data structure called spindle-shaped graphs (SPIG). A SPIG succinctly records various information related to the set of super graphs of a newly added edge in the visual query fragment. Specifically, PRAGUE realizes a unified visual framework to support SPIG-based processing of modification-efficient sub graph containment and similarity queries. Extensive experiments on real-world and synthetic datasets demonstrate effectiveness of PRAGUE. 2013-08-02T04:28:18Z 2019-12-06T20:07:49Z 2013-08-02T04:28:18Z 2019-12-06T20:07:49Z 2012 2012 Conference Paper https://hdl.handle.net/10356/99467 http://hdl.handle.net/10220/12884 10.1109/ICDE.2012.49 en |
| spellingShingle | Bhowmick, Sourav S. Jin, Changjiu Choi, Byron Zhou, Shuigeng PRAGUE: towards blending practical visual subgraph query formulation and query processing |
| title | PRAGUE: towards blending practical visual subgraph query formulation and query processing |
| title_full | PRAGUE: towards blending practical visual subgraph query formulation and query processing |
| title_fullStr | PRAGUE: towards blending practical visual subgraph query formulation and query processing |
| title_full_unstemmed | PRAGUE: towards blending practical visual subgraph query formulation and query processing |
| title_short | PRAGUE: towards blending practical visual subgraph query formulation and query processing |
| title_sort | prague towards blending practical visual subgraph query formulation and query processing |
| url | https://hdl.handle.net/10356/99467 http://hdl.handle.net/10220/12884 |
| work_keys_str_mv | AT bhowmicksouravs praguetowardsblendingpracticalvisualsubgraphqueryformulationandqueryprocessing AT jinchangjiu praguetowardsblendingpracticalvisualsubgraphqueryformulationandqueryprocessing AT choibyron praguetowardsblendingpracticalvisualsubgraphqueryformulationandqueryprocessing AT zhoushuigeng praguetowardsblendingpracticalvisualsubgraphqueryformulationandqueryprocessing |