• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Scientific and statistical database management >Preflndex: An Efficient Supergraph Containment Search Technique
【24h】

Preflndex: An Efficient Supergraph Containment Search Technique

机译：Preflndex：一种有效的超图包含搜索技术

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Graphs are prevailingly used in many applications to model complex data structures. In this paper, we study the problem of super-graph containment search. To avoid the NP-complete subgraph isomorphism test, most existing works follow the filtering-verification framework and select graph-features to build effective indexes, which filter false results (graphs) before conducting the costly verification. However, searching features multiple times in the query graphs yields huge redundant computation, which leads to the emergence of the computation-sharing framework. This paper follows the roadmap of computation-sharing framework to efficiently process supergraph containment queries. Firstly, database graphs are clustered into disjoint groups for sharing the computation cost within each group. While it is shown NP-hard to maximize the computation-sharing benefits of a clustering, efficient algorithm is developed to approximate the optimal solution with an approximation factor of 1/2. A novel prefix-sharing indexing technique, Preflndex, is then proposed based on which efficient query processing algorithm integrating both filtering and verification is developed. Finally, Preflndex is enhanced with multi-level sharing and suffix-sharing to further avoid redundant computation. An extensive empirical study demonstrates the efficiency and scalability of our techniques which achieve orders of magnitudes of speed-up against the state-of-the-art techniques.
机译：图在许多应用程序中普遍使用，以对复杂的数据结构进行建模。在本文中，我们研究了超图包含搜索的问题。为了避免NP完全亚图同构测试，大多数现有工作都遵循过滤验证框架并选择图特征来构建有效索引，这些索引会在进行昂贵的验证之前过滤错误的结果（图）。但是，在查询图中多次搜索特征会产生大量的冗余计算，这导致了计算共享框架的出现。本文遵循了计算共享框架的路线图，以有效地处理上标包含查询。首先，将数据库图聚类为不相交的组，以共享每个组内的计算成本。虽然已证明NP很难最大程度地发挥聚类的计算共享优势，但仍开发了一种有效的算法，以近似因子1/2逼近最优解。然后提出了一种新的前缀共享索引技术，即Preflndex，在此基础上，开发了一种有效的查询处理算法，将过滤和验证结合在一起。最后，Preflndex通过多级共享和后缀共享得到了增强，从而进一步避免了冗余计算。广泛的经验研究证明了我们的技术的效率和可扩展性，与最新技术相比，可实现数量级的提速。

著录项

  • 来源
  • 会议地点 Heidelberg(DE);Heidelberg(DE)
  • 作者

    Gaoping Zhu; Xuemin Lin; Wenjie Zhang; Wei Wang; Haichuan Shang;

  • 作者单位

    The University of New South Wales, Sydney, NSW, Australia;

    The University of New South Wales, Sydney, NSW, Australia;

    The University of New South Wales, Sydney, NSW, Australia;

    The University of New South Wales, Sydney, NSW, Australia;

    The University of New South Wales, Sydney, NSW, Australia;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 TP311.13;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号