一种基于上界值剪枝的用户敏感top-k dominating查询方法

信息化社会带来了数据量的快速增长,但也导致数据的完整性和价值密度越来越低,如何从海量不完整数据中快速找到有价值的信息用于用户个性化推荐,已经成为研究的热点。结合上界值剪枝算法,提出一种用户敏感top-k dominating(TKD)查询方法(USTD)。该方法首先结合用户兴趣度,重新定义了不完整数据集上对象的支配关系及其度量方法,计算对象的权重支配分数;然后以重新定义的支配关系,证明了依据上界值可剪枝的条件;最后将上界值剪枝条件融于USTD的查询过程,以从数据集中快速找到前k个满足用户兴趣的数据。实验结果表明,USTD算法在查询速度上有一定提升,在查询结果的评分上具有显著优势。

一种有效的海量数据Top-k Dominating查询算法

在多准则决策支持等多个应用中,top-k dominating查询是一种十分实用的查询,它在潜在的巨大的数据空间中返回k个支配分数最大的元组.现有算法,要么需要为特定的属性组合构建索引,要么需要较大的I/O费用或内存费用,从而无法有效处理海量数据上top-k dominating查询.文中提出一种新的查询算法TDEP,该算法利用以较小代价为每个属性构建的有序列表来有效返回海量数据上的top-k dominating查询结果.文中将TDEP算法的执行明确地分为两个阶段:增长阶段和收缩阶段.在每个阶段,TDEP算法以round-robin方式读取涉及到的有序列表并维护候选元组,直到满足结束条件.文中分析了两个阶段的执行行为,提出一种新的不需要重新读取有序列表的支配分数计算方法.同时,文中还提出有效的早剪切操作,可以有效减少TDEP算法需要维护的候选元组数量.实验结果表明:和现有算法相比,TDEP算法具有较大的性能优势.

Quantum algorithm for minimum dominating set problem with circuit design

Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover’s search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.

分布式网络中连续时间周期的全局top-K频繁流测量

在分布式网络中,测量top-K频繁流对资源分配、安全监控等应用至关重要。现有的top-K频繁流测量工作存在不适用于测量分布式网络流量或只考虑单时间周期等局限。为此,提出了分布式网络中连续时间周期的全局top-K频繁流测量方案,在分布节点中布置了紧凑的概率数据结构来记录网络流信息,每个时间周期结束后分布节点向中心节点发送必要信息,中心节点汇聚得到从测量开始至当前时间周期的全局top-K频繁流。考虑到每条流可能出现在一个或多个测量节点,使用了不同的方法来减少传输开销。对于每条流只会出现在单一节点的情况,采用传输分段最小值的方法来获得阈值,实验结果表明这种方法减少了全量传输超过50%的传输开销。对于每条流会出现在多个节点的情况,提出了多阶段无误差处理方法和单阶段快速处理方法,分别应对不能容忍误差的场景和实际高速网络流量,相比每个时间周期都使用已有单周期方法,传输开销的实验表现降低了两个数量级。最后还提出了一种利用历史平均增值信息降低通信延迟的方法,实验结果表明该方法有效降低了限制信息的平均相对误差。

一次性条件下top-k高平均效用序列模式挖掘算法

针对传统序列模式挖掘(SPM)不考虑模式重复性且忽略各项的效用(单价或利润)与模式长度对用户兴趣度影响的问题,提出一次性条件下top-k高平均效用序列模式挖掘(TOUP)算法。TOUP算法主要包括两个核心步骤:平均效用计算和候选模式生成。首先,提出基于各项出现位置与项重复关系数组的CSP(Calculation Support of Pattern)算法计算模式支持度,从而实现模式平均效用的快速计算;其次,采用项集扩展和序列扩展生成候选模式,并提出了最大平均效用上界,基于该上界实现对候选模式的有效剪枝。在5个真实数据集和1个合成数据集上的实验结果表明,相较于TOUP-dfs和HAOP-ms算法,TOUP算法的候选模式数分别降低了38.5%~99.8%和0.9%~77.6%;运行时间分别降低了33.6%~97.1%和57.9%~97.2%。TOUP的算法性能更优,能更高效地挖掘用户感兴趣的模式。

