PMC: Select Materialized Cells in Data Cubes

QC-Tree is one of the most storage-efficient structures for data cubes in an MOLAP system. Although QC-Tree can achieve a high compression ratio, it is still a fully materialized data cube. In this paper, an improved structure PMC is presented allowing us to materialize only a part of the cells in a QC-Tree to save more storage space. There is a notable difference between our partially materialization algorithm and traditional materialized views selection algorithms. In a traditional algorithm, when a view is selected, all the cells in this view are to be materialized. Otherwise, if a view is not selected, all the cells in this view will not be materialized. This strategy results in the unstable query performance. The presented algorithm, however, selects and materializes data in cell level, and, along with further reduced space and update cost, it can ensure a stable query performance. A series of experiments are conducted on both synthetic and real data sets. The results show that PMC can further reduce storage space occupied by the data cube, and can shorten the time to update the cube.     

基于内容图像检索中的一种动态多维索引方法

多维索引技术是基于内容检索的图像数据库的关键技术。SR-tree和X-tree是目前比较成熟有效的多维索引技术。为了提高多维索引的性能,我们在分析SR-tree和X-tree的结构和性能的基础上,针对SR-tree分裂算法的不足,引入X-tree中超级节点的思想,通过改进插入和分裂算法,设计了一种新的多维索引结构ESR-tree,即ExtendedSR-tree。实验表明,随着数据量和维数的增多,ESR-tree的性能明显优于SR-tree和X-tree。     

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

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

VisualDM：一个灵活的可视化数据挖掘系统

如果要建造一个健壮的数据挖掘系统，仅仅依靠挖掘算法是不够的。目前的挖掘算法还没有完全“智能”化，所以挖掘有用的信息常常不是很有效。不过可视化技术给了我们很大的帮助，我们将挖掘算法和可视化技术结合起来，从而实现了数据挖掘系统VisualDM。     

多维组合预测的贝叶斯极大似然估计

为了实际预测的需要,提出了多维组合预测问题,即若干单项多维预测的变权组合预测.在各单项预测无偏且服从正态分布前题下,求出了p时刻预测向量Xp的先验分布密度和后验分布密度.利用主观先验信息、预测信息和样本信息,运用贝叶斯估计方法,得到了Xp的贝叶斯极大似然估计,其权重随时刻p的改变而改变.本方法充分利用了多维变量间的相关信息,进一步提高了预测的科学性和有效性,体现了对样本信息和预测信息的进一步综合应用.     

Image Manifolds which are Isometric to Euclidean Space

Recently, the Isomap procedure [10] was proposed as a new way to recover a low-dimensional parametrization of data lying on a low-dimensional submanifold in high-dimensional space. The method assumes that the submanifold, viewed as a Riemannian submanifold of the ambient high-dimensional space, is isometric to a convex subset of Euclidean space. This naturally raises the question: what datasets can reasonably be modeled by this condition? In this paper, we consider a special kind of image data: families of images generated by articulation of one or several objects in a scene—for example, images of a black disk on a white background with center placed at a range of locations. The collection of all images in such an articulation family, as the parameters of the articulation vary, makes up an articulation manifold, a submanifold of L ². We study the properties of such articulation manifolds, in particular, their lack of differentiability when the images have edges. Under these conditions, we show that there exists a natural renormalization of geodesic distance which yields a well-defined metric. We exhibit a list of articulation models where the corresponding manifold equipped with this new metric is indeed isometric to a convex subset of Euclidean space. Examples include translations of a symmetric object, rotations of a closed set, articulations of a horizon, and expressions of a cartoon face. The theoretical predictions from our study are borne out by empirical experiments with published Isomap code. We also note that in the case where several components of the image articulate independently, isometry may fail; for example, with several disks in an image avoiding contact, the underlying Riemannian manifold is locally isometric to an open, connected, but not convex subset of Euclidean space. Such a situation matches the assumptions of our recently-proposed Hessian Eigenmaps procedure, but not the original Isomap procedure.     

基于C++语言的多维动态数组的实现

在用Visual C 语言处理复杂和庞大的数据时,常需要用到多维动态数组来管理,但开辟多维动态数组时指针的使用是极为复杂和难于理解的。针对这一问题,利用“递推”的思想进行研究,给出快速有效地建立多维动态数组的C 代码的思路和方法,并给出详细代码。经过验证此方法是可行的,从而为较好地解决这类问题带来很大的方便。     

重建数据立方体的数据覆盖方法

数据切片体现了数据立方体某方面的数据特征,当产生数据切片的数据立方体由于某种原因不可访问时,通过已知的多个数据切片尽可能地恢复数据立方体中的原始信息,有利于对数据的深入分析和理解.提出了一种基于数据切片重建数据立方体的方法,通过数据切片的连接生成多维细粒度空间,利用数据覆盖操作逐步细分每个数据切片所对应的多维空间,以逼近多维细粒度空间.提出了重建后数据立方体的可查询判据.该方法直接利用数据库中的基本操作来实现,高效地支持大数据量的应用环境.     

基于双幅图像三维重建的不确定性分析

由于得到基于误差传播理论的重建不确定性显式公式并没有直观性,文章在给出三维重建扰动分析模型的基础上,应用多元分析的统计方法研究了图像量化误差、匹配误差、标定误差等对重建精度的影响。采用计算机仿真图像进行实验,向重建模型中输入高斯噪声进行扰动分析,这样有利于对不确定性的评定,仿真实验证明了方法的有效性。最后,对三维重建点的伸展不确定性也进行了可视化。     

Searching in metric spaces by spatial approximation

We propose a new data structure to search in metric spaces. A metric space is formed by a collection of objects and a distance function defined among them which satisfies the triangle inequality. The goal is, given a set of objects and a query, retrieve those objects close enough to the query. The complexity measure is the number of distances computed to achieve this goal. Our data structure, called sa-tree (“spatial approximation tree”), is based on approaching the searched objects spatially, that is, getting closer and closer to them, rather than the classic divide-and-conquer approach of other data structures. We analyze our method and show that the number of distance evaluations to search among n objects is sublinear. We show experimentally that the sa-tree is the best existing technique when the metric space is hard to search or the query has low selectivity. These are the most important unsolved cases in real applications. As a practical advantage, our data structure is one of the few that does not need to tune parameters, which makes it appealing for use by non-experts. Edited by R. Sacks-Davis Received: 17 April 2001 / Accepted: 24 January 2002 / Published online: 14 May 2002