Xia M.,CAS Institute of Software
Proceedings of the Annual ACM Symposium on Theory of Computing | Year: 2016
A holographic algorithm solves a problem in a domain of size n, by reducing it to counting perfect matchings in planar graphs. It may simulate a n-value variable by a bunch of t matchgate bits, which has 2t values. The transformation in the simulation can be expressed as a n × 2t matrix M, called the base of the holographic algorithm. We wonder whether more matchgate bits bring us more powerful holographic algorithms. In another word, whether we can solve the same original problem, with a collapsed base of size n × 2r, where r < t. Base collapse is discovered for small domain n = 2,3,4. For n = 3,4, the base collapse is proved under the condition that there is a full rank generator. We prove for any n, the base collapse to a r ≤ [log n], under some similar conditions. One of the conditions is that the original problem is defined by one symmetric function. In the proof, we utilize elementary matchgate transformations instead of matchgate identities. © 2016 ACM.
Ding Z.-M.,CAS Institute of Software
Jisuanji Xuebao/Chinese Journal of Computers | Year: 2012
Index is a key technology to improve the query processing performance of moving objects databases. However, current index methods for moving object trajectories, such as STR-Tree, TB-Tree, FNR-Tree, and MON-Tree, take trajectory units as the basic index records, and therefore, frequent insertions are needed when location updates occur in order to keep the consistency between the index and the trajectories in database, which greatly affects the overall performance of moving objects databases. To solve this problem, we propose a new index method, Dynamic Sketched-Trajectory R-Tree for Network-constrained Moving Objects (DSTR-Tree) in this paper. The DSTR-Tree divides the spatial-temporal space into equal-sized grid cells, transforms every trajectory into a sketched trajectory with each unit connecting two centers of the grid cells that the moving object travels through, and indices the sketched trajectory units as an R-Tree. Since the sketched trajectory has much coarser granularity than the original trajectory, the index updating cost can be greatly reduced - when a location update occurs, even though the original trajectory needs to be changed, the sketched trajectory may remain unchanged so that the DSTR-Tree does not need to be changed either. The experimental results show that the DSTR-Tree outperforms the previously proposed trajectory index methods in running moving objects databases with frequent location updates.
Sun Z.,CAS Institute of Automation |
Zhang H.,CAS Institute of Software |
Tan T.,CAS Institute of Automation |
Wang J.,CAS Shanghai Institute of Technical Physics
IEEE Transactions on Pattern Analysis and Machine Intelligence | Year: 2014
Iris recognition as a reliable method for personal identification has been well-studied with the objective to assign the class label of each iris image to a unique subject. In contrast, iris image classification aims to classify an iris image to an application specific category, e.g., iris liveness detection (classification of genuine and fake iris images), race classification (e.g., classification of iris images of Asian and non-Asian subjects), coarse-to-fine iris identification (classification of all iris images in the central database into multiple categories). This paper proposes a general framework for iris image classification based on texture analysis. A novel texture pattern representation method called Hierarchical Visual Codebook (HVC) is proposed to encode the texture primitives of iris images. The proposed HVC method is an integration of two existing Bag-of-Words models, namely Vocabulary Tree (VT), and Locality-constrained Linear Coding (LLC). The HVC adopts a coarse-to-fine visual coding strategy and takes advantages of both VT and LLC for accurate and sparse representation of iris texture. Extensive experimental results demonstrate that the proposed iris image classification method achieves state-of-the-art performance for iris liveness detection, race classification, and coarse-to-fine iris identification. A comprehensive fake iris image database simulating four types of iris spoof attacks is developed as the benchmark for research of iris liveness detection. © 2013 IEEE.
Liao Q.,IBM |
Shi L.,CAS Institute of Software
Proceedings of the ACM Conference on Computer Supported Cooperative Work, CSCW | Year: 2013
In this paper we report on a case study of rumor transmission during a nationwide scandal via China's most popular microblogging service, weibo.com. Specifically, we explore dynamics of the rumor discourse by characterizing different statement types and their evolution over time. We examine the roles that different user groups play in the rumor discussions. Through qualitative and statistical analyses, our results identify seven reaction patterns to rumors and their different development trends. We reveal a three-stage pattern of the change of leadership during the rumor discussions. By connecting social theories on rumor transmission to the large scale social platform, this paper offers insight into understanding rumor development in social media, as well as utilizing microblogging data for effectively detecting, analyzing and controlling public rumors. Copyright 2013 ACM.
Shen Y.-D.,CAS Institute of Software
IJCAI International Joint Conference on Artificial Intelligence | Year: 2011
[Fages, 1994] introduces the notion of well-supportedness as a key requirement for the semantics of normal logic programs and characterizes the standard answer set semantics in terms of the well-supportedness condition. With the property of well-supportedness, answer sets are guaranteed to be free of circular justifications. In this paper, we extend Fages' work to description logic programs (or DL-programs). We introduce two forms of well-supportedness for DL-programs. The first one defines weakly well-supported models that are free of circular justifications caused by positive literals in rule bodies. The second one defines strongly well-supported models that are free of circular justifications caused by either positive or negative literals. We then define two new answer set semantics for DL-programs and characterize them in terms of the weakly and strongly well-supported models, respectively. The first semantics is based on an extended Gelfond-Lifschitz transformation and defines weakly well-supported answer sets that are free of circular justifications for the class of DL-programs without negative dlatoms. The second semantics defines strongly wellsupported answer sets which are free of circular justifications for all DL-programs. We show that the existing answer set semantics for DL-programs, such as the weak answer set semantics, the strong answer set semantics, and the FLP-based answer set semantics, satisfy neither the weak nor the strong well-supportedness condition, even for DL-programs without negative dl-atoms. This explains why their answer sets incur circular justifications.