XML过滤中缓存失效策略的性能分析数学模型

硬件缓存行为是内存驻留的数据密集型系统(例如XML过滤机制)的一个重要特征.目前对XML的过滤方式的主流研究都是用自动机来表达主存中长期运行的XML查询.现主要通过分析性的建模和系统度量来研究基于自动机的XML过滤的cache性能,将原本笼统地针对整个cache失效性的分析细化成建立cache圈内模型和跨圈模型来估计cache的失效率,并通过实验证明该评估机制具有较高的精确度.     

A Semantic Cache Framework for Secure XML Queries

Secure XML query answering to protect data privacy and semantic cache to speed up XML query answering are two hot spots in current research areas of XML database systems. While both issues are explored respectively in depth,they have not been studied together,that is,the problem of semantic cache for secure XML query answering has not been addressed yet. In this paper,we present an interesting joint of these two aspects and propose an efficient framework of semantic cache for secure XML query answering,which can improve the performance of XML database systems under secure circumstances. Our framework combines access control,user privilege management over XML data and the state-of-the-art semantic XML query cache techniques,to ensure that data are presented only to authorized users in an efficient way. To the best of our knowledge,the approach we propose here is among the first beneficial efforts in a novel perspective of combining caching and security for XML database to improve system performance. The efficiency of our framework is verified by comprehensive experiments.     

一种支持大页的层次化DRAMNVM混合内存系统

随着大数据应用的涌现,计算机系统需要更大容量的内存以满足大数据处理的高时效性需求.新型非易失性存储器(non-volatile memory,NVM)结合传统动态随机存储器(dynamic random access memory, DRAM)组成的混合内存系统具有内存容量大、功耗低的优势,因而得到了广泛关注.大数据应用同时也面临着旁路转换缓冲器(translation lookaside buffer, TLB)缺失率过高的性能瓶颈.大页可以有效降低TLB缺失率,然而,在混合内存中支持大页面临着大页迁移开销过大的问题.因此,设计了一种支持大页和大容量缓存的层次化混合内存系统：DRAM和NVM分别使用4KB和2MB粒度的页面分别进行管理,同时在DRAM和NVM之间实现直接映射.设计了基于访存频率的DRAM缓存数据过滤机制,减轻了带宽压力.提出了基于内存实时信息的动态热度阈值调整策略,灵活适应应用访存特征的变化.实验显示：与使用大页的全NVM内存系统和缓存热页(caching hot page, CHOP)系统相比平均有69.9%和15.2%的性能提升,而与使用大页的全DRAM内存系统相比平均只有8.8%的性能差距.     

Schema-aware XPath filtering on XML document streams

The XML stream filtering is gaining widespread attention from the research community in recent years. There have been many efforts to improve the performance of the XML filtering system by utilizing XML schema information. In this paper, we design and implement an XML stream filtering system, SFilter, which uses DTD or XML schema information for improving the performance. We propose the simplification and two kinds of optimization, one is static and the other is dynamic optimization. The Simplification and static optimization transform the XPath queries to make automata as an index structure for the filtering. The dynamic optimization are done in runtime at the filtering time. We developed five kinds of static optimization and two kinds of dynamic optimization. We present the novel filtering algorithm for the resulting transformed XPath queries and runtime optimizing. The experimental result shows that our system filters the XML streams efficiently.     

支持StAX的高效XML解析器的设计与实现

StAX是JCP提出的一种新的XML解析方式，它提供给用户更多的解析控制权。本文给出了用于XML语法分析的下推自动机模型的设计以及StAX解析器OnceStAXParser的实现。OnceStAXParser在经过了严格的XML兼容性测试和StAXAPI兼容性测试之后，还从多个方面进行了性能优化，包括自动机实现优化、有计划的预分配和延迟处理策略以及适度封装策略等。性能测试数据表明，OnceStAXParser的吞吐量比SunSJSXP平均高5％，比BEAStAXRI平均高38％。     

高效XML验证技术的实现

XML解析器是分析、处理XML文档的基础软件.对XML解析器的高效验证技术进行了研究,实现了支持StAX接口的验证型解析器OnceStAXParser2.0.该解析器采用了多项性能优化措施,包括属性验证的高效实现、元素验证自动机的优化、基于统计的预测算法等.性能测试表明,在进行验证的条件下,OnceStAXParser2.0具有出色的解析性能.     

基于有限自动机的XML过滤技术研究综述

介绍了基于有限自动机的XML过滤技术的研究现状,依据自动机的特点进行分类,分析了其中几种典型算法,并对XML过滤算法的优缺点进行了深入讨论和比较.     

基于自动机XML正则路径表达式查询研究

