基于阈值的概率图可达查询

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定图的可达查询不能有效地处理不确定性,因此该文研究用概率语义描述的图可达性查询.具体的,该文使用可能世界概率模型定义不确定图(称为概率图),基于该模型,研究了基于阈值的概率可达查询(T-PR).首先为避免枚举所有可能世界,给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法,给出3种改进方法,它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计.     

不确定图数据库中高效查询处理

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.     

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

面向不确定平面图的模式匹配查询

平面图的模式匹配查询可广泛应用于生物网络、社会网络、指纹识别和图像分割等。由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定平面图的查询处理技术不能有效地处理不确定性,因此利用概率语义描述的平面图的模式进行匹配查询。具体地,使用可能世界概率模型定义不确定平面图,基于该模型,研究了不确定模式匹配(UPM)查询。首先给出一个确定算法可避免枚举所有的可能世界,同时给出改进的确定算法可更快速地求解查询。其次设计出采样算法,可快速地估算出匹配概率,并具有较高的精确度。基于真实不确定平面图数据的大量实验验证了该设计。最后将该查询应用于肺部CT图像的分割,结果表明此方法优于经典的图像分割算法。     

基于距离阈值的不确定图可达性查询处理

在不确定数据的处理中,不确定图作为典型的数据模型得到了广泛的关注,研究的内容包括基于不确定图的子图匹配、最近邻查询及连接查询等,本文研究基于距离阈值的不确定图可达性查询,即给定不确定图及图中任意两点s、t和距离阈值d,返回s和t的d可达的概率.提出一种基于随机抽样的可达性查询处理算法.定义了一种不确定图可能图实例的分类树模型.为了提高图实例分类的获取效率,提出基于双向遍历的优化分类树模型.设计了基于图实例类抽样的可达性查询处理算法并通过理论分析和实验验证了算法的性能.     

受限网络移动对象的概率最近邻查询

基于自由空间移动对象概率最近邻查询,给出受限网络移动对象概率最近邻(CNPNN)查询概念,提出一种基于网络概率Voronoi图的CNPNN查询算法.利用基于网络距离的概率度量得到不确定数据的网络概率Voronoi单元,建立网络概率Voronoi 图覆盖受限网络.使用对点查询具有优势的R+树,对不确定数据的网络概率Voronoi单元进行索引,减少搜索时间.确定查询对象所在网络Voronoi单元,得到查询对象最可能的最近邻.实验结果表明,该算法时间复杂度为O(n2+mlogmn),在一定条件下具有较好的性能.     

基于图数据库的RDF数据分布式存储

RDF数据模型具有天然的图结构,因此以图结构存储可以避免RDF逻辑数据模型到物理数据模型的转换。基于图数据库的RDF数据分布式存储方案,重点讨论RDF图数据流分割、图数据库分布式扩展、SPARQL查询语言转CYPHER图形查询语言等。实验对比了基于Neo4j图数据库与基于MySQL关系型数据库的RDF数据存储方案的处理性能,并验证了RDF图数据流分割算法的有效性。     

高效的连续不确定XML数据Top-k查询算法

目前,不确定XML数据的top-k查询算法中都没有处理连续不确定数据,本文提出SPCProTJFast算法,该算法改进了传统的归并算法,并结合连续不确定数据的过滤方法,实现了连续不确定XML的Top-k查询。为了避免概率下限值过小对过滤效果的影响,又提出HPCProTJFast算法,该算法推迟了对连续节点的处理,只有在获得满足概率条件的整枝路径时才对连续节点进行访问。实验表明,在执行时间以及过滤效率上,同直接处理连续不确定数据的ProTJFast算法相比,这两种算法都要更高效,并且HPCProTJFast算法的效率更高。     

无线传感器网络不确定数据PT-Top k查询处理技术

