The pivoted subgraph isomorphism problem is a special subgraph isomorphism problem that focuses on the pivoted nodes rather than the entire subgraphs. The key challenge in adapting existing techniques to the pivoted p...
详细信息
ISBN:
(纸本)9783031001239;9783031001222
The pivoted subgraph isomorphism problem is a special subgraph isomorphism problem that focuses on the pivoted nodes rather than the entire subgraphs. The key challenge in adapting existing techniques to the pivoted problem is eliminating their redundant intermediate results. In this paper, we propose a GPU-based pivoted subgraph isomorphism filtering technique, where information of each node is encoded into a series of codes. When performing a pivot subgraph search, the candidate nodes satisfying the coding requirements are collected parallelly on GPU while others are filtered away. Then the final result can be effectively retrieved by a verification process on the filtered nodes. As demonstrated by the experimental results, our method dramatically reduces the processing time of the pivoted subgraph isomorphism problem. Compared to the state-of-the-art GPU-friendly subgraph matching method GpSM which also focuses on filtering effect, the algorithm's execution time is halved, confirming that our approach can effectively process pivoted subgraph isomorphism queries.
We propose a length-flexible coding scheme by defining a balanced tree. For an arbitrary code length, we first construct a balanced binary tree (BBT) where the root node represents a transmitted codeword, the leaf nod...
详细信息
We propose a length-flexible coding scheme by defining a balanced tree. For an arbitrary code length, we first construct a balanced binary tree (BBT) where the root node represents a transmitted codeword, the leaf nodes represent either active bits or frozen bits, and a parent node is related to its child nodes by a length-adaptive $(U+V\mid V)$ operation. Both the encoding and the successive cancellation (SC)-based decoding can be implemented over the constructed coding tree. For code construction, we propose a signal-to-noise ratio (SNR)-dependent method and two SNR-independent methods, all of which evaluate the reliabilities of leaf nodes and then select the most reliable leaf nodes as the active nodes. Numerical results demonstrate that our proposed codes can have comparable performance to the 5G polar codes. To reduce the decoding latency, we propose a partitioned successive cancellation (PSC)-based decoding algorithm, which can be implemented over a sub-tree obtained by pruning the coding tree. Numerical results show that the PSC-based decoding can achieve similar performance to the conventional SC-based decoding.
In this paper, we give a classification of (finite or countable) No-categorical coloured linear orders, generalizing Rosenstein's characterization of N-0-categorical linear orderings. We show that they can all be ...
详细信息
In this paper, we give a classification of (finite or countable) No-categorical coloured linear orders, generalizing Rosenstein's characterization of N-0-categorical linear orderings. We show that they can all be built from coloured singletons by concatenation and Q(n)-combinations (for n >= 1). We give a method using coding trees to describe all structures in our list. (C) 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
XML data is widely used in the information exchange field of Internet, and XML document data clustering is the hot research topic. In the XML document clustering process, measure differences between two XML documents ...
详细信息
ISBN:
(纸本)9781510600294
XML data is widely used in the information exchange field of Internet, and XML document data clustering is the hot research topic. In the XML document clustering process, measure differences between two XML documents is time costly, and impact the efficiency of XML document clustering. This paper proposed an XML documents clustering method based on frequent patterns of XML document dataset, first proposed a coding tree structure for encoding the XML document, and translate frequent pattern mining from XML documents into frequent pattern mining from string. Further, using the cosine similarity calculation method and cohesive hierarchical clustering method for XML document dataset by frequent patterns. Because of frequent patterns are subsets of the original XML document data, so the time consumption of XML document similarity measure is reduced. The experiment runs on synthetic dataset and the real datasets, the experimental result shows that our method is efficient.
Current video coding standards like HEVC, VP9, VVC, AV1, etc., involve partitioning a picture into coding tree units (CTU), typically corresponding to 64x64 or 128x128 picture areas. Each CTU is partitioned into codin...
详细信息
ISBN:
(数字)9781510638273
ISBN:
(纸本)9781510638273
Current video coding standards like HEVC, VP9, VVC, AV1, etc., involve partitioning a picture into coding tree units (CTU), typically corresponding to 64x64 or 128x128 picture areas. Each CTU is partitioned into coding blocks following a recursive coding tree. In recently published perceptual video encoding methods, the CTU is used as the spatial unit to assign a QP value in a given picture area. Such an approach fits well with the usual rate distortion optimization used to decide the coding tree representation of a CTU since a constant QP is used inside the CTU. Thus Lagrangian rate distortion optimization works in such a situation. However, for some applications, finer spatial granularity may be desired with an adaptive QP. A perceptual video coding scheme may use a codec agnostic QP allocation process that proceeds on a 16x16 block basis. The issue raised in such a case is that the rate distortion trade-off among split modes no more works with the Lagrangian method. This paper proposes several methods to perform the rate distortion optimization of a coding tree in the situation where multiple QPs may be assigned inside the same CTU. First a theoretical method to solve the problem is described. It consists in a coding tree RD optimization using multiple Lagrange parameters. Then some simpler empirical methods which emulate the theoretical approach are proposed. Experimental results show the benefit of the proposed methods on top of VP9 and HEVC video encoders.
The recently introduced quadtreecoding structures used in HEVC increase compression efficiency in comparison to previous standards at the cost of higher computational complexity levels. This paper proposes an evoluti...
详细信息
ISBN:
(纸本)9781467325332;9781467325349
The recently introduced quadtreecoding structures used in HEVC increase compression efficiency in comparison to previous standards at the cost of higher computational complexity levels. This paper proposes an evolution of a complexity control method for HEVC encoders based on the dynamic adjustment of these structures' maximum depth. The new method improves the previous solution by adopting a new control strategy and compensating the motion effect on a maximum tree depth map which is central to the complexity control strategy. The proposed method is capable of performing a more accurate complexity control than our previous strategy while still reducing compression efficiency losses in terms of image quality and bit rate.
Analogues of Ramsey's Theorem for infinite structures such as the rationals or the Rado graph have been known for some time. In this context, one looks for optimal bounds, called degrees, for the number of colors ...
详细信息
Analogues of Ramsey's Theorem for infinite structures such as the rationals or the Rado graph have been known for some time. In this context, one looks for optimal bounds, called degrees, for the number of colors in an isomorphic substructure rather than one color, as that is often impossible. Such theorems for Henson graphs however remained elusive, due to lack of techniques for handling forbidden cliques. Building on the author's recent result for the triangle-free Henson graph, we prove that for each k >= 4, the k-clique-free Henson graph has finite big Ramsey degrees, the appropriate analogue of Ramsey's Theorem. We develop a method for coding copies of Henson graphs into a new class of trees, called strong coding trees, and prove Ramsey theorems for these trees which are applied to deduce finite big Ramsey degrees. The approach here provides a general methodology opening further study of big Ramsey degrees for ultrahomogeneous structures. The results have bearing on topological dynamics via work of Kechris, Pestov, and Todorcevic and of Zucker.
暂无评论