基于自动机正则路径表达式查询技术是半结构化数据模式下XML查询研究领域颇有价值的方法。许多研究方法对含有“//”操作符和“*”通配符复杂正则路径重写都会产生大量中间路径。设计了处理XML正则路径查询高效方法——CSAS,利用对象交换模型(OEM)作为XML数据模型,有限自动机作为查询模型,提出裁剪XMLSchema转化的自动机片断作为重写自动机来重写“//”和“*”符号的重写技术;利用剪枝技术、谓词处理后移策略实现查询优化。实验证明,CSAS方法是一种高效的XML正则路径表达式查询方法。     

基于语义贡献值的XML查询缓存替换策略

传统缓存替换策略对语义缓存替换缺乏针对性,不能有效重用缓存中的数据,影响缓存命中率。为此,针对可扩展标记语言查询(XML)代数查询的特点,提出一种基于语义贡献值的XML查询缓存替换策略,根据用户历史查询的缓存项进行聚类分析,预测其对未来查询的语义贡献值,当缓存空间不足时替换语义贡献值最小的项,从而提高用户查询效率。实验结果表明,相比最不经常使用策略和最近最少使用策略,该策略能有效缩短查询时间,提高缓存命中率。     

Scalable Filtering of Multiple Generalized-Tree-Pattern Queries over XML Streams

An XML publish/subscribe system needs to filter a large number of queries over XML streams. Most existing systems only consider filtering the simple XPath statements. In this paper, we focus on filtering of the more complex Generalized-Tree-Pattern (GTP) queries. Our filtering mechanism is based on a novel Tree-of-Path (TOP) encoding scheme, which compactly represents the path matches for the entire document. First, we show that the TOP encodings can be efficiently produced via a shared bottom-up path matching. Second, with the aid of this TOP encoding, we can 1) achieve polynomial time and space complexity for post processing, 2) avoid redundant predicate evaluations, 3) allow an efficient duplicate-free and merge join-based algorithm for merging multiple encoded path matches and 4) simplify the processing of GTP queries. Overall our approach maximizes the sharing opportunity across queries by exploiting the suffix as well as prefix sharing. At the same time, our TOP encodings allow efficient post processing for GTP queries. Extensive performance studies show that our GFilter solution not only achieves significantly better filtering performance than state-of-the-art algorithms, but also is capable of efficiently filtering the more complex GTP queries.     

Path and cache conscious prefetching (PCCP)

Main memory cache performance continues to play an important role in determining the overall performance of object-oriented, object-relational and XML databases. An effective method of improving main memory cache performance is to prefetch or pre-load pages in advance to their usage, in anticipation of main memory cache misses. In this paper we describe a framework for creating prefetching algorithms with the novel features of path and cache consciousness. Path consciousness refers to the use of short sequences of object references at key points in the reference trace to identify paths of navigation. Cache consciousness refers to the use of historical page access knowledge to guess which pages are likely to be main memory cache resident most of the time and then assumes these pages do not exist in the context of prefetching. We have conducted a number of experiments comparing our approach against four highly competitive prefetching algorithms. The results shows our approach outperforms existing prefetching techniques in some situations while performing worse in others. We provide guidelines as to when our algorithm should be used and when others maybe more desirable.     

高性能的XML解析器OnceXMLParser

XML(extensible markup language)解析器是分析、处理XML文档的基础软件.研究高性能验证型XML解析器的实现.开发了支持3种解析模型的XML解析器OnceXMLParser,该解析器通过了严格的XML兼容性测试和API兼容性测试.OnceXMLParser具有轻量级体系结构并进行了多方面的性能优化,包括高效的词法分析、基于统计分析的自动机实现、合理的资源分配策略以及语言层次上的优化.性能测试结果表明,OnceXMLParser具有出色的解析性能.     

Decision-cache based XACML authorisation and anonymisation for XML documents

This paper describes a decision cache for the eXtensible Access Control Markup Language (XACML) that supports fine-grained authorisation and anonymisation of XML based messages and documents down to XML attribute and element level. The decision cache is implemented as an XACML obligation service, where a specification of the XML elements to be authorised and anonymised is sent to the Policy Enforcement Point (PEP) during initial authorisation. Further authorisation of individual XML elements according to the authorisation specification is then performed on all matching XML resources, and decisions are stored in the decision cache. This makes it possible to cache fine-grained XACML authorisation and anonymisation decisions, which reduces the authorisation load on the Policy Decision Point (PDP). The theoretical solution is related to a practical case study consisting of a privacy-enhanced intrusion detection system that needs to perform anonymisation of Intrusion Detection Message Exchange Format (IDMEF) XML messages before they are sent to a security operations centre that operates in privacy-preserving mode. The solution increases the scalability of XACML based authorisation significantly, and may be instrumental in implementing federated authorisation and anonymisation based on XACML in several areas, including intrusion detection systems, web services, content management systems and GRID based authentication and authorisation.     