A Game Theoretic Approach for a Minimal Secure Dominating Set

The secure dominating set(SDS),a variant of the dominating set,is an important combinatorial structure used in wireless networks.In this paper,we apply algorithmic game theory to study the minimum secure dominating set(Min SDS) problem in a multi-agent system.We design a game framework for SDS and show that every Nash equilibrium(NE) is a minimal SDS,which is also a Pareto-optimal solution.We prove that the proposed game is an exact potential game,and thus NE exists,and design a polynomial-time distributed local algorithm which converges to an NE in O(n) rounds of interactions.Extensive experiments are done to test the performance of our algorithm,and some interesting phenomena are witnessed.

Complex adaptive system theory,agent-based modeling,and simulation in dominant technology formation

Dominant technology formation is the key for the hightech industry to“cross the chasm”and gain an established foothold in the market(and hence disrupt the regime).Therefore,a stimulus-response model is proposed to investigate the dominant technology by exploring its formation process and mechanism.Specifically,based on complex adaptive system theory and the basic stimulus-response model,we use a combination of agent-based modeling and system dynamics modeling to capture the interactions between dominant technology and the socio-technical landscape.The results indicate the following:(i)The dynamic interaction is“stimulus-reaction-selection”,which promotes the dominant technology’s formation.(ii)The dominant technology’s formation can be described as a dynamic process in which the adaptation intensity of technology standards increases continuously until it becomes the leading technology under the dual action of internal and external mechanisms.(iii)The dominant technology’s formation in the high-tech industry is influenced by learning ability,the number of adopting users and adaptability.Therein,a“critical scale”of learning ability exists to promote the formation of leading technology:a large number of adopting users can promote the dominant technology’s formation by influencing the adaptive response of technology standards to the socio-technical landscape and the choice of technology standards by the socio-technical landscape.There is a minimum threshold and a maximum threshold for the role of adaptability in the dominant technology’s formation.(iv)The socio-technical landscape can promote the leading technology’s shaping in the high-tech industry,and different elements have different effects.This study promotes research on the formation mechanism of dominant technology in the high-tech industry,presents new perspectives and methods for researchers,and provides essential enlightenment for managers to formulate technology strategies.

Species’ geographical range, environmental range and traits lead to specimen collection preference of dominant plant species of grasslands in Northern China

Many different factors,such as species traits,socio-economic factors,geographical and environmental factors,can lead to specimen collection preference.This study aims to determine whether grassland specimen collection in China is preferred by species traits(i.e.,plant height,flowering and fruiting period),environmental range(i.e.,the temperature and precipitation range)and geographical range(i.e.,distribution range and altitudinal range).Ordinary least squares models and phylogenetic generalized linear mixed models were used to analyze the relationships between specimen number and the explanatory variables.Random Forest models were then used to find the most parsimonious multivariate model.The results showed that interannual variation in specimen number between 1900 and 2020 was considerable.Specimen number of these species in southeast China was notably lower than that in northwest China.Environmental range and geographical range of species had significant positive correlations with specimen number.In addition,there were relatively weak but significant associations between specimen number and species trait(i.e.,plant height and flowering and fruiting period).Random Forest models indicated that distribution range was the most important variable,followed by flowering and fruiting period,and altitudinal range.These findings suggest that future floristic surveys should pay more attention to species with small geographical range,narrow environmental range,short plant height,and short flowering and fruiting period.The correction of specimen collection preference will also make the results of species distribution model,species evolution and other works based on specimen data more accurate.

大图中多样化Top-k模式挖掘算法研究

