基于层次有序维的分组聚集算法

在联机分析处理(OLAP)中,有效地维度模型对海量数据的即席复杂分组聚集查询起着关键的作用.在偏序和映射的基础上,通过定义层次有序维,提出一种基于层次有序维的分组聚集算法.该算法利用维属性之间的聚集关系,通过约束层次链中的元素次序,实现了分组聚集计算中多表连接转换为维范围的查询,提高了连接和聚集效率.最后,实验结果验证了该算法的有效性.     

联机分析处理中的非规则维建模

预聚集技术通过预先计算并保存原始数据上的查询结果以实现联机分析处理系统的快速查询响应能力．然而,在实际应用中,许多非规则维的结构难以使用传统多维模型进行建模,从而影响了预聚集技术的使用．为此,基于子级别到父级别的部分映射定义级别之间的部分序关系,进而提出了一个支持非覆盖、非映上等非规则雏中维级别关系建模的维模型．同时,在维模型基础上,定义了支持非规则维的立方体模型以及典型的联机分析处理操作．多维模型与关系模式的转换定义和实例分析证明了该多维模型可以实现对各种非规则维的建模支持,保证了预聚集技术在联机分析处理中的使用．     

支持非覆盖维的扩展多维数据模型

非覆盖维等复杂结构维的处理一直都是数据仓库领域的难题,本文在详细分析非覆盖维特性的基础上,提出了一个扩展的多维数据模型,改变了传统的级别间的映射关系的定义方式,定义了从父级别到子级别分区的映射关系,从而实现了对非覆盖维和非平衡维的支持,并能够完整地表达各种复杂维层次结构语义.同时,基于DAG图描述的维层次结构,定义了基于该多维模型的立方体代数和OLAP操作.将多维数据库概念模型中的维与度量的转换操作引入到OLAP操作集合中,使其支持复杂维的转化操作,进而丰富和增强基于该模型的OLAP系统的分析能力.     

数据仓库中维的建模和查询

维是数据仓库的重要组成部分，也是OLAP的主要查询对象，但标准的星形／雪花模型对实际应用中维的建模存在明显缺陷，而且SQL语言对维实体、维层次结构不能提供直接、有效的支持，使得OLAP查询的表达较为繁琐、冗长。为此，提出了一个基于关系数据库的SQL（D）数据模型，它给出了层次链、层次树、维的正式定义，支持不平衡、异构的维层次结构；并对SQL作了相应的扩充，支持维的定义、维层次比较、维的引用和维聚集层次的指定，使得原先冗长、复杂的OLAP查询表达式变得简洁、易于理解。最后对扩充的语义给出实现算法。     

支持OO查询物理优化的二维字典签名方法

提出支持面向对象查询物理优化的二维字典签名方法.首先提出其基本设计思想,在定义二维 字典及其数据结构之后,给出了二维字典签名的构造算法及其查询操作算法,最后构造了存储 开销和查询代价模型.     

一种基于维层次聚集树的Cube增量更新算法

提出利用Cube中的维层次聚集树（dimension hierarchy aggregate tree,简称DHA-Tree）来对聚集Cube进行增量更新维护,在维层次聚集Cube中进行数据插入和删除等数据更新时,充分利用维层次聚集树中的维层次前缀,由下向上用更新前后的差值对受到更新结点影响的所有祖先结点进行增量更新.在插入新维数据时,在不需要重新构建聚集Cube就可以对聚集Cube进行增量更新,从而减少了Cube的更新时间.对基于维层次聚集树的聚集Cube与传统Cube进行了算法性能分析和比较,结果表明本文所提出的聚集Cube的增量更新算法性能最佳.     

改进的二维典型相关分析及其人脸识别应用

针对二维典型相关分析(2DCCA)中类标矩阵维数较大及算法耗时过多的问题,提出一种改进的2DCCA特征提取方法。利用图像的频谱性质定义低维的类标矩阵,从有利于模式分类的角度构造出新的准则函数,采用二维主成分分析对所得特征进一步降维,得到更具分类判别能力的低维特征。在ORL和组合人脸数据库上的实验结果表明,该特征具有较好的分类能力。     

半监督的局部保留投影降维方法