在无线传感器网络现实应用中,感知数据普遍存在不确定性。由于不确定数据引入了概率维度,使得不确定数据查询种类更加丰富,同时也给查询处理带来困难。不确定数据Top-k查询是一个典型的不确定数据查询任务。考虑到无线传感器网络查询处理技术对查询响应时间和网络通信消耗的高要求,研究了面向层次聚簇结构的无线传感器网络不确定数据Top-k查询处理技术。通过分析不确定数据特点,基于x-tuple规则元组模型,采用簇内与簇间的两阶段数据查询处理机制,提出了基于Poisson分布的分布式不确定数据PT-Top k查询处理近似算法TPQP。通过实验,从总体通信消耗、与概率阈值p相关分析、与排序数k相关分析以及数据敏感度分析等方面,说明了TPQP算法在通信消耗、查询响应时间上的优越性。     

Contorsion: A Semantic XPath Processor

This work describes the architecture of Contorsion, a semantic XPath processor that acts over an RDF mapping of XML. It contributes to a recent research trend that defines an XML-to-RDF mapping allowing XML documents interoperate at the semantic level. We use a model-mapping approach to represent instances of XML and XML Schema in RDF. This representation retains the node order, in contrast with the usual structure-mapping approach. The processor can be fed with an unlimited set of XML schemas and/or RDFS/OWL ontologies. The queries are resolved taking in consideration the structural and semantic connections descrived in the schemas and ontologies. Such behaviour, schema-awareness and semantic integration, can be useful for exploiting schema and ontology hierarchies in XPath queries.     

一种保持结点可达性的高效社会网络图匿名算法

为了保护社会网络隐私信息,提出了多种社会网络图匿名化技术.图匿名化目的在于通过图修改操作来防止隐私泄露,同时保证匿名图在社会网络分析和图查询方面的数据可用性.可达性查询是一种基本图查询操作,可达性查询精度是衡量图数据可用性的一项重要指标.然而,当前研究忽略了图匿名对结点可达性的影响,导致较大的可达性信息损失.为了保持匿名图中结点的可达性,提出了可达性保持图匿名化（reachability preserving anonymization,简称RPA）算法,其基本思想是将结点进行分组并采取贪心策略进行匿名,从而减少匿名过程中的可达性信息损失.为了保证RPA算法的实用性,针对其执行效率进行优化,首先提出采用可达区间来高效地评估边添加操作所导致的匿名损失;其次,通过采用候选邻居索引,进一步加速RPA算法对每个结点的匿名过程.基于真实社会网络数据的实验结果表明了RPA算法的高执行效率,同时验证了生成匿名图在可达性查询方面的高精度.     

Coding-based Join Algorithms for Structural Queries on Graph-Structured XML Document

In many applications, XML documents need to be modelled as graphs. The query processing of graph-structured XML documents brings new challenges. In this paper, we design a method based on labelling scheme for structural queries processing on graph-structured XML documents. We give each node some labels, the reachability labelling scheme. By extending an interval-based reachability labelling scheme for DAG by Rakesh et al., we design labelling schemes to support the judgements of reachability relationships for general graphs. Based on the labelling schemes, we design graph structural join algorithms to answer the structural queries with only ancestor-descendant relationship efficiently. For the processing of subgraph query, we design a subgraph join algorithm. With efficient data structure, the subgraph join algorithm can process subgraph queries with various structures efficiently. Experimental results show that our algorithms have good performance and scalability. Support by the Key Program of the National Natural Science Foundation of China under Grant No.60533110; the National Grand Fundamental Research 973 Program of China under Grant No. 2006CB303000; the National Natural Science Foundation of China under Grant No. 60773068 and No. 60773063.     

PS+Pre/Post: A novel structure and access mechanism for wireless XML stream supporting twig pattern queries

XML data broadcast is an efficient way to disseminate XML data to a large number of mobile clients in mobile wireless networks. Recently, several indexing methods have been proposed to improve the performance of XML query processing in terms of access time and tuning time over XML streams. However, existing indexing methods cannot process twig pattern XML queries. In this paper, we propose a novel structure for streaming XML data called PS+Pre/Post by integrating the path summary technique and the pre/post labeling scheme. Our proposed XML stream structure exploits the benefits of the path summary technique and the pre/post labeling scheme to efficiently process different types of XML queries over the broadcast stream. Experimental results show that our proposed XML stream structure improves the performance of access time and tuning time in processing different types of XML queries.     