频繁模式挖掘(Frequent Pattern Mining,FPM)是图数据挖掘领域的一项重要任务。该任务的目标是从图数据中找到出现频次大于给定阈值的所有模式。近年来,随着社交网络等大规模图数据的涌现,单一大图上的FPM问题受到广泛关注,并得到了较为充分的研究,取得了一系列研究成果。然而,已有技术大都存在着计算成本高、挖掘结果理解困难以及并行计算难等问题。针对上述问题,文中提出了一种从大规模图数据中挖掘多样化top-k模式的方法。首先设计了一个多样化函数,用于度量模式集合的多样性;随后设计了一种面向分布式图数据,具有提前终止特性的分布式挖掘算法DisTopk,以实现多样化top-k模式高效挖掘。在真实图数据和合成图数据上进行了大量实验,结果表明,与传统分布式挖掘算法相比,DisTopk算法能更高效地挖掘多样化top-k模式。

Safety and efficacy of transcatheter arterial embolization in autosomal dominant polycystic kidney patients with gross hematuria: Six case reports

BACKGROUND To retrospectively report the safety and efficacy of renal transcatheter arterial embolization for treating autosomal dominant polycystic kidney disease(ADPKD)patients with gross hematuria.CASE SUMMARY The purpose of this study is to retrospectively report the safety and efficacy of renal transcatheter arterial embolization for treating ADPKD patients with gross hematuria.Materials and methods:During the period from January 2018 to December 2019,renal transcatheter arterial embolization was carried out on 6 patients with polycystic kidneys and gross hematuria.Renal arteriography was performed first,and then we determined the location of the hemorrhage and performed embolization under digital subtraction angiography monitoring.Improvements in routine blood test results,routine urine test results,urine color and postoperative reactions were observed and analyzed.Results:Renal transcatheter arterial embolization was successfully conducted in 6 patients.The indices of 5 patients and the color of gross hematuria improved after surgery compared with before surgery.No severe complication reactions occurred.CONCLUSION For autosomal dominant polycystic kidney syndrome patients with gross hematuria,transcatheter arterial embolization was safe and effective.

Top-k空间偏好查询方法研究

随着无线通信技术的发展和智能移动终端的广泛普及,基于位置的服务已经融入了人们生活的方方面面。其中,Top-k空间偏好查询在地理信息系统、城市建设规划、资源调度与分配、旅游规划等领域具有重要的意义。Top-k空间偏好查询是根据空间对象周围的特征对空间对象进行等级评价,并返回具有最高等级评价的k个空间对象。目前,对于Top-k空间偏好查询的研究主要集中在欧式空间和路网环境,本文对欧式空间和路网环境下的Top-k空间偏好查询方法进行分析和比较。

基于本地差分隐私的网络测量Top-k目的地址估计研究

针对网络测量中的Top-k目的地址问题,设计了基于布谷鸟过滤器的ε-本地差分隐私Top-k目的地址估计机制。在保护隐私的前提下,该机制能够提高对Top-k目的地址的估计效果。采用了多轮迭代方法,将布谷鸟过滤器和本地差分隐私模型结合,在服务器端和客户端进行了一轮交互。理论分析部分证明了所提出的机制符合本地差分隐私模型,并在数据集上进行了实验,对比了F1分数、NCR分数以及L1误差,验证了所提机制的有效性。

无爪图中的次和与Dominating最长路

设H为一图.H中由m个点组成的独立集和由m个点组成的割集分别称为m-独立集和m-割集,而经过v∈V（H）的圈v-圈.设D为H的子图,测|D|和H-D分别表示|V（D）|（D的阶）和H-V（D）.称H是无爪的,如果它不含K1,3作为导出子图.称H是m-路连通的（m≥1）,如果|H|≥2,H的任一对点都由长度≥m的路相联.称只有一个点的图为0-路连通的.H中的路R是一dominating路,如果R是Hamilton的,或者V（H-R）是一独立点集.对H的子图A和D。

