A Tree Pattern Matching Algorithm for XML Queries with Structural Preferences

In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly complex model, the lack or the ignorance of the explicit document model (DTD—Document Type Definition, Schema, etc.) increases the risk of obtaining an empty result set when the query is too specific, or, too large result set when it is too vague (e.g. it contains wildcards such as “*”). The reason is that in both cases, users write queries according to the document model they have in mind;this can be very far from the one that can actually be extracted from the document. Opposed to exact queries, preference queries are more flexible and can be relaxed to expand the search space during their evaluations. Indeed, during their evaluation, certain constraints (the preferences they contain) can be relaxed if necessary to avoid precisely empty results;moreover, the returned answers can be filtered to retain only the best ones. This paper presents an algorithm for evaluating such queries inspired by the TreeMatch algorithm proposed by Yao et al. for exact queries. In the proposed algorithm, the best answers are obtained by using an adaptation of the Skyline operator (defined in relational databases) in the context of documents (trees) to incrementally filter into the partial solutions set, those which satisfy the maximum of preferential constraints. The only restriction imposed on documents is No-Self-Containment.

基于模式语义的非膨胀性Pattern Tree简化

近年来,XQuery逐渐成为XML查询语言的事实标准。PatternTree被广泛应用于XQuery查询处理。PatternTree用匹配方法处理查询,其本身的大小和复杂程度决定了匹配的效率。该文论述了利用模式语义简化PatternTree的规则。这种方法避免了因插入冗余节点而导致PatternTree的膨胀。三个判断冗余节点的规则不但可以判断叶节点的冗余,而且可以在保留叶节点的情况下,判断非叶节点的冗余。实验证明了方法的可行性和有效性。

Pattern Tree最小简单分解策略

PatternTree(PTQ)是复杂的树状结构,求解PTQ需要在XML文档集合中查找与之匹配的数据。在PTQ中,只有部分节点是需要输出的查询目标节点,其余节点则是中间结果。因此,如何在求解过程中尽量避免中间结果的产生,是XML查询优化面临的一个关键问题。论文提出了一种PTQ分解策略,能够根据不同查询操作的粒度,将PTQ分解为可用一种内部操作实现的最大片断集合。从而有效的限制中间结果的产生,提高查询效率。

Introducing tree neighbouring relationship factors in forest pattern spatial analysis:weighted Delaunay triangulation method

It is important to quantify and analyze forest spatial patterns for studying biological characteristics,population interaction and the relationship between the population and environment.In this study,the forest spatial structure unit was generated based on the Delaunay triangulation model(DTM),and the weights were generated using the comprehensive values of the tree diameter at breast height,total height and crown width.The distance between neighbors determined by the DTM was weighted to transform the original coordinates of trees into logical coordinates.Then,a weighted spatial pattern(WSP)was developed.After weighting,the neighboring trees were replaced,the replacement ratio was 38.3%,and there was 57.4%of the central tree.Correlation analysis showed that the uniform angle index of the WSP was significantly correlated with the tree size standard deviation under uniformity(r=0.932)and randomness(r=0.711).The DTM method not only considers the spatial distance between trees,but also considers the non-spatial attributes of trees.By changing the spatial topological relation between trees,this method further improves the spatial structure measurement of forest.

Improved Pattern Tree for Incremental Frequent-Pattern Mining

By analyzing the existing prefix-tree data structure, an improved pattern tree was introduced for processing new transactions. It firstly stored transactions in a lexicographic order tree and then restructured the tree by sorting each path in a frequency-descending order. While updating the improved pattern tree, there was no need to rescan the entire new database or reconstruct a new tree for incremental updating. A test was performed on synthetic dataset T1014D100K with 100 000 transactions and 870 items. Experimental results show that the smaller the minimum sup- port threshold, the faster the improved pattern tree achieves over CanTree for all datasets. As the minimum support threshold increased from 2% to 3.5%, the runtime decreased from 452.71 s to 186.26 s. Meanwhile, the runtime re- quired by CanTree decreased from 1 367.03 s to 432.19 s. When the database was updated, the execution time of im- proved pattern tree consisted of construction of original improved pattern trees and reconstruction of initial tree. The experiment results showed that the runtime was saved by about 15% compared with that of CanTree. As the number of transactions increased, the runtime of improved pattern tree was about 25% shorter than that of FP-tree. The improved pattern tree also required less memory than CanTree.

