基于量子第三方的隐私数据库查询协议

保障查询数据库时用户及数据库的隐私性具有重要意义。该文利用三光子GHZ(Greenberger-Horne- Zeilinger)态的量子关联性,提出一个基于量子第三方的隐私数据库查询协议。协议对于信道损耗具有很高的容忍度,并且能够有效地抵抗第三方发动伪造量子纠缠态和量子记忆存储攻击。在第三方的帮助下,协议能够确定地控制用户获得数据库隐私信息的数量。同时,利用Mermin-Bell不等式进行真正的三方纠缠验证保证协议的安全性,这一思想也拓展了设备无关纠缠验证的应用领域。     

关系数据库中基于区域聚类的多区域查询优化

针对关系数据库及其应用中多个区域查询的并发处理,提出了一种区域聚类的方法,其基本思路是将多个查询中相近的区域分成若干组,每组构成较大的区域,从较大的区域中检索元组.这种方法避免了多个区域中相同部分的多次访问,减少了数据库I/O操作的次数.对于低维和高维数据,此方法与一一查询的朴素方法相比,其性能都有明显提高.     

一种基于彩色特征点的对象查询方法

图像检索系统中对象的查询,主要采用分割技术来实现。虽然一些研究人员提出过利用光学特征的方法,但是只应用于灰度图像,不能对大量的彩色图像进行有效的查询。为此本文提出了一种基于彩色特征点的对象查询新方法。首先,利用Harris彩色点提取嚣从彩色图像中提取出一组能表征图像特征的彩色点;其次,利用特征点的梯度、角度不变性构造检索策略来实现对象的查询。实验表明,该方法对于对象的光照变化和几何变化有较强的鲁棒性。     

对等网络研究及其挑战

Internet的飞速发展使对等网络(P2P)研究成为热点,本文介绍了非结构化的第一代P2P系统和基于兮布式啥希表的第二代P2P系统,对算法进行了比较和分析,指出了存在的问题和面临的挑战。     

On fuzzy approaches for enlarging skyline query results

In the last decade, skyline queries have gained much attention and are proved to be valuable for multi-criteria decisions. Based on the concept of Pareto dominance, they return the non-dominated points, called the skyline points. In practice, it may happen that the skyline only contains a small number of points which could be insufficient for the user needs. In this paper, we discuss two fuzzy-set-based approaches to enriching the small skyline with particular points that could serve the decision makers’ needs. The basic idea consists in identifying the most interesting points among the non-skyline ones. On the one hand, we introduce a novel fuzzy dominance relationship which makes more demanding the dominance between the points of interest. So, much points would be considered as incomparable and then as elements of the new relaxed skyline. On the other hand, we leverage an appropriate fuzzy closeness relation to retrieve non skyline points that are fuzzily close to some skyline points. Furthermore, we develop efficient algorithms to compute the relaxed variants of skyline. Extensive experiments are conducted to demonstrate the effectiveness of our approaches and analyze the performance of the proposed algorithms. A comparative study between the approaches presented is made as well.     

On the non-efficient PAC learnability of conjunctive queries

This note serves three purposes: (i) we provide a self-contained exposition of the fact that conjunctive queries are not efficiently learnable in the Probably-Approximately-Correct (PAC) model, paying clear attention to the complicating fact that this concept class lacks the polynomial-size fitting property, a property that is tacitly assumed in much of the computational learning theory literature; (ii) we establish a strong negative PAC learnability result that applies to many restricted classes of conjunctive queries (CQs), including acyclic CQs for a wide range of notions of acyclicity; (iii) we show that CQs (and UCQs) are efficiently PAC learnable with membership queries.     

Algebraic optimization of recursive queries

Over the past few years, much attention has been paid to deductive databases. They offer a logic-based interface, and allow formulation of complex recursive queries. However, they do not offer appropriate update facilities, and do not support existing applications. To overcome these problems an SQL-like interface is required besides a logic-based interface.

In the PRISMA project we have developed a tightly-coupled distributed database, on a multiprocessor machine, with two user interfaces: SQL and PRISMAlog. Query optimization is localized in one component: the relational query optimizer. Therefore, we have defined an eXtended Relational Algebra that allows recursive query formulation and can also be used for expressing executable schedules, and we have developed algebraic optimization strategies for recursive queries. In this paper we describe an optimization strategy that rewrites regular (in the context of formal grammars) mutually recursive queries into standard Relational Algebra and transitive closure operations. We also describe how to push selections into the resulting transitive closure operations.

The reason we focus on algebraic optimization is that, in our opinion, the new generation of advanced database systems will be built starting from existing state-of-the-art relational technology, instead of building a completely new class of systems.     

Queries and Concept Learning

We consider the problem of using queries to learn an unknown concept. Several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. Examples are given of efficient learning methods using various subsets of these queries for formal domains, including the regular languages, restricted classes of context-free languages, the pattern languages, and restricted types of propositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.     

Multidimensional extendible hashing for partial-match queries

Hashing is a well-known technique for organizing direct access files. Extendible hashing removes the restriction on the expansion of the file and thus allows dynamic files. We generalize the technique to store multi-attribute keys. Exact-match queries (searching) can be done in constant time usingn-dimensional hashing. Ann-dimensional partial-match queries givenk attributes can be answered inO(N**((n –k)/n)) time whereN is the number of records stored. It is shown thatn-dimensional hashing is a special case of one-dimensional hashing, thus the storage utilization of the buckets is independent ofn. Simulation results are presented to show the advantages of multidimensional hashing.This research was partially supported by a Research Initiation Grant from the University of Houston.     

Exact Learning of Formulas in Parallel

We investigate the parallel complexity of learning formulas from membership and equivalence queries. We show that many restricted classes of boolean functions cannot be efficiently learned in parallel with a polynomial number of processors.