道路网多用户偏好Top-k天际线查询方法

已有的天际线(Skyline)查询主要聚焦于单用户场景,并基于单用户模型进行Skyline计算,而较少考虑道路网环境下多用户情况.为了弥补已有方法无法解决道路网络环境下多用户偏好和权重Top-k Skyline查询问题的不足,提出了一种基于道路网环境下多用户偏好Top-k Skyline(multi-user preference Top-k Skyline,MUP-TKS)查询方法.在道路网环境下考虑多用户的不同偏好和权重进行Skyline查询,可以快速得到符合查询用户群偏好和权重的结果集,提供用户群更好的决策支持.MUP-TKS首先通过所提的G_DBC算法,利用道路网中数据点与查询点之间的位置关系和新的索引结构Vor-R*-DHash剪枝、过滤数据点,从而得到距离较优集;再利用静态Skyline集不变的性质,预先计算、保存该集合;然后通过所提的新支配关系对距离较优集与静态Skyline集取并集后的集合S进行放松支配;最后利用所提TK_DC算法对经过放松支配后的候选结果集打分,依据数据点得分情况,排序输出Top-k个结果集返回用户群.理论研究与实验表明,所提方法具有较好的效率与可靠性.

On the dominating set in circular arc graphs

圆弧图是比区间图更广泛的一类交图.设 G=(V,E)是任意图,用V(G)、i(G)、ir(G)和β(G)分别表示 G 的控制数、独立控制数、无赘数和点覆盖数.讨论了圆弧图的这些图参数之间的关系.

卷积神经网络的top-k相似节点搜索方法

针对复杂网络环境下搜索与目标节点文本和结构均相似的top-k节点问题,本文提出了一种基于卷积神经网络的top-k相似节点搜索算法LRE-CNN.对于一个无向带权复杂网络,首先为网络中每个节点构造基于度和权重的最近邻网络模型,利用最近邻网络相对加权熵计算度和权重对节点结构的影响.然后,通过KL散度比较节点对的差异生成节点结构相似度,从而筛选出目标节点的候选相似节点.最后,利用卷积神经网络(CNN)抽取目标节点和候选相似节点的文本特征间的潜在关系,从而预测出与目标节点文本结构均相似的top-k节点.通过在不同规模的复杂网络上进行实验,并与现有主流相似节点搜索方法进行对比,实验结果表明所提方法具有较高的检索准确率,同时具有较高的执行效率,能够有效适用于大规模复杂网络环境下的相似节点top-k搜索.

图论中图的Dominating圈的存在

本文作者采用构造分析的方法研究并得到了一类非Dominating圈图的结构。在此基础上就图的两个参数研究了图的Dominating圈的存在,得到一些关于Dominating圈存在的新结果,扩大了Dominating圈图的范围,而且这些结果均比Veldman得到的更好。主要结果为:设图G是具有n(≥5)个顶点的简单图,如果对于G的任意一对分离的边e,f及对V(G)的任意非空子集S d(e)+d(f)≥n-3及ω_1(G-S)≤|S|则图G是Dominating圈图。

子图的度与 Dominating 圈

笔者利用子图的度给出了如下结果：对2-连通无爪图 G，若任意同构于 K2的不相邻子图 H1，H2，H3满足：d（H1）＋d（H2）＋d（H3）≥｜G｜-1，则 G 的任意最长圈是 Dominating 圈。

Diversity of Pareto front: A multiobjective genetic algorithm based on dominating information

In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking method based on dominating number is proposed to build the Pareto front. Without increasing basic Pareto method’s computation complexity and introducing new parameters, a new multiobjective genetic algorithm based on proposed ranking method (MOGA-DN) is presented. Simulation results on function optimization and parameters optimization of control system verify the efficiency of MOGA-DN.

Minimum Dominating Tree Problem for Graphs

A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.