共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
4.
5.
Moustafa A. Hammad Walid G. Aref Ahmed K. Elmagarmid 《The VLDB Journal The International Journal on Very Large Data Bases》2008,17(3):469-488
This paper introduces a class of join algorithms, termed W-join, for joining multiple infinite data streams. W-join addresses
the infinite nature of the data streams by joining stream data items that lie within a sliding window and that match a certain
join condition. In addition to its general applicability in stream query processing, W-join can be used to track the motion
of a moving object or detect the propagation of clouds of hazardous material or pollution spills over time in a sensor network
environment. We describe two new algorithms for W-join and address variations and local/global optimizations related to specifying
the nature of the window constraints to fulfill the posed queries. The performance of the proposed algorithms is studied experimentally
in a prototype stream database system, using synthetic data streams and real time-series data. Tradeoffs of the proposed algorithms
and their advantages and disadvantages are highlighted, given variations in the aggregate arrival rates of the input data
streams and the desired response times per query.
This is an extended version of the paper published in the Proceedings of the 15th International Conference on Scientific and
Statistical Database Management, SSDBM 2003, Boston, U.S.A., pp. 75–84. 相似文献
6.
Identification of all pairs of objects in a dataset whose similarity is not less than a specified threshold is of major importance for management, search, and analysis of data. Set similarity joins are commonly used to implement this operation; they scale to large datasets and are versatile to represent a variety of similarity notions. Most methods proposed so far present two main phases at a high level of abstraction: candidate generation producing a set of candidate pairs and verification applying the actual similarity measure to the candidates and returning the correct answer. Previous work has primarily focused on the reduction of candidates, where candidate generation presented the major effort to obtain better pruning results. Here, we propose an opposite approach. We drastically decrease the computational cost of candidate generation by dynamically reducing the number of indexed objects at the expense of increasing the workload of the verification phase. Our experimental findings show that this trade-off is advantageous: we consistently achieve substantial speed-ups as compared to known algorithms. 相似文献
7.
8.
结构连接的效率直接影响XML查询的性能。经典的Anc-Des-B+算法在判断双亲/孩子关系时跳过双亲节点的后裔(非孩子)节点的能力不强。为此,基于区间编码的思想提出一种改进的编码方法,把每个节点译码为六元组,并增加双亲节点的信息。给出的ZParent算法可以跳过孩子列表中所有不参与连接的元素节点,只需要扫描一次列表P和列表C,即可实现基于该编码的结构连接计算。实验结果表明,该方法具有较好的时间性能。 相似文献
9.
基于索引的XML查询技术研究 总被引:2,自引:0,他引:2
介绍了目前XML数据查询技术的研究现状,对主要的XML索引查询技术作了较深入的探讨,其中包括:基于路径索引的XML查询方法,如DataGuide、1-index、A(k)索引等;基于编码的XML索引查询方法,如Anc_Desc_B^+、XR树+XR-Stack算法等。文中对相关XML索引查询方法的优点和不足进行了分析。 相似文献
10.
连接操作是影响分布式查询性能的关键因素,数据存储是影响连接操作的重要因素.为了提高分布式系统的查询性能,通过研究数据之间的关系,提出一个关联数据分布树.利用该关联数据分布树来构造一系列的关联元组集合,然后按照各个站点的负载能力,把这些关联数据集合分配给相关站点.实验结果表明,当多个关系频繁的进行连接操作时,关联数据分布树能有效地提高整个分布式系统的查询性能. 相似文献
11.
The processing of XML queries can result in evaluation of various structural relationships. Efficient algorithms for evaluating ancestor-descendant and parent-child relationships have been proposed. Whereas the problems of evaluating preceding-sibling-following-sibling and preceding-following relationships are still open. In this paper, we studied the structural join and staircase join for sibling relationship. First, the idea of how to filter out and minimize unnecessary reads of elements using parent's structural information is introduced, which can be used to accelerate structural joins of parent-child and preceding-sibling-following-sibling relationships. Second, two efficient structural join algorithms of sibling relationship are proposed. These algorithms lead to optimal join performance: nodes that do not participate in the join can be judged beforehand and then skipped using B^+-tree index. Besides, each element list joined is scanned sequentially once at most. Furthermore, output of join results is sorted in document order. We also discussed the staircase join algorithm for sibling axes. Studies show that, staircase join for sibling axes is close to the structural join for sibling axes and shares the same characteristic of high efficiency. Our experimental results not only demonstrate the effectiveness of our optimizing techniques for sibling axes, but also validate the efficiency of our algorithms. As far as we know, this is the first work addressing this problem specially. 相似文献
12.
XML and other semi-structured data can be represented by a graph model. The paths in a data graph are used as a basic constructor of a query. Especially, by using patterns on paths, a user can formulate more expressive queries. Patterns in a path enlarge the search space of a data graph and current research for indexing semi-structured data focuses on reducing the search space. However, the existing indexes cannot reduce the search space when a data graph has some references.
In this paper, we introduce a partitioning technique for all paths in a data graph and an index graph which can effectively find appropriate path partitions for a path query with patterns. 相似文献
13.
Su-Cheng Haw Author Vitae Chien-Sing Lee Author Vitae 《Journal of Systems and Software》2009,82(6):1025-1035
Optimizing query processing is always a challenging task in the XML database community. Current state-of-the-art approaches focus mainly on simple query. Yet, as the usage of XML shifts towards the data-oriented paradigm, more and more complex query processing needs to be supported. In this paper, we present TwigX-Guide, a hybrid system, which takes advantage of the beautiful features of path summary in DataGuide and region encoding in TwigStack to improve complex query processing. Experimental results indicate that TwigX-Guide can process complex queries on an average 38% better than the TwigStack algorithm, 31% better than TwigINLAB, 11% better than TwigStackList and about 9% better than TwigStackXB in terms of execution time. 相似文献
14.
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. 相似文献
15.
有效支持XML结构化连接的索引——CATI 总被引:1,自引:0,他引:1
结构化连接的效率直接影响着XML查询的性能,目前对XML的结构化连接大多都是基于编码的方法.介绍了一种全新的有效支持XML结构化连接的树索引CATI(compact ancestor tree index)CATI的基本思想是,对于给定的一个祖先后代查询(A-D查询)或Twig查询,遍历XML文档,找出所有的祖先A的实例,用以建立CATI的主干;对于每个A实例,找出它的直接后代D的实例链接在它的后面.因为经典的结构连接算法Stack-Tree算法效率较高且使用较广,因此应用基于CATI的结构连接算法和基于Stack-Tree的结构连接算法就A-D查询和Twig查询做了大量实验.实验结果表明,基于CATI的结构化连接在一般查询情况下性能明显优于基于Stack-Tree的结构化连接. 相似文献
16.
为了更加有效实现XML文档的结构查询,加强结构连接操作的效率,提出一种新结构连接算法.该算法采用扩展的前缀编码方案,在编码中增加了type、index等字段以利于定位树中结点在祖先结点列表或者后裔结点列表中的位置.该算法通过将XML文档树转换成左孩子右兄弟树,并定位树中一个祖先元素的起始点下标和终结点下标来找到该祖先元素的后裔结点列表.算法时间复杂度分析表明了该算法比现有算法的性能更好. 相似文献
17.
每一个复杂的Twig查询都由线性Twig查询构成,有效地处理线性Twig查询显得非常重要。DM XML系统以国产DM5.6关系数据库为平台,融合结构映射和模型映射,实现独特的路径分区编码方案来存储XML数据。在系统中,线性Twig查询解析后,形成线性Twig查询的路径集,而该集合中的每一个路径可被唯一变换为关系数据库中整型主键的范围查询。实验结果显示,路径分区编码方案能加速线性Twig查询,它将为高效实现复杂Twig查询奠定基础。 相似文献
18.
NoSQL systems are increasingly adopted for Web applications requiring scalability that relational database systems cannot meet. Although NoSQL systems have not been designed to support joins, as they are applied to a wide variety of applications, the need to support joins has emerged. Furthermore, joins performed in NoSQL systems are generally similarity joins, rather than exact-match joins, which find similar pairs of records. Since Web applications often use the MapReduce framework, we develop a solution to perform similarity joins in NoSQL systems using the MapReduce framework. 相似文献
19.
基于关系数据库有效地实现RPE查询 总被引:5,自引:1,他引:5
各种XML查询语言的共同特点就是利用正则路径表达式(RPE)来导航XML文档的查询。本文结合我们提出的一种新的XML数据的关系存储模式,对有效地实现RPE查询的相关研究工作进行了总结,并提出了两个有效地实现包含连接的索引改进归并连接算法。算法采用索引定位技术、短路技术和预侦技术来减少连接代价。因此,不仅能够在当前上下文计算环境下有效地实现包含连接的计算,而且能够大量地避免包含连接中不必要的扫描和搜索。 相似文献
20.
如今对XML查询的优化是对XML的热点研究方向。其中的结构连接操作是XML数据库查询的主要操作。和关系数据库中的连接运算一样,结构连接顺序的选择是XML数据库查询优化的核心。文中主要通过对XML查询优化中各种选择连接顺序算法的研究,提出了一种优化的算法,在规模较大的XML查询中能够有效缩减搜索空间,提高效率。 相似文献