针对现有数据降维算法不能同时利用标记样本和无标记样本的问题,提出一种半监督局部保留投影降维方法。定义类间相似度和类内相似度,同时最大化类间分离度、最小化类内分离度,保持样本总体结构和局部结构,从而提高数据降维的效果。在人工数据集、UCI数据库和Olivetti人脸库中的测试结果表明,该方法的识别率较高。     

半监督的稀疏保持二维边界Fisher分析降维算法

针对样本集中类别标签样本不足的问题,提出一种半监督的稀疏保持二维边界fisher分析降维算法.首先利用图像像素间的空间结构信息,基于图像矩阵进行降维;然后设计类内散度矩阵和类间散度矩阵,以保持样本间的类内紧凑性和类间分离性;最后通过稀疏保持对特征间的稀疏重构性加以约束,所获得的稀疏重构权重保持了局部几何结构,而且也包含了自然鉴别信息.在YALE,ORL和AR人脸数据库上的实验结果表明,该算法具有很好的分类和识别性能.     

图像分形维数计算方法的比较

分形维数是度量图像纹理粗糙度的一种常用方法,而依据分形维数的定义很难求解图像的分形维数。大量计算图像分形维数的算法被提出,但是这些方法往往基于不同的应用背景,没有总体比较和评价,多局限于差分盒子维的选用和改进,算法普遍存在计算误差较大,适应能力模糊的缺点。基于目前常用图像分形维数的计算方法,测试不同方法对图像粗糙度的敏感程度和时间复杂程度。从而对这些方法的适用范围进行分析和比较,给出应用的推荐模型。     

多维数据模型中维层次结构的自动生成算法及其实现

多维数据模型是数据仓库及联机分析处理的核心,目前主要有两种:星型模型和雪花模型。维层次结构是多维数据模型最重要的概念之一。该文提出了一个算法,它能够在雪花模型中根据维表间的依赖关系构造维的层次结构。指出使用该算法的前提并进行了证明,随后实现了算法。文章最后提出了在星型模型中构造维的层次结构的基本过程。     

维上带层次数据立方的自底向上计算

通过扩展 BUC算法 ,提出了 HBUC算法 ,自底向上地计算维上带层次的数据立方 .HBU C算法的关键在于对层次之间的映像关系进行了合理地编码 ,并选择了恰当的层次扫描路线 ,这些不仅能够保证 HBU C算法继承和扩展BUC算法的优化过程 :Write- Ancestors和 Collapsing,而且使粗粒度级的聚集计算因为共享细粒度级的排序结果而得到加速 ,从而大大提高了 HBUC的计算效率 .     

Conceptual entropy and its effect on class hierarchies

All systems that undergo frequent change characteristically tend toward disorder. This is known as entropy and is recognized in all branches of science. Class hierarchies are shared structures which, if useful, undergo frequent change in the form of additional subclassing, modification to existing classes, and sometimes the restructuring of the hierarchy itself. Given this frequent change, we can expect class hierarchies to exhibit entropic tendencies, which we term conceptual entropy. Conceptual entropy is manifested by increasing conceptual inconsistency as we travel down the hierarchy. That is, the deeper the level of the hierarchy, the greater the probability that a subclass will not consistently extend and/or specialize the concept of its superclass. Constructing and maintaining consistent class hierarchies is one of the most difficult activities of object-oriented design. The article describes an automated classification tool that helps minimize conceptual entropy     

Java Native Interface idioms for C++ class hierarchies

The Java^TM Native Interface (JNI) provides a set of mechanisms for implementing Java methods in C or C++. JNI is useful for reusing C and C++ code repositories within Java frameworks. JNI is also useful for real‐time systems, where compiled C/C++ code executes performance‐critical tasks, while Java code executes system control and feature tasks. Available JNI literature concentrates on creating Java proxy classes that allow Java clients to interact with C++ classes. Current JNI literature does not discuss Java proxies for entire C++ inheritance hierarchies; that is the topic of this paper. Our experience in reusing C++ class hierarchies within a Java framework has uncovered a set of useful techniques for constructing Java proxy class hierarchies that mirror their C++ counterparts. This report gives both high level design guidelines and specific programming idioms for constructing Java class hierarchies that serve as proxies for C++ counterparts. We begin by discussing opportunities for reuse within a proxy class hierarchy, as well as problems caused by differences between the Java and C++ approaches to inheritance. The two most significant differences are due to C++ support for invocation of a member function based on the static type of its class, and C++ support for multiple implementation inheritance. Two example C++ class hierarchies provide the basis for a set of sections that present the design guidelines and that codify the programming idioms. This work could serve as the basis for an automatic generator of Java proxy class hierarchies. Copyright © 2000 John Wiley & Sons, Ltd.     

