Querying business processes with BP-QL

We present in this paper BP-QL, a novel query language for querying business processes. The BP-QL language is based on an intuitive model of business processes, an abstraction of the emerging BPEL (business process execution language) standard. It allows users to query business processes visually, in a manner very analogous to how such processes are typically specified, and can be employed in a distributed setting, where process components may be provided by distinct providers.     

Zoned-partitioning of tree-like access methods

The performance of access methods and the underlying disk system is a significant factor in determining the performance of database applications, especially with large sets of data. While modern hard disks are manufactured with multiple physical zones, where seek times and data transfer rates vary significantly across the zones, there has been little consideration of this important disk characteristic in designing access methods (indexing schemes). Instead, conventional access methods have been developed based on a traditional disk model that comes with many simplifying assumptions such as an average seek time and a single data transfer rate. The paper proposes novel partitioning techniques that can be applied to any tree-like access methods, both dynamic and static, fully utilizing zoning characteristics of hard disks. The index pages are allocated to disk zones in such a way that more frequently accessed index pages are stored in a faster disk zone. On top of the zoned data placement, a localized query processing technique is proposed to significantly improve the query performance by reducing page retrieval times from the hard disk.     

Fault tolerant multiple event detection in a wireless sensor network

With an increasing acceptance of Wireless Sensor Networks (WSNs), the health of individual sensor is becoming critical in identifying important events in the region of interest. One of the key challenges in detecting event in a WSN is how to detect it accurately transmitting minimum information providing sufficient details about the event. At the same time, it is also important to devise a strategy to handle multiple events occurring simultaneously. In this paper, we propose a Polynomial-based scheme that addresses these problems of Event Region Detection (PERD) by having a aggregation tree of sensor nodes. We employ a data aggregation scheme, TREG (proposed in our earlier work) to perform function approximation of the event using a multivariate polynomial regression. Only coefficients of the polynomial (P$P$) are passed instead of aggregated data. PERD includes two components: event recognition and event report with boundary detection. This can be performed for multiple simultaneously occurring events. We also identify faulty sensor(s) using the aggregation tree. Performing further mathematical operations on the calculated P$P$ can identify the maximum (max) and minimum (min) values of the sensed attribute and their locations. Therefore, if any sensor reports a data value outside the [min, max] range, it can be identified as a faulty sensor. Since PERD is implemented over a polynomial tree on a WSN in a distributed manner, it is easily scalable and computation overhead is marginal. Results reveal that event(s) can be detected by PERD with error in detection remaining almost constant achieving a percentage error within a threshold of 10%$10\%$ with increase in communication range. Results also show that a faulty sensor can be detected with an average accuracy of 94%$94\%$ and it increases with increase in node density.     

基于自动机理论的XML查询重写研究

研究了基于自动机理论的XML查询重写问题,尤其针对局部查询重写技术作了深入研究.通过实例对其有效性进行了合理的分析.     

基于Web的达梦数据库交互式查询工具的实现

本系统主要功能：对用户输入的单句或多句SQL语句进行处理,及时返回查询结果或者操作信息。本系统具有以下特点：采用主流的Web设计语言JSP设计客户端界面,用JDBC实现对数据库的无缝连接;使用JDBC扩展包中的行集来缓存结果集;使用javacc工具自动生成语法分析器;这些后台操作大部分采用了JavaBeans进行封装。     

Communication contention in APN list scheduling algorithm

Task scheduling is an essential aspect of parallel process system. This NP-hard problem assumes fully connected homogeneous processors and ignores contention on the communication links. However, as arbitrary processor network (APN), communication contention has a strong influence on the execution time of a parallel application. This paper investigates the incorporation of contention awareness into task scheduling. The innovation is the idea of dynamically scheduling edges to links, for which we use the earliest finish communication time search algorithm based on shortest-path search method. The other novel idea proposed in this paper is scheduling priority based on recursive rank computation on heterogeneous arbitrary processor network. In the end, to reduce time complexity of algorithm, a parallel algorithm is proposed and speedup O(PPE) is achieved. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithm significantly surpasses classic and static communication contention awareness algorithm, especially for high data transmission rate parallel application. Supported by the National Natural Science Foundation of China (Grant Nos. 90715029 and 60603053), the Cultivation Fund of the Key Scientific and Technical Innovation Project, Ministry of Edacation of China, and the Key Project of Science & Technology of Hunan Province (Grant No. 2006GK2006)     

基于完全加权关联规则挖掘和查询扩展的信息检索

将完全加权关联规则挖掘技术应用于信息检索,提出一种基于完全加权关联规则挖掘和查询扩展的信息检索模型,重点阐述模型的设计思想及其算法和实现的关键技术.实验结果表明,该模型有效,能提高信息检索性能,有很高的实际应用价值和推广前景.     

基于概念图的信息检索的查询扩展模型

针对传统的基于关键词匹配的信息检索存在的查全率和精确率不高的问题,提出一种基于概念图匹配的查询扩展方法：一方面通过知网对用户查询的词或者句子进行扩展后,将用户查询和文档生成概念图;另一方面利用概念图的不完全匹配和语义相似度的计算方法计算概念图的相似度,以提高检索效果。实验结果表明该方法取得了良好的效果。     

多媒体查询语言及其评价准则

随着多媒体技术和多媒体相关应用的发展,对有效检索多媒体信息的要求越来越迫切.查询语言作为信息检索的有效工具,其研究也越来越受到关注.对现有的多媒体查询语言进行了全面的综述,将它们分为两类:专用语言和通用语言.尽管查询语言对多媒体信息系统提供有效的查询服务至关重要,但目前仍没有较好的多媒体查询语言评价准则.因此,针对多媒体查询语言的查询表达能力设计准则共16条,并根据这些准则对多媒体查询语言进行了评价.评价结果表明,这些语言能满足用户的基本查询要求,但在高级语义查询和不确定查询等方面还有欠缺.最后展望了多媒体查询语言的未来研究方向.     

On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.