数据流中结构二叉树挖掘算法研究

针对传统数据流挖掘算法不能挖掘出频繁项之间的关系而且挖掘时间和空间复杂度高、准确度不高的问题,本文提出了一种数据流中结构二叉树挖掘算法（AMST）。该算法利用了二叉树结构的优势,将所处理事务数据库中的数据流转化成结构化二叉树,然后利用数据流矩阵对结构二叉树进行挖掘。整个过程只对事务数据库进行了一次扫描,大大提高了挖掘的效率。此外,算法还找出了具有层次关系的频繁子树。实验结果表明,AMST算法性能稳定,在时间复杂度和空间复杂度方面有很大的优越性,能够快速准确地对数据流进行挖掘。     

A memoryless binary query tree based Successive Scheme for passive RFID tag collision resolution

The deployments of RFID system are seriously affected by collision caused by multiple tags responding simultaneously. To facilitate the resolution of collisions caused by densely distributed memoryless passive tags in successive cycles, based on the binary query tree protocol, this paper proposes a new Successive Scheme. In this scheme, the binary query tree constructed by the protocol will be reused. In the subsequent cycle, only the successful or idle binary query strings in the tree are adopted directly as the initial binary query strings, and these collision query strings in the tree are skipped. Due to the dynamic entrance and departure of tags, new nodes will be added to and abundant nodes will be removed from the tree. The performance of this Successive Scheme will be analyzed theoretically and examined with numeric simulations. Results indicate that in almost all cases, the Successive Scheme outperforms the commonly used binary query tree protocols in terms of system efficiency, message complexity, time, and time system efficiency. Especially when the tags stay stable, the system efficiency of the scheme is improved to 69.2%. Besides, simulation results also reveal that the scheme can deal efficiently with the case that the binary tag identifiers are in biased distribution.