Generating IDS Attack Pattern Automatically Based on Attack Tree

Generating attack pattern automatically based on attack tree is studied. The extending definition of attack tree is proposed. And the algorithm of generating attack tree is presented. The method of generating attack pattern automatically based on attack tree is shown, which is tested by concrete attack instances. The results show that the algorithm is effective and efficient. In doing so, the efficiency of generating attack pattern is improved and the attack trees can be reused.

Study on Bush Tree Growth in XLPE Using 3D PD Patterns

Exploitation of equipment with cross linked polyethylene (XLPE ) insulation requires its condition monitoring and diagnostic. Traditionally diagnostics of insulation is carried out by means of partial discharge detection. However, such identification of a defect, for example, void, inclusion or treeing, does not say about its danger from a point of view of full insulation gap breakdown and insulation construction failure. For this purpose a 29 kV CN-CV cable sample is studied. The experiment is based on research for determination of the dependencies between PD characteristics in XLPE upon time and three dimension PD patterns of corresponding treeing. The investigations were carried out by means of electrical measurement of PD current and simultaneous optical recording of treeing image. The needleplane electrode is applied as the electrode. As a result, -q-n PD patterns which are used as the bases to bush tree initialization and growth can be obtained. Test results show that PD pattern recognition can be applied as a powerful tool for recognizing electrical tree initialization and growth. This can make a good basis for on-line condition monitoring of high voltage power cable.

Association RuleMining Frequent-Pattern-Based Intrusion Detection in Network

In the network security system,intrusion detection plays a significant role.The network security system detects the malicious actions in the network and also conforms the availability,integrity and confidentiality of data informa-tion resources.Intrusion identification system can easily detect the false positive alerts.If large number of false positive alerts are created then it makes intrusion detection system as difficult to differentiate the false positive alerts from genuine attacks.Many research works have been done.The issues in the existing algo-rithms are more memory space and need more time to execute the transactions of records.This paper proposes a novel framework of network security Intrusion Detection System(IDS)using Modified Frequent Pattern(MFP-Tree)via K-means algorithm.The accuracy rate of Modified Frequent Pattern Tree(MFPT)-K means method infinding the various attacks are Normal 94.89%,for DoS based attack 98.34%,for User to Root(U2R)attacks got 96.73%,Remote to Local(R2L)got 95.89%and Probe attack got 92.67%and is optimal when it is compared with other existing algorithms of K-Means and APRIORI.

Mining condensed frequent subtree base

In frequent tree pattern mining, the number of frequent subtrees generated is often too large. To tackle this problem, the concept of condensed frequent subtree base is proposed. The base consists of the maximal frequent subtrees for a series of support thresholds. It is a subset of frequent subtrees, and is used to approximate the support of arbitrary frequent subtrees with guaranteed maximal error bound. In addition, an algorithm is developed to mine such a condensed subtree base in a database of labeled rooted ordered trees. The algorithm adopts the way of fight-most extension to generate systematically all frequent rooted ordered subtrees. Several techniques are proposed to prune the branches that do not correspond to the maximal frequent subtrees. Heuristic techniques are used to arrange the order of computation so that relatively expensive computation is avoided as much as possible. Experimental results show that the size of the base is less than 10% of that of the complete set, and the algorithm outperforms the previous algorithms.

Ethnographic Decision Tree Modeling of the Decision Criteria and Decision Patterns for Adult Married Women with Unexpected Pregnancies

