视频结构化浏览和查询系统：Videowser

显然目前存在一些基于镜头的视频分析方法能够为用户操纵视频提供一些方便,但由于在一个长视频中其镜头数太多,单元太小,而且单个视频镜头往往也无法表达出潜在的视频语义,所有这些都说明了必要的一个更高的层次上去组织视频。本文提出的视频目录层次结构把视频中镜头在其自身时间及内容的约束下形成若干镜群,再对镜群中的镜头进行聚类获得若干视觉相似镜头的集束－镜组,据此设计和实现的Videowser可让用户通过视频的目录层次结构进行非线性的浏览及观看;用户除了进行非线性的浏览外,还可根据自己的需要直接进行基于视频内容和语义的综合查询。     

音乐数据库的基于内容检索及一种基于ICA算法的按调查询系统的提出

目前音频数据库的研究相对于图象处于滞后,文中侧重音乐角度,结合MPEG标准和基于内容检索的应用,综述了音频检索的研究现状,分析了音频方面研究的特殊性和相关应用中的问题;并提出基于独立分量分析（ICA）的按调查询（QBH）的系统,较好地解决了特征提取中的鸡尾酒会效应问题。系统的查询结果置于三维声效环境中加速了查询。     

基于网格中间件的统一检索

网格技术是近年来新兴的一个研究热点,它使互联网上所有资源实现全面共享与协同工作,将整个因特网整合为一个巨大的超级计算机,为用户提供"即连即用"的服务.本文详细介绍了网格中间件OGSA-DAI和OGDA-DQP,并针对目前图书馆期刊信息整合的现状,利用网格中间件技术对各种期刊数据库进行整合,即利用OGSA-DAI对期刊数据库进行封装,通过OGSA-DQP进行统一检索,解决了目前在异构数据库整合中基于界面整合自治性差、稳定性不好的特点.     

GIS二维、三维空间信息查询功能的实现与应用

空间信息查询是GIS中的重要功能之一,因而也是GIS软件开发人员的工作重点之一。从中国大陆岩石圈GIS这一实际应用出发,在分析相关技术的基础上,提出了一套GIS二维和三维空间－属性数据交互查询的实现方法,并将此方法用于GIS软件平台开发,实现了高效的功能。最后给出应用实例,结果证明了这种方法的可行性和实用性。     

基于关系数据库分裂存储的XML文档片段重构*

首先对基于关系数据库分裂存储XML文档的各种方法进行总结,并对X-RESTORE基于关系数据库的XML文档的分裂存储原理和关系存储模式进行介绍;然后对XML查询的三种计算模式进行分析;最后基于X-RESTORE给出一个重构结果文档片段的算法,并对该算法的执行代价进行分析。分析结果显示,X-RESTORE不仅能够有效地支持XML的选择计算模式,而且能够有效地支持XML的抽取计算模式和重构计算模式。     

基于内容的图象检索技术的研究和发展

多媒体技术和数字图书馆的发展和应用,使基于图象内容的检索技术,成为图象处理和计算机视觉的前沿问题。图象数据库检索查询的研究目的就是实现自动地、智能化地检索和管理图象。文章详细介绍了该技术的研究状况和具体应用,并探讨了其发展前景。     

Optimizing multiple dimensional queries simultaneously in multidimensional databases