Lazy behavioral subtyping

Inheritance combined with late binding allows flexible code reuse but complicates formal reasoning significantly, as a method call’s receiver class is not statically known. This is especially true when programs are incrementally developed by extending class hierarchies. This paper develops a novel method to reason about late bound method calls. In contrast to traditional behavioral subtyping, reverification of method specifications is avoided without restricting method overriding to fully behavior-preserving redefinition. The approach ensures that when analyzing the methods of a class, it suffices to consider that class and its superclasses. Thus, the full class hierarchy is not needed, and incremental reasoning is supported. We formalize this approach as a calculus which lazily imposes context-dependent subtyping constraints on method definitions. The calculus ensures that all method specifications required by late bound calls remain satisfied when new classes extend a class hierarchy. The calculus does not depend on a specific program logic, but the examples in the paper use a Hoare style proof system. We show soundness of the analysis method. The paper finally demonstrates how lazy behavioral subtyping can be combined with interface specifications to produce an incremental and modular reasoning system for object-oriented class hierarchies.     

View creation for queries in object oriented databases

A view in object oriented databases corresponds to virtual schema with restructured generalization and decomposition hierarchies,Numbers of view creation methodologies have been proposed.A major drawback of existing methodologies is that they do not maintain the closure property.That is,the result of a query does not have the same semantics as embodied in the object oriented data model.Teherefore,this paper presents a view creation methodology that derives a class in response to a user‘s query,integrates derived class in global schema (i.e., considers the problem of classes moving in class hierarchy)and selects the required classes from global schema to create the view for user‘s query.Novel idea of view creation includes:(a) an object algebra for class derivation and customization(where the derived classes in terms of object instances and procedure/methods are studied),(b)maintenance of closure property,and (c)classification algorithm which provides mechanism to deal with the problem of a class moving in a class hierarchy.     

Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers

The Vapnik-Chervonenkis (V-C) dimension is an important combinatorial tool in the analysis of learning problems in the PAC framework. For polynomial learnability, we seek upper bounds on the V-C dimension that are polynomial in the syntactic complexity of concepts. Such upper bounds are automatic for discrete concept classes, but hitherto little has been known about what general conditions guarantee polynomial bounds on V-C dimension for classes in which concepts and examples are represented by tuples of real numbers. In this paper, we show that for two general kinds of concept class the V-C dimension is polynomially bounded in the number of real numbers used to define a problem instance. One is classes where the criterion for membership of an instance in a concept can be expressed as a formula (in the first-order theory of the reals) with fixed quantification depth and exponentially-bounded length, whose atomic predicates are polynomial inequalities of exponentially-bounded degree, The other is classes where containment of an instance in a concept is testable in polynomial time, assuming we may compute standard arithmetic operations on reals exactly in constant time.Our results show that in the continuous case, as in the discrete, the real barrier to efficient learning in the Occam sense is complexity-theoretic and not information-theoretic. We present examples to show how these results apply to concept classes defined by geometrical figures and neural nets, and derive polynomial bounds on the V-C dimension for these classes.     

Observations on complete sets between linear time and polynomial time

There is a single set that is complete for a variety of nondeterministic time complexity classes with respect to related versions of m-reducibility. This observation immediately leads to transfer results for determinism versus nondeterminism solutions. Also, an upward transfer of collapses of certain oracle hierarchies, built analogously to the polynomial-time or the linear-time hierarchies, can be shown by means of uniformly constructed sets that are complete for related levels of all these hierarchies. A similar result holds for difference hierarchies over nondeterministic complexity classes. Finally, we give an oracle set relative to which the nondeterministic classes coincide with the deterministic ones, for several sets of time bounds, and we prove that the strictness of the tape-number hierarchy for deterministic linear-time Turing machines does not relativize.