Introduction: As far as adult and married women were concerned, when they occurred to “unplanned pregnancy”, they felt so surprised and concussive all the time. Besides, the unplanned pregnancy also affects the other members in the family system. Therefore, when married women have to face the choice: “birth” or “abortion”, they’ll consider lots of thoughts and different decision criteria and decision pattern under various influences on physician, mind, mental and society. The purpose of this study was to investigate the criteria considered and the decision patterns involved when adult married women decide whether to terminate or continue an unplanned pregnancy. Methods: The study uses the method—“Ethnographic Decision Tree Modeling” [1] to build model of the decision criteria and decision patterns involved when adult married women make a decision about their unplanned pregnancy. There are three process in the research method: “Pilot Study”—interview two groups, every group distinct 4 married adult women with unplanned pregnancies, which decide whether to terminate or continue an unplanned pregnancy, what is the items of decision characters affect to the choice: “birth” or “abortion”. “Building of the Model”, displays the importance in proper order of those items and build the modeling with these two groups of women. “Testing of the Model”: investigate the criteria considered and the decision patterns involved when adult married women decide whether to terminate or continue an unplanned pregnancy. The study interviewed 34 married adult women with 43 unplanned pregnancies totally. Results: The result of the study finds out 12 items of decision characters, including planning to get pregnant or not, stability of feelings for married partner, the points of view on life, was affected by mother, mother-in-law, an husband’s emphasis on male, the meanings of children, the financial burden, the plan an assignment of career and time, the past pregnant experiences, the status of raising children, the health of parents and fetus, the effect of living environment, and social and cultural vision. Besides, there are four decision patterns of married adult women with unplanned pregnancy are “receiving abortion positively”;“giving birth as long as getting pregnancy naturally”;“ the minds are hesitative and changeable”, and “being forced by important others.” Conclusion: By setting the decision model tree, we found several decision criteria and patterns, and possible modes actions to be taken, could offer to see the adult married women’s decision-making and struggles in mind about unplanned pregnancy.

基于FP-Tree的模式分解算法

提出了基于FP-Tree的PD算法。该算法将模式分解焦点从原始数据集转移到数据相对集中的FP-Tree上,从而进一步提高了PD算法挖掘频繁模式集的效率。文中以实例说明了该算法的工作过程。

基于OWSFP-Tree的最大频繁项目集挖掘算法

为了解决FP-Max算法挖掘最大频繁项目集时递归生成条件模式树和超集检验的问题,提出了基于单向有序FP-Tree的NCFP-Max算法。该算法在挖掘过程中采用预剪枝策略减少挖掘结点,利用单向有序FP-Tree避免每次存储当前挖掘出的频繁项目集之前都需要超集检验,利用项目表格避免递归生成条件模式树减少时空资源。实验结果表明,在事务条数多、项的数量大的情况下,NCFP-Max算法的挖掘时间比FP-Max算法缩短了50%左右。

基于FP-Tree的最大频繁项目集挖掘及更新算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,之前的很多研究都是采用Apriori类的候选项目集生成-检验方法.然而,候选项目集产生的代价是很高的,尤其是在存在大量强模式和/或长模式的时候.提出了一种快速的基于频繁模式树(FP-tree)的最大频繁项目集挖掘DMFIA(discover maximum frequent itemsets algorithm)及其更新算法UMFIA(update maximum frequent itemsets algorithm).算法UMFIA将充分利用以前的挖掘结果来减少在更新的数据库中发现新的最大频繁项目集的费用.

基于FP-tree的最大频繁模式挖掘算法

在FP-tree结构的基础上提出了最大频繁模式挖掘算法FP-Max。算法FP-Max只需要两次数据库扫描,挖掘过程不会产生候选项集。实验表明,算法FP-Max在挖掘密集型数据集方面是高效的。

基于FP-Tree模型的频繁轨迹模式挖掘方法

通过对经典频繁模式数据结构FP-tree的扩展与改进,提出了一种适用于处理轨迹数据的灵活高效的FP-tree轨迹挖掘方法(NFTM)。首先运用二维筛选和GPS格式过滤的方法对轨迹进行预处理,然后将有效数据经一次扫描后,生成按照真实轨迹顺序排列且具备时空属性的改进型FP-tree,使用动态数组存储模式挖掘过程中得到的候选集,根据用户的输入针对性输出相应时间和频率范围的频繁轨迹。最后通过与GSP算法、Prefixspan算法的对比测试表明,该算法具有更短执行时间和更优性能。

基于FP-tree和约束概念格的关联规则挖掘算法及应用研究

现有的基于频繁模式树FP-tree和概念格的规则挖掘算法在构造概念格时存在重复遍历FP-tree问题,在挖掘后件约束的规则时算法构造的概念格包含冗余结点。针对这两个问题,提出了通过遍历FP-tree生成候选概念格节点的策略,并根据候选概念格节点进一步构造规则约束条件下无冗余概念格。通过实际项目中大气腐蚀数据进行算法的应用,结果表明该算法比现有算法具有更高的挖掘效率且腐蚀规则结果对材料腐蚀现状研究具有重要指导价值。

