针对已有方法在XML数据上基于SLCA(smallest lowest common ancestor)语义处理查询时存在的冗余计算问题,提出了一种基于列存储的倒排索引CList,用于避免已有方法的倒排表中相同数据重复存储的问题。基于CList,提出了一种自顶向下的查...针对已有方法在XML数据上基于SLCA(smallest lowest common ancestor)语义处理查询时存在的冗余计算问题,提出了一种基于列存储的倒排索引CList,用于避免已有方法的倒排表中相同数据重复存储的问题。基于CList,提出了一种自顶向下的查询处理算法TDCOL(top-down SLCA computation based oncol-umn storage)来提升系统的处理性能。对于给定查询Q={k1,k2,...,km}的每个公共祖先结点,TDCOL在保证仅处理一次的情况下即可得到所有满足条件的结果,因而将时间复杂度降为O(m′|LID1|′lb|Skmaxch(v)|),其中|LID1|是Q的最短倒排表中包含的不同ID值的数目,Skmaxch(v)是所有被处理结点的包含关键字的孩子结点集中的最大集合。最后通过比较各种指标,从不同角度对TDCOL算法的性能优势进行了验证。展开更多
社区搜索的目标是从数据图中得到包含查询顶点的紧密子图,在社会学、生物学等领域有着广泛应用。针对现有基于子图连通性的社区模型的基础连通结构都是完全连通图,无法满足实际应用中用户对社区结构多样性的需求的问题,提出一种基于moti...社区搜索的目标是从数据图中得到包含查询顶点的紧密子图,在社会学、生物学等领域有着广泛应用。针对现有基于子图连通性的社区模型的基础连通结构都是完全连通图,无法满足实际应用中用户对社区结构多样性的需求的问题,提出一种基于motif连通性的社区搜索方法,其中包括基于motif连通性的社区(MCC)模型以及两个相应的社区搜索算法——MPCS(Motif-Processed Community Search)算法和基于MP-index的社区搜索算法。MCC模型可以协助用户自由指定社区的基础连通结构,MPCS算法可以用来解决MCC的搜索问题。此外,提出两个分别针对motif实例搜索过程及所属社区判断过程的剪枝优化技术。最后,设计了MP-index以避免社区搜索过程中的冗余遍历操作。在多个真实数据集上进行实验的结果表明:剪枝优化可以使MPCS算法的耗时减少60%~85%,而基于MP-index的社区搜索算法相较于加入剪枝优化的MPCS算法,效率提升普遍达到了2~3个数量级。可见,所提方法在商品推荐和社交网络等问题上有着实际应用价值。展开更多
社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文...社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文提出了规模受限的影响力社区搜索(Size-Constrained Influential Community search,SCIC),设计了基于深度优先搜索的基础算法,在此基础上进一步提出了基于结点预处理、剪枝规则和贪心策略的优化算法,用于减少冗余计算,加速枚举过程.在10个不同规模的数据集上进行实验,实验结果表明基础算法在搜索获得的社区规模和影响力上均优于已有算法,同时,本文提出的优化算法能够显著提升搜索效率,将响应时间缩减至基础算法的1%.展开更多
文摘针对已有方法在XML数据上基于SLCA(smallest lowest common ancestor)语义处理查询时存在的冗余计算问题,提出了一种基于列存储的倒排索引CList,用于避免已有方法的倒排表中相同数据重复存储的问题。基于CList,提出了一种自顶向下的查询处理算法TDCOL(top-down SLCA computation based oncol-umn storage)来提升系统的处理性能。对于给定查询Q={k1,k2,...,km}的每个公共祖先结点,TDCOL在保证仅处理一次的情况下即可得到所有满足条件的结果,因而将时间复杂度降为O(m′|LID1|′lb|Skmaxch(v)|),其中|LID1|是Q的最短倒排表中包含的不同ID值的数目,Skmaxch(v)是所有被处理结点的包含关键字的孩子结点集中的最大集合。最后通过比较各种指标,从不同角度对TDCOL算法的性能优势进行了验证。
文摘社区搜索的目标是从数据图中得到包含查询顶点的紧密子图,在社会学、生物学等领域有着广泛应用。针对现有基于子图连通性的社区模型的基础连通结构都是完全连通图,无法满足实际应用中用户对社区结构多样性的需求的问题,提出一种基于motif连通性的社区搜索方法,其中包括基于motif连通性的社区(MCC)模型以及两个相应的社区搜索算法——MPCS(Motif-Processed Community Search)算法和基于MP-index的社区搜索算法。MCC模型可以协助用户自由指定社区的基础连通结构,MPCS算法可以用来解决MCC的搜索问题。此外,提出两个分别针对motif实例搜索过程及所属社区判断过程的剪枝优化技术。最后,设计了MP-index以避免社区搜索过程中的冗余遍历操作。在多个真实数据集上进行实验的结果表明:剪枝优化可以使MPCS算法的耗时减少60%~85%,而基于MP-index的社区搜索算法相较于加入剪枝优化的MPCS算法,效率提升普遍达到了2~3个数量级。可见,所提方法在商品推荐和社交网络等问题上有着实际应用价值。
文摘社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文提出了规模受限的影响力社区搜索(Size-Constrained Influential Community search,SCIC),设计了基于深度优先搜索的基础算法,在此基础上进一步提出了基于结点预处理、剪枝规则和贪心策略的优化算法,用于减少冗余计算,加速枚举过程.在10个不同规模的数据集上进行实验,实验结果表明基础算法在搜索获得的社区规模和影响力上均优于已有算法,同时,本文提出的优化算法能够显著提升搜索效率,将响应时间缩减至基础算法的1%.
