Search

ABSTRACT We present a new method for computing temporal aggregation that uses a multidimensional index. The novelty of our method lies in mapping the start time and end time of […]

Spatial joins find all pairs of objects that satisfy a given spatial relationship. In spatial joins using indexes, original-space indexes such as the R-tree are widely used. An original-space indexis the one that indexes objects as represented in the original space. Since original-space indexes deal with extents of objects, it is relatively complex to optimize join algorithms using these indexes. On the other hand, transform-space indexes, which transform objects in the original space into points in the transform space and index them, deal only with points but no extents. Thus, optimization of join algorithms using these indexes can be relatively simple. However, the disadvantage of these join algorithms is that they cannot be applied to original-space indexes such as the R-tree. In this paper, we present a novel mechanism for achieving the best of these two types of algorithms. Specifically, we propose the new notion of the transform-space view and present the transform-space view join algorithm. The transform-space view is a virtual transform-space index based on an original-space index. It allows us to 'interpret' or 'view' an existing original-space index as a transform-space index with no space and negligible time overhead and without actually modifying the structure of the original-space index or changing object representation. The transform-space view join algorithm joins two original-space indexes in the transform space through the notion of the transform-space view. Through analysis and experiments, we verify the excellence of the transform-space view join algorithm. The transform-space view join algorithm always outperforms existing ones for all the data sets tested in terms of all three measures used: the one-pass buffer size (the minimum buffer size required for guaranteeing one disk access per page), the number of disk accesses for a given buffer size, and the wall clock time. Thus, it constitutes a lower-bound algorithm. We believe that the proposed transform-space view can be applied to developing various new spatial query processing algorithms in the transform space. Index Terms--Transform-space view, adaptive row major order, spatial join, corner transformation, databases.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.05.009 Byline: Young-Ho Park (a), Kyu-Young Whang (a), Byung Suk Lee (b), Wook-Shin Han (c) Keywords: XML; Inverted indexes; Partial match queries; Information retrieval Abstract: We propose XIR-Linear, a method for efficiently evaluating linear path expressions (LPEs) on large-scale heterogeneous XML documents using information retrieval (IR) techniques. LPEs are the primary form of XPath queries, and their evaluation techniques have been researched actively. XPath queries in their general form are partial match queries, and these queries are particularly useful for searching documents of heterogeneous schemas. Thus, XIR-Linear is geared for partial match queries expressed as LPEs. XIR-Linear has its basis on existing methods using relational tables (e.g., XRel, XParent), and drastically improves their efficiency using the inverted index technique. Specifically, it indexes the labels in label paths (i.e., sequences of node labels) like keywords in texts, and finds the label paths matching the LPE far more efficiently than string match used in the existing methods. We demonstrate the efficiency of XIR-Linear by comparing it with XRel and XParent using XML documents crawled from the Internet. The results show that XIR-Linear outperforms XRel and XParent by an order of magnitude with the performance gap widening as database size grows. Author Affiliation: (a) Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science and Technology (KAIST), 373-1, Koo-Sung Dong, Yoo-Sung Ku, Daejeon 305-701, Republic of Korea (b) Department of Computer Science, University of Vermont, Burlington, VT 05405, USA (c) Department of Computer Engineering, Kyungpook National University, Daegu 702-701, Republic of Korea Article History: Received 28 May 2004; Revised 9 May 2005; Accepted 9 May 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2004.10.012 Byline: Min-Jae Lee (a), Kyu-Young Whang (a), Wook-Shin Han (b), Il-Yeol Song (c) Keywords: Spatial join; Corner transformation; Databases Abstract: A transform-space index indexes spatial objects represented as points in the transform space. An advantage of a transform-space index is that optimization of spatial join algorithms using these indexes can be more formal. The authors earlier proposed the Transform-Based Spatial Join algorithm that joins two transform-space indexes. It renders global optimization easy with little overhead by utilizing the characteristics of the transform space. In particular, it allows us to globally determine the order of accessing disk pages, which makes a significant impact on the performance of joins. For this purpose, we use various space filling curves. In this paper, we propose a new space filling curve called the adaptive row major order (ARM order). The ARM order adaptively controls the order of accessing pages and significantly reduces the one-pass buffer size (the minimum buffer size required for guaranteeing one disk access per page) and the number of disk accesses for a given buffer size. Through analysis and experiments, we verify excellence of the ARM order when used with the Transform-Based Spatial Join. The Transform-Based Spatial Join with the ARM order always outperforms those with other conventional space filling curves in terms of both measures used: the one-pass buffer size and the number of disk accesses. Specifically, it reduces the one-pass buffer size by up to 25.9 times and the number of disk accesses by up to 2.11 times. We conclude that we achieve these results mainly due to global optimization of the order of accessing disk pages using an adaptive space filling curve. Author Affiliation: (a) Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science and Technology (KAIST), 373-1, Koo-Sung Dong, Yoo-Sung Ku, Daejeon 305-701, Republic of Korea (b) Department of Computer Engineering, Kyungpook National University, Sankyuk-Dong, Buk-Gu, Daegu 702-701, Republic of Korea (c) College of Information Science and Technology, Drexel University, Philadelphia, PA, USA Article History: Received 4 December 2003; Revised 18 October 2004; Accepted 18 October 2004

Prefetching is an effective method for minimizing the number of fetches between the client and the server in a database management system. In this paper, we formally define the notion of prefetching. We also formally propose new notions of the type-level access locality and type-level access pattern. The type-level access locality is a pheonomenon that repetitive patterns exist in the attributes referenced. The type-level access pattern is a pattern of attributes that are referenced in accessing the objects. We then develop an efficient capturing and prefetching policy based on this formal framework. Existing prefetching methods are based on object-level or page-level access patterns, which consist of object-ids or page-ids of the objects accessed. However, the drawback of these methods is that they work only when exactly the same objects or pages are accessed repeatedly. In contrast, even though the same objects are not accessed repeatedly, our technique effectively prefetches objects if the same attributes are referenced repeatedly, i.e., if there is type-level access locality. Many navigational applications in Object-Relational Database Management Systems (ORDBMSs) have type-level access locality. Therefore, our technique can be employed in ORDBMSs to effectively reduce the number of fetches, thereby significantly enhancing the performance. We also address issues in implementing the proposed algorithm. We have conducted extensive experiments in a prototype ORDBMS to show effectiveness of our algorithm. Experimental results using the 007 benchmark, a real GIS application, and an XML application show that our technique reduces the number of fetches by orders of magnitude and improves the elapsed time by several factors over on-demand fetching and context-based prefetching, which is a state-of-the-art prefetching method. These results indicate that our approach provides a new paradigm in prefetching that improves performance of navigational applications significantly and is a practical method that can be implemented in commercial ORDBMSs. Index Terms--Prefetching, type-level access patterns, type-level access locality, object-relational DBMSs.

In video-on-demand (VOD) systems, as the size of the buffer allocated to user requests increases, initial latency and memory requirements increase. Hence, the buffer size must be minimized. The existing static buffer allocation scheme, however, determines the buffer size based on the assumption that the system is in the fully loaded state. Thus, when the system is in a partially loaded state, the scheme allocates a buffer larger than necessary to a user request. This paper proposes a dynamic buffer allocation scheme that allocates to user requests buffers of the minimum size in a partially loaded state, as well as in the fully loaded state. The inherent difficulty in determining the buffer size in the dynamic buffer allocation scheme is that the size of the buffer currently being allocated is dependent on the number of and the sizes of the buffers to be allocated in the next service period. We solve this problem by the predict-and-enforce strategy, where we predict the number and the sizes of future buffers based on inertia assumptions and enforce these assumptions at runtime. Any violation of these assumptions is resolved by deferring service to the violating new user request until the assumptions are satisfied. Since the size of the current buffer is dependent on the sizes of the future buffers, it is represented by a recurrence equation. We provide a solution to this equation, which can be computed at the system initialization time for runtime efficiency. We have performed extensive analysis and simulation. The results show that the dynamic buffer allocation scheme reduces initial latency (averaged over the number of user request in service from one to the maximum capacity) to 1/29.4 ~ 1/11.0 of that for that static one and, by reducing the memory requirement, increases the number of concurrent user requests to 2.36 ~ 3.25 times that of the static one when averaged over the amount of system memory available. These results demonstrate that the dynamic buffer allocation scheme significantly improves the performance and capacity of VOD systems. Index Terms--VOD systems, dynamic buffer allocation, multimedia systems, buffer scheduling methods.

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through experiments. To the extent of authors' knowledge, the spatial join processing using corner transformation is new. In corner transformation, two regions in one file joined with two adjacent regions in the other file share a large common area. The proposed algorithm utilizes this property in order to reduce the number of disk accesses for spatial join. Experimental results show that the performance of the algorithm is generally better than that of the [R.sup.*]-tree based algorithm proposed by Brinkhoff et al. This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering. We also briefly mention that the join algorithm based on corner transformation has a nice property of being amenable to parallel processing. We believe that our result will provide a new insight towards transformation-based processing of spatial operations. Index Terms - Spatial join, GIS, spatial databases, corner transformation.