¹School of Computer Science, National University of Defense Technology, Changsha 410073, China
²School of Computer and Communication, Hunan University of Technology, Zhuzhou 412008, China

---

Abstract—Multiple parallel transactions in new-type distributed software environment result in that the events produced by every transaction are randomly ranked. If the tokens of these events are incomplete or unavailable, it is difficult for software system to distinguish these events to actually belong to which transaction, corresponding transaction analysis and prediction can’t be executed. In this paper, the problem of stripping events with incomplete tokens is transferred into maximum-weight perfect matching of bigraph system. If the transition time among these events is independently and identically distributed, all possible states (events) are separated into multiple cutsets, every cutset composes a bigraph system. The maximumweight perfect matching is used to finish respective matching, and then the results of independent matching of multiple bigraph systems are spliced to gain the most possible footprint sequences produced by multiple transactions, which is convenient for subsequent analysis and prediction. For implementing quick stripping for transaction footprints, the paper presents rank-maximal matching algorithm to improve matching efficiency. Simulation experiment confirms that the method presented in this paper can effectively implement transaction footprint stripping with incomplete tokens. Compared to other methods, the rank-maximal matching algorithm has higher matching efficiency and lower time cost.

Index Terms—incomplete token, transaction footprint, bigraph matching, maximum-likelihood rule, rank-maximal matching

[PDF]

Cite: Changyun Li, Junfeng Man, and Zhibing Wang, "An Improved Method for Transaction Footprints Stripping with Bigraph System," Journal of Software vol. 7, no. 9, pp. 2141-2148, 2012.