基于FC-tree的频繁闭项目集挖掘算法

目前提出的频繁项目集挖掘算法大多基于Apriori算法思想,但这类算法会产生巨大的候选集并且重复扫描数据库。本文针对这一问题,给出了一种基于FC-tree的频繁闭项目集挖掘算法Max-FCIA,该算法将频繁项目集存储在哈希表中,节省了程序的搜索时间。此外,利用广度优先搜索和有效的剪枝策略,大大限制了候选项目集的生成,缩小了搜索空间从而提高了程序的性能。实验结果表明该算法是快速有效的。

基于改进FP-tree的最大频繁项集挖掘算法

现有的最大频繁项集挖掘算法在挖掘过程中需要进行超集检测,基于FP-tree的算法需要递归的建立条件频繁模式树,挖掘效率不高。提出了一种基于改进FP-tree高效挖掘最大频繁项集的算法(MMFI)。该算法修改了FP-tree结构并采用NBN策略,在挖掘过程中既不需要进行超集检测也不需要递归的建立条件频繁模式树。算法分析和实验结果表明,该算法是一种有效、快速的算法。

基于改进的FP-tree最大频繁模式挖掘算法

针对FP-growth算法时空效率低的问题,提出了改进的FP-tree构造算法。该算法利用动态结点插入技术构造FP-tree,能有效减小模式树的宽度,达到压缩空间的目的;同时,该算法提高了前缀路径的共享性,提高了算法的效率。针对密集型数据的频繁模式完全集难以挖掘的问题,文中提出了IFPmax最大频繁模式挖掘算法,在改进的IFP-tree结构的基础上,利用结点的秩进行预判断,充分利用最大频繁模式的性质对已经存在的结点进行标记,有效避免了节点的冗余遍历,提高了最大频繁模式挖掘算法的效率。实验表明,在不同的基准数据集上文中提出的算法更有效,避免了节点的冗余遍历,使最大频繁模式挖掘算法效率更高。

滇金丝猴夜宿树的选择及夜宿地的利用方式

野生灵长类夜宿地的利用方式可以明确地反映一个物种特有的生境利用方式和生存之道。2003年12月至2004年10月,我们利用可自动脱落GPS无线电项圈对云南省丽江市金丝厂的一个滇金丝猴(Rhinopithecus bieti)群体的活动进行了持续跟踪记录。本研究着重于对所研究猴群夜宿树的选择和夜宿地的利用方式的考查,并结合可能影响夜宿地选择和利用的环境因素,比如天气、季节、日均温度等做了系统分析。研究群计有180余只个体,家域面积约27.8 km^(2)。GPS项圈记录到夜宿树的有272个夜晚,由此我们确认了131个夜宿地。其中70个(54.3%)夜宿地仅利用了一次,剩余的则不同程度地多次利用(2~9次)。在这些重复利用的夜宿地中,持续利用同一夜宿点的情形共发生了19次,其中连续3个夜晚在同一夜宿地过夜的现象出现了3次,剩下的16次是连续利用同一夜宿地2次。这种连续利用同一夜宿地的情况占重复利用同一夜宿的7.0%,发生频率不高,而且几乎都出现在冬季(84.0%)。滇金丝猴对于同一夜宿地的重复造访的时间间隔约50 d。一旦发生连续重复利用的情况,猴群当天的移动距离显著缩短(527 m vs.884 m),降低了群体移动所必需的能量消耗。明显地,滇金丝猴夜宿点的选择受其当天下午和第二天早上觅食点的位置的影响。鉴于较大的群体和明显回避夜宿地重复利用的特性,提示这是猴群对家域内食物分布的行为响应,避免对同一地点的过度利用造成食物的不足。采用大量(131个)而分散的夜宿地利用方式会保证猴群能够获得充足的食物供应。此外,相较于其他树种,滇金丝猴更喜欢在云南铁杉(Tsuga dumosa)树上过夜,而且尽量不以夜宿点作为觅食点,可能与卫生和安全有关。