一种高效的基于刻面分类的构件检索算法研究

如何从构件库中准确快速找到需要的构件,是每个构件库系统需要解决的一个主要问题。基于树匹配的思想通过研究构件的特点,提出了基于刻面路径匹配的算法,它使用后缀字典排序来提高查询的效率,该算法可以在保持构件查询速度的前提下,有效提高构件的查全率和查准率,实验结果证明了该算法的可行性与有效性。     

一种高效的XML路径查询索引

XML文档的查询索引是当前研究的热点。提出一种高效的XML路径查询索引KDXI,首先对XML文档进行编码,然后建立结构索引并对结构索引进行编码。研究了基于KDXI索引结构的半结构连接算法和路径查询处理过程。通过KDXI索引机制,可以有效执行一般的路径查询语句,并避免冗余的结构连接操作。实验证明了KDXI索引机制的优越性。     

基于代价的XML路径索引构建

处理路径表达式是XML查询技术中的难点和热点．在本实验室提出的XML路径表达式索引-结构化映射的基础上．为了降低构建索引所需的空间开销，本文提出了构建路径索引的代价模型，并设计了基于给定查询负载，有选择地构建路径索引的相应算法，为给定查询负载自动选择近最优索引模式（NOIS）．本文还提出了当查询效率发生变化时，系统对索引模式进行自适应调整的策略．实验研究表明：使用本文方法，系统可在不影响路径表达式处理效率的前提下，大大降低路径索引的空间开销，取得查询收益和空间开销的较佳权衡．     

一种新的基于Dewey编码的XML路径索引

建立高效的索引来快速定位满足要求的节点是提高XML数据查询效率的一个必要手段.文中以降低复杂度和提高查询效率为目标,以基于路径的XML索引原理为基础,提出了一种新型的基于Dewey编码的索引结构RTL-Index.RTL-Index通过对文档节点编码来表示结构信息,利用前缀路径匹配操作完成结构查询,支持含通配符" 和后代轴"//"的查询以及兄弟节点无序的模式树的查询.仿真实验结果表明RTL-Index索引具有较低的时间和空间复杂度,解决了XML文档分支路径查找问题,是一种较为有效的XML索引结构.     

D（k，l）-索引：一种自适应的XML数据索引

XML已成为网络上数据表示和交换的一种实际标准。为促进XML的数据和半结构化数据的查询，几种结构概要被提出。它们可以直接从数据中得出，并以索引的方式来估计在XML数据上的路径表达式。在本文中，综合几种索引提出新型数据结构D(k，l)索引。其参数k，l刻画了节点向上和向下的相似度。它考虑各个节点向上路径和向下路径的相似关系，因此它可以有效地支持路径表达式，尤其支持带分支路径表达式的查询，同时，它也可以根据查询情况的变化来动态地改变索引结构，使索引结构更适合当前的查询要求，实验表明我们的方法具有很好的效率和效果。     

IRST(k,l)-Index:一种支持分支路径查询的高效XML结构索引

为快速准确地查询图结构XML文档,本文在互关联后继树(IRST)的基础上,引入结构索引的相似性归并思想,提出一种基于互关联后继树且支持分支路径查询的高效XML结构索引-IRST(k,l)-index,并给出该索引的快速创建和查询算法.经实验验证,与国际上同类索引相比,该索引的创建速度更快、查询效率更高、空间开销更小.     

基于PATRICIA-TRIES的XML路径索引设计

随着XML逐渐成为Internet数据表示与交换的标准，如何快速准确地访问XML文档中的数据已成为亟待解决的关键问题，建立路径索引是提高查询效率的一种重要手段．本文设计了一种基于PATRICIA-TRIES的路径索引，简称PT索引．该索引有如下特点：一、基于PATRICIA-TRIES结构，实现快速检索．二、采用压缩编码能够将路径索引放入内存，三、索引含有结构和文本信息，通过查询索引就能提供结果，无需打开原文档．其后，分析了PT索引的时间和空间复杂性，并与三种的典型的索引结构进行了对比实验，结果证明了其在路径查询方面具有更高的效率．     

基于DOM的XML数据库的索引技术研究

XML作为一种数据交换的国际标准，已经贯穿于Internet应用的各个领域之中，如何快速准确地存储和查询XML数据的数据库技术是一个重要的研究课题。XML索引技术对XML数据库查询处理起着至关重要的作用，提出了基于DOM的XML数据库的索引技术(路径连接索引、值索引和引用索引)，解决了传统的基于树的遍历的XML数据查询方法性能上的不足，并着重对处理含有谓词和引用关系等较复杂的查询路径的不同处理方法进行了对比和分析，还给出了索引空间利用率、查询性能和索引维护代价3个方面的标准测试结果，表明新的索引技术可以有效地提高查询处理效率。     

基于索引的XML查询技术研究

介绍了目前XML数据查询技术的研究现状，对主要的XML索引查询技术作了较深入的探讨，其中包括：基于路径索引的XML查询方法，如DataGuide、1-index、A（k）索引等；基于编码的XML索引查询方法，如Anc_Desc_B^＋、XR树＋XR-Stack算法等。文中对相关XML索引查询方法的优点和不足进行了分析。     

利用DTD模式优化基于路径的XML的查询

XML作为一种数据的表示形式,正在数据库及网络中数据传输的领域被广泛使用,提高对它查询的速度也成为一个我们研究的方向,最近提出了利用DTD来提高查询效率的方法,基于这一思想,为了更高效地利用DTD,这篇文章提出了一种更高效利用DTD的方法,首先介绍了扫描DTD树的结果,即真路径的存储方式,然后给出了扫描DTD树的算法,我们还给出了怎样利用真路径对文档树进行扫描的算法,最后给出了例子,并分析了我们提高效率的原理.     

基于面向对象XML数据的索引机制

XML正在迅速成为Internet上信息表示和数据交换的重要标准.而面向对象的特征具有很强的建模能力,将面向对象的概念引入到XML可以提高XML模式语言的建模能力.而现有的索引模式都不支持面向对象XML数据的查询,由此提出了一种基于面向对象XML数据的OOCtree（Object-Oriented compact tree）索引模式,它是一棵包含组级和元素级的两级双向树.组级提供简洁的结构概要和继承信息,可以在查询早期阶段裁剪大量的搜索空间;元素级提供详细的孩子父亲连接关系,可以快速地访问某元素的父亲,极大地提高了查询处理效率.     

Constructing suffix tree for gigabyte sequences with megabyte memory

Mammalian genomes are typically 3 Gbps (gibabase pairs) in size. The largest public database NCBI (National Center for Biotechnology Information (http://www.ncbi.nlm.nih.gov)) of DNA contains more than 20 Gbps. Suffix trees are widely acknowledged as a data structure to support exact/approximate sequence matching queries as well as repetitive structure finding efficiently when they can reside in main memory. But, it has been shown as difficult to handle long DNA sequences using suffix trees due to the so-called memory bottleneck problems. The most space efficient main-memory suffix tree construction algorithm takes nine hours and 45 GB memory space to index the human genome [S. Kurtz (1999)]. We show that suffix trees for long DNA sequences can be efficiently constructed on disk using small bounded main memory space and, therefore, all existing algorithms based on suffix trees can be used to handle long DNA sequences that cannot be held in main memory. We adopt a two-phase strategy to construct a suffix tree on disk: 1) to construct a diskbase suffix-tree without suffix links and 2) rebuild suffix links upon the suffix-tree being constructed on disk, if needed. We propose a new disk-based suffix tree construction algorithm, called DynaCluster, which shows O(nlogn) experimental behavior regarding CPU cost and linearity for I/O cost. DynaCluster needs 16 MB main memory only to construct more than 200 Mbps DNA sequences and significantly outperforms the existing disk-based suffix-tree construction algorithms using prepartitioning techniques in terms of both construction cost and query processing cost. We conducted extensive performance studies and report our findings in this paper.     

Path Summaries and Path Partitioning in Modern XML Databases

XML path summaries are compact structures representing all the simple parent-child paths of an XML document. Such paths have also been used in many works as a basis for partitioning the document’s content in a persistent store, under the form of path indices or path tables. We revisit the notions of path summaries and path-driven storage model in the context of current-day XML databases. This context is characterized by complex queries, typically expressed in an XQuery subset, and by the presence of efficient encoding techniques such as structural node identifiers. We review a path summary’s many uses for query optimization, and given them a common basis, namely relevant paths. We discuss summary-based tree pattern minimization and present some efficient summary-based minimization heuristics. We consider relevant path computation and provide a time- and memory-efficient computation algorithm. We combine the principle of path partitioning with the presence of structural identifiers in a simple path-partitioned storage model, which allows for selective data access and efficient query plans. This model improves the efficiency of twig query processing up to two orders of magnitude over the similar tag-partitioned indexing model. We have implemented the path-partitioned storage model and path summaries in the XQueC compressed database prototype [8]. We present an experimental evaluation of a path summary’s practical feasibility and of tree pattern matching in a path-partitioned store.     

An efficient index structure for XML based on generalized suffix tree

A novel index structure based on the generalized suffix tree (PIGST) is proposed. Combined with post lists, PIGST can answer both structural and content queries. The distinct paths in an XML collection are mapped into strings. The construction algorithm of the PIGST for the path strings is presented based on the modification and improvement of a well-known suffix tree construction algorithm that only requires linear time and space complexity. The query process merely needs m character comparisons for direct containment queries, where m is the length of a query string. An efficient processing method for the indirect containment queries that avoids the inefficient tree traversal operation is also presented. Experiments show that PIGST outperforms earlier approaches.     

Evaluation Techniques for Generalized Path Pattern Queries on XML Data

Finding the occurrences of structural patterns in XML data is a key operation in XML query processing. Existing algorithms for this operation focus almost exclusively on path patterns or tree patterns. Current applications of XML require querying of data whose structure is complex or is not fully known to the user, or integrating XML data sources with different structures. These applications have motivated recently the introduction of query languages that allow a partial specification of path patterns in a query. In this paper, we consider partial path queries, a generalization of path pattern queries, and we focus on their efficient evaluation under the indexed streaming evaluation model. Our approach explicitly deals with repeated labels (that is, multiple occurrences of the same label in a query). We show that partial path queries can be represented as rooted dags for which a topological ordering of the nodes exists. We present three algorithms for the efficient evaluation of these queries. The first one exploits a structural summary of data to generate a set of path patterns that together are equivalent to a partial path query. To evaluate these path patterns, we extend a previous algorithm for path-pattern queries so that it can work on path patterns with repeated labels. The second one extracts a spanning tree from the query dag, uses a stack-based algorithm to find the matches of the root-to-leaf paths in the tree, and merge-joins the matches to compute the answer. Finally, the third one exploits multiple pointers of stack entries and a topological ordering of the query dag to apply a stack-based holistic technique. We analyze our algorithms and perform extensive experimental evaluations. Our experimental results show that the holistic algorithm outperforms the other ones. Our approaches are the first ones to efficiently evaluate this class of queries in the indexed streaming model.     

Temporal XML: modeling, indexing, and query processing

In this paper we address the problem of modeling and implementing temporal data in XML. We propose a data model for tracking historical information in an XML document and for recovering the state of the document as of any given time. We study the temporal constraints imposed by the data model, and present algorithms for validating a temporal XML document against these constraints, along with methods for fixing inconsistent documents. In addition, we discuss different ways of mapping the abstract representation into a temporal XML document, and introduce TXPath, a temporal XML query language that extends XPath 2.0. In the second part of the paper, we present our approach for summarizing and indexing temporal XML documents. In particular we show that by indexing continuous paths, i.e., paths that are valid continuously during a certain interval in a temporal XML graph, we can dramatically increase query performance. To achieve this, we introduce a new class of summaries, denoted TSummary, that adds the time dimension to the well-known path summarization schemes. Within this framework, we present two new summaries: LCP and Interval summaries. The indexing scheme, denoted TempIndex, integrates these summaries with additional data structures. We give a query processing strategy based on TempIndex and a type of ancestor-descendant encoding, denoted temporal interval encoding. We present a persistent implementation of TempIndex, and a comparison against a system based on a non-temporal path index, and one based on DOM. Finally, we sketch a language for updates, and show that the cost of updating the index is compatible with real-world requirements.     

Answering XML Queries Using Path-Based Indexes: A Survey

The problem of answering XML queries using path-based indexes is to find efficient methods for accelerating the XML query with pre-designed index structures over the XML database. This problem received increasing interests and have been lucubrated in recent years. Regular path expression is the core of the XML query languages e.g., XPath and XQuery. Most of the state-of-the-art path-based XML indexes, therefore, hammer at how to efficiently answer the path-based XML queries. This paper surveys various approaches to indexing XML data proposed in the literature. We give a step by step analysis to show the evolution of index structures for XML path information, based on tree structures or more commonly, directed labeled graphs. For each approach, we first present the specific issue it aims to tackle, and then the proposed solution presented. Furthermore, construction, physical data storage and maintenance costs, are analyzed.     

Data storage practices and query processing in XML databases: A survey

With the rapid emergence of XML as a data exchange standard over the Web, storing and querying XML data have become critical issues. The two main approaches to storing XML data are (1) to employ traditional storage such as relational database, object-oriented database and so on, and (2) to create an XML-specific native storage. The storage representation affects the efficiency of query processing. In this paper, firstly, we review the two approaches for storing XML data. Secondly, we review various query optimization techniques such as indexing, labeling and join algorithms to enhance query processing in both approaches. Next, we suggest an indexing classification scheme and discuss some of the current trends in indexing methods, which indicate a clear shift towards hybrid indexing.     

一种基于s-DOM的XML文档索引算法

改造XML树模型是提高XML查询效率的重要方法。通过分析现有的索引算法,对XML树模型进行了改造,提出了基于Signature的索引策略(s-DOM)。采用该策略预处理XML文档可以大大缩小搜索范围,从而提高了查询的效率。     

一种适用连续不确定XML数据的索引

针对连续不确定XML数据概率阈值范围查询,提出一种新的CUXI索引树。该索引树的构建方法是借鉴U树对空间数据自顶向下递归构建索引树的思想,将连续不确定XML文档中具有相同父亲的叶子节点构建二维数据矩形,在聚类的基础上来构建相应的CUXI索引树,其中叶子节点存储连续不确定数据辅助信息。为了提高查询效率,对连续不确定数据制定了过滤策略,通过遍历索引树过滤掉不满足查询范围的子树。理论和实验结果表明,此索引技术可提高查询处理的性能。