Query processing optimization in broadcasting XML data in mobile communications

Todays, XML as a de facto standard is used to broadcast data over mobile wireless networks. In these networks, mobile clients send their XML queries over a wireless broadcast channel and recieve their desired XML data from the channel. However, downloading the whole XML data by a mobile device is a challenge since the mobile devices used by clients are small battery powered devices with limited resources. To meet this challenge, the XML data should be indexed in such a way that the desired XML data can be found easily and only such data can be downloaded instead of the whole XML data by the mobile clients. Several indexing methods are proposed to selectively access the XML data over an XML stream. However, the existing indexing methods cause an increase in the size of XML stream by including some extra information over the XML stream. In this paper, a new XML stream structure is proposed to disseminate the XML data over a broadcast channel by grouping and summarizing the structural information of XML nodes. By summarizing such information, the size of XML stream can be reduced and therefore, the latency of retrieving the desired XML data over a wirless broadcast channel can be reduced. The proposed XML stream structure also contains indexes in order to skip from the irrelevant parts over the XML stream. It therefore can reduce the energy consumption of mobile devices in downloading the results of XML queries. In addition, our proposed XML stream structure can process different types of XML queries and experimental results showed that it improves the performace of XML query processing over the XML data stream compared to the existing research works in terms of access and tuning times.

     

Ultrawrap: SPARQL execution on relational data

The Semantic Web’s promise of web-wide data integration requires the inclusion of legacy relational databases,¹ i.e. the execution of SPARQL queries on RDF representation of the legacy relational data. We explore a hypothesis: existing commercial relational databases already subsume the algorithms and optimizations needed to support effective SPARQL execution on existing relationally stored data. The experiment is embodied in a system, Ultrawrap, that encodes a logical representation of the database as an RDF graph using SQL views and a simple syntactic translation of SPARQL queries to SQL queries on those views. Thus, in the course of executing a SPARQL query, the SQL optimizer uses the SQL views that represent a mapping of relational data to RDF, and optimizes its execution. In contrast, related research is predicated on incorporating optimizing transforms as part of the SPARQL to SQL translation, and/or executing some of the queries outside the underlying SQL environment.Ultrawrap is evaluated using two existing benchmark suites that derive their RDF data from relational data through a Relational Database to RDF (RDB2RDF) Direct Mapping and repeated for each of the three major relational database management systems. Empirical analysis reveals two existing relational query optimizations that, if applied to the SQL produced from a simple syntactic translations of SPARQL queries (with bound predicate arguments) to SQL, consistently yield query execution time that is comparable to that of SQL queries written directly for the relational representation of the data. The analysis further reveals the two optimizations are not uniquely required to achieve a successful wrapper system. The evidence suggests effective wrappers will be those that are designed to complement the optimizer of the target database.     

有向图上的广义可达性查询处理方法

随着社会网络、生物信息学、本体等应用的迅速发展,如何在图上进行高效的信息检索成为一个亟待解决的问题。两点间可达性查询是一种常见的查询方式,目前针对此类查询已经提出了许多算法。但是在一些应用中,这种查询语义并不能满足用户需求。基于此,提出了两种广义可达性查询语义。研究了如何在大图上进行高效的广义可达性查询的问题,依据Path-tree编码的特性提出了一种新的二级索引机制——RB+索引。基于RB+索引,针对不同类型查询提出了两种高效的查询处理方法。该方法充分利用Path-tree编码的特性,有效地处理广义可达性查询。通过实验对提出的索引和查询算法进行了验证。     

Towards practical meta-querying

We describe a meta-querying system for databases containing queries in addition to ordinary data. In the context of such databases, a meta-query is a query about queries. Representing stored queries in XML, and using the standard XML manipulation language XSLT as a sublanguage, we show that just a few features need to be added to SQL to turn it into a fully-fledged meta-query language. The good news is that these features can be directly supported by extensible database technology.