Some significant progress related to multidimensional data analysis has been achieved in the past few years, including the design of fast algorithms for computing datacubes, selecting some precomputed group-bys to materialize, and designing efficient storage structures for multidimensional data. However, little work has been carried out on multidimensional query optimization issues. Particularly the response time (or evaluation cost) for answering several related dimensional queries simultaneously is crucial to the OLAP applications. Recently, Zhao et al. first exploited this problem by presenting three heuristic algorithms. In this paper we first consider in detail two cases of the problem in which all the queries are either hash-based star joins or index-based star joins only. In the case of the hash-based star join, we devise a polynomial approximation algorithm which delivers a plan whose evaluation cost is $ O(n^{\epsilon }$) times the optimal, where n is the number of queries and is a fixed constant with . We also present an exponential algorithm which delivers a plan with the optimal evaluation cost. In the case of the index-based star join, we present a heuristic algorithm which delivers a plan whose evaluation cost is n times the optimal, and an exponential algorithm which delivers a plan with the optimal evaluation cost. We then consider a general case in which both hash-based star-join and index-based star-join queries are included. For this case, we give a possible improvement on the work of Zhao et al., based on an analysis of their solutions. We also develop another heuristic and an exact algorithm for the problem. We finally conduct a performance study by implementing our algorithms. The experimental results demonstrate that the solutions delivered for the restricted cases are always within two times of the optimal, which confirms our theoretical upper bounds. Actually these experiments produce much better results than our theoretical estimates. To the best of our knowledge, this is the only development of polynomial algorithms for the first two cases which are able to deliver plans with deterministic performance guarantees in terms of the qualities of the plans generated. The previous approaches including that of [ZDNS98] may generate a feasible plan for the problem in these two cases, but they do not provide any performance guarantee, i.e., the plans generated by their algorithms can be arbitrarily far from the optimal one. Received: July 21, 1998 / Accepted: August 26, 1999     

Low-contention data structures

We consider the problem of minimizing contention in static (read-only) dictionary data structures, where contention is measured with respect to a fixed query distribution by the maximum expected number of probes to any given cell. The query distribution is known by the algorithm that constructs the data structure but not by the algorithm that queries it. Assume that the dictionary has n$n$ items. When all queries in the dictionary are equiprobable, and all queries not in the dictionary are equiprobable, we show how to construct a data structure in O(n)$O\left(n\right)$ space where queries require O(1)$O\left(1\right)$ probes and the contention is O(1/n)$O(1/n)$. Asymptotically, all of these quantities are optimal. For arbitrary   query distributions, we construct a data structure in O(n)$O\left(n\right)$ space where each query requires O(logn/loglogn)$O(logn/loglogn)$ probes and the contention is O(logn/(nloglogn))$O(logn/(nloglogn))$. The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: for a large class of algorithms, we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(loglogn)$\Omega (loglogn)$.     

OLAP query reformulation in peer-to-peer data warehousing

Inter-business collaborative contexts prefigure a distributed scenario where companies organize and coordinate themselves to develop common and shared opportunities, but traditional business intelligence systems do not provide support to this end. To fill this gap, in this paper we envision a peer-to-peer data warehousing architecture based on a network of heterogeneous peers, each exposing query answering functionalities aimed at sharing business information. To enhance the decision making process, an OLAP query expressed on a peer needs to be properly reformulated on the local multidimensional schemata of the other peers. To this end, we present a language for the definition of mappings between the multidimensional schemata of peers and we introduce a query reformulation framework that relies on the translation of mappings, queries, and multidimensional schemata onto the relational level. Then, we formalize a query reformulation algorithm and prove two properties: correctness and closure, that are essential in a peer-to-peer setting. Finally, we discuss the main implementation issues related to the reformulation setting proposed, with specific reference to the case in which the local multidimensional engines hosted by peers use the standard MDX language.     

Ontological query answering under expressive Entity-Relationship schemata

The Entity-Relationship (ER) model is a fundamental tool for database design, recently extended and employed in knowledge representation and reasoning due to its expressiveness and comprehensibility. We address the problem of answering conjunctive queries under constraints representing schemata expressed in an extended version of the Entity-Relationship model. This extended model, called ER⁺, comprises is-a constraints among entities and relationships, plus functional and mandatory participation constraints. In particular, it allows for arbitrary permutations of the roles in is-a among relationships. A key notion that ensures high tractability in ER⁺ schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs of ER⁺. We provide a precise syntactic characterization of separable ER⁺ schemata by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under separable ER⁺ schemata, and also under several sublanguages of ER⁺. We show that the addition of so-called negative constraints does not increase the complexity of query answering. With such constraints, our model properly generalizes the most widely adopted tractable ontology languages, including those in the DL-Lite family.