Decision-cache based XACML authorisation and anonymisation for XML documents

This paper describes a decision cache for the eXtensible Access Control Markup Language (XACML) that supports fine-grained authorisation and anonymisation of XML based messages and documents down to XML attribute and element level. The decision cache is implemented as an XACML obligation service, where a specification of the XML elements to be authorised and anonymised is sent to the Policy Enforcement Point (PEP) during initial authorisation. Further authorisation of individual XML elements according to the authorisation specification is then performed on all matching XML resources, and decisions are stored in the decision cache. This makes it possible to cache fine-grained XACML authorisation and anonymisation decisions, which reduces the authorisation load on the Policy Decision Point (PDP). The theoretical solution is related to a practical case study consisting of a privacy-enhanced intrusion detection system that needs to perform anonymisation of Intrusion Detection Message Exchange Format (IDMEF) XML messages before they are sent to a security operations centre that operates in privacy-preserving mode. The solution increases the scalability of XACML based authorisation significantly, and may be instrumental in implementing federated authorisation and anonymisation based on XACML in several areas, including intrusion detection systems, web services, content management systems and GRID based authentication and authorisation.     

Discrete-event modeling of multi-agent systems with broadcasting-based parallel composition

Multi-agent systems have been widely used in logistics and manufacturing. In this paper we develop an automaton-based modeling framework for a special type of multi-agent systems, where agents are instantiated from a finite number of finite-state automaton templates, and interactions among agents are characterized via cooperative synchronization and broadcasting. To describe the compositional behavior of all agents, we propose a novel broadcasting-based parallel composition rule and show that it is commutative and associative. The effectiveness of this modeling framework and the parallel composition rule is illustrated in a simple multi-agent system.     

A survey on XML streaming evaluation techniques

XML is currently the most popular format for exchanging and representing data on the web. It is used in various applications and for different types of data including structured, semistructured, and unstructured heterogeneous data types. During the period, XML was establishing itself, data streaming applications have gained increased attention and importance. Because of these developments, the querying and efficient processing of XML streams has became a central issue. In this study, we survey the state of the art in XML streaming evaluation techniques. We focus on both the streaming evaluation of XPath expressions and of XQuery queries. We classify the XPath streaming evaluation approaches according to the main data structure used for the evaluation into three categories: automaton-based approach, array-based approach, and stack-based approach. We review, analyze, and compare the major techniques proposed for each approach. We also review multiple query streaming evaluation techniques. For the XQuery streaming evaluation problem, we identify and discuss four processing paradigms adopted by the existing XQuery stream query engines: the transducer-based paradigm, the algebra-based paradigm, the automata-algebra paradigm, and the pull-based paradigm. In addition, we review optimization techniques for XQuery streaming evaluation. We address the problem of optimizing XQuery streaming evaluation as a buffer optimization problem. For all techniques discussed, we describe the research issues and the proposed algorithms and we compare them with other relevant suggested techniques.     

基于J2EE与XML的Web打印系统

提出一种Web打印系统的设计思想,该系统综合运用XML与J2EE技术,设计可重复调用的打印包,为打印配置信息设计XML描述,采用缓存和存储过程有效提高系统的性能.     

基于XML扩展语法的模式分类研究

XML正在迅速成为WWW上采用的信息交换、表示和存储手段之一,论文对XML文档进行了多层次的抽象,得出了扩展XML语法和自动机等概念。作为一个应用,论文利用这一抽象对W3C推荐的两种最通用的模式进行上述语法观点的分类,从而有利于在不同的应用中选取合适的模式。     

一种Active XML模式重写算法

基于树自动机理论,研究了Active xML(简记为AXML)模式重写问题,提出了一种多项式时间的AXML模式重写判定算法,并对算法进行了实现.实验结果证明了所提算法用于判定AXML模式重写的优越性.     

信息中心网络内缓存替换算法性能分析与优化

信息中心网络(information centric networking, ICN)是一类受到广泛关注的新型互联网体系结构.通过对网络内(in-network)缓存的充分利用,信息中心网络可以极大地增强内容分发效率.网络内缓存的管理机制一直是信息中心网络研究中的热点问题.分析了网络内缓存的基准缓存替换最近最少使用(least recently used, LRU)算法的性能,指出多跳LRU缓存中广泛存在的“缓存退化”问题：在首个缓存节点发生缺失的内容请求也很难被下游的缓存命中.针对这一问题,提出一种基于预过滤的O(1)复杂度的改进算法.在原有缓存前放置一个仅记录内容标识的预过滤缓存,完成对原始内容请求的整形,使得预处理后的请求流量可以更容易被后面几跳缓存命中.基于真实互联网拓扑的实验表明,在信息中心网络典型应用场景下,预过滤LRU的缓存命中率可以达到LRU的2～3倍.