1,720,998 research outputs found
Hybrid hierarchical motion estimation under illumination variations
No full textA hybrid hierarchical motion estimation method is presented. Selective application of some devised dynamic image models according to the pyramid level results in fast and effective motion estimation in the presence of complex changes in illumination
Efficient time-series subsequence matching using duality in constructing windows
No full textIn this paper, we propose a new subsequence matching method, Dual Match. Dual Match exploits duality in constructing windows and significantly improves performance. Dual Match divides data sequences into disjoint windows and the query sequence into sliding windows, and thus, is a dual approach of the one by Faloutsos et al. (Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, Washington, 1994, pp. 419-429.) (FRM in short), which divides data sequences into sliding windows and the query sequence into disjoint windows. FRM causes a lot of false alarms (i.e., candidates that do not qualify) by storing minimum bounding rectangles rather than individual points representing windows to save storage space for the index. Dual Match solves this problem by directly storing points without incurring excessive storage overhead. Experimental results show that, in most cases, Dual Match provides large improvement both in false alarms and performance over FRM given the same amount of storage space. In particular, for low selectivities (less than 10(-4)), Dual Match significantly improves performance up to 430-fold. On the other hand, for high selectivities (more than 10(-2)), it shows a very minor degradation (less than 29%). For selectivities in between (10(-4)-10(-2)), Dual Match shows performance slightly better than that of FRM. Overall, these results indicate that our approach provides a new paradigm in subsequence matching that improves performance significantly in large database applications. (C) 2001 Elsevier Science Ltd. All rights reserved
PrefetchGuide: capturing navigational access patterns for prefetching in client/server object-oriented/object-relational DBMSs
No full textIn prefetching, the objects that are expected to be accessed in the future are fetched from the server to the client in advance. Prefetching reduces the number of round-trips and increases the system performance. To prefetch object effectively, we need to correctly predict the future navigational patterns. In this paper, we propose the PrefetchGuide, a novel data structure that captures the navigational access patterns. We also formally define the notion of the attribute access log set and analyze the navigational access patterns that can be captured by the PrefetchGuide. We then present an prefetching algorithm using the PrefetchGuide. To show effectiveness of our algorithm, we have conducted extensive experiments in a prototype object-relational database management systems (DBMS). The results show that our method significantly outperforms the state-of-the-art prefetching method. These results indicate that our approach provides a practical method that can be implemented in commercial object-oriented/object-relationaI DBMSs. We believe our method is practically usable for object-oriented programmers and DBMS implementors. (C) 2002 Elsevier Science Inc. All rights reserved
Effective reference probability incorporating the effect of expiration time in Web cache
No full textWeb caching has become an important problem when addressing the performance issues in Web applications. The expiration time of the Web data item is useful a piece of information for performance enhancement in Web caching. In this paper, we introduce the notion of the effective reference probability that incorporates the. effect of expiration time for Web caching. For a formal approach, we propose the continuous independent reference model extending the existing independent reference model. Based on this model, we define formally the effective reference probability and derive it theoretically. By simply replacing the reference probability in the existing cache replacement algorithms with the effective reference probability, we can take the effect of expiration time into account. The results of performance experiments show that the replacement algorithms using the effective reference probability always outperform existing ones. In particular, when the cache fraction is 0.05 and data update is comparatively frequent (i.e., the update frequency is more than 1/10 of the reference frequency), the performance is enhanced by more than 30% in LRU-2 and 13% in Aggarwal's method. The results show that the effective reference probability significantly enhances the performance of Web caching when the expiration time is given
An aggregation algorithm using a multidimensional file in multidimensional OLAP
No full textAggregation is an operation that plays a key role in multidimensional OLAP (MOLAP). Existing aggregation methods in MOLAP have been proposed for file structures such as multidimensional arrays. These file structures are suitable for data with uniform distributions, but do not work well with skewed distributions. In this paper, we consider an aggregation method that uses dynamic multidimensional files adapting to skewed distributions. In these multidimensional files, the sizes of page regions vary according to the data density in these regions, and the pages that belong to a larger region are accessed multiple times while computing aggregations. To solve this problem, we first present an aggregation computation model that uses the new notions of disjoint-inclusive partition and induced space filling curves. Based on this model, we then present a dynamic aggregation algorithm. Using these notions, the algorithm allows us to maximize the effectiveness of the buffer-we control the page access order in such a way that a page being accessed can reside in the buffer until the next access. We have conducted experiments to show the effectiveness of our approach. Experimental results for a real data set show that the algorithm reduces the number of disk accesses by up to 5.09 times compared with a naive algorithm. The results further show that the algorithm achieves a near optimal performance (i.e., normalized I/O = 1.01) with the total main memory (needed for the buffer and the result table) less than 1.0% of the database size. We believe our work also provides an excellent formal basis for investigating further issues in computing aggregations in MOLAR (C) 2003 Published by Elsevier Science Inc
A top-down approach for density-based clustering using multidimensional indexes
No full textClustering on large databases has been studied actively as all increasing number of applications involve huge amount of data. In this paper, we propose all efficient top-down approach for density-based clustering, which is based on the density information stored in index nodes of a multidimensional index. We first provide a formal definition of the cluster based on the concept of region contrast partition. Based on this notion, we propose a novel top-down clustering algorithm, which improves the efficiency through branch-and-bound pruning. For this pruning, we present a technique for determining the bounds based oil sparse and dense internal regions and formally prove the correctness of the bounds. Experimental results show that the proposed method reduces the elapsed time by up to 96 times compared with that of BIRCH, which is a well-known clustering method. The results also show that the performance improvement becomes more marked as the size of the database increases. (C) 2003 Elsevier Inc. All rights reserved
Scaling-invariant boundary image matching using time-series matching techniques
No full textIn this paper we address the scaling-invariant problem in boundary image matching. Supporting the invariant property against the horizontal or vertical image scaling is very important in boundary image matching to get more intuitive and more accurate matching results. We note that supporting the scaling-invariance is a challenging problem since the number of possible scaling factors is infinite. In this paper we solve this scaling-invariant problem in the time-series domain instead of the image domain. We first define the scaling distance between boundary images and present an interpolation-based method to compute that distance in the time-series domain. We then propose the notion of scaling-invariant distance between boundary images, which is the minimum distance among all possible scaling distances of two images. We use this scaling-invariant distance as the similarity measure in scaling-invariant boundary image matching. Computing the scaling-invariant distance, however, is very difficult or almost impossible, and we instead present how to compute its upper and lower bounds on the given scaling range. Using these lower and upper bounds we also propose divide-and-conquer algorithms to determine the scaling-invariant similarity between boundary images. Finally, we propose sequential and index-based matching methods, respectively, that perform the scaling-invariant boundary image matching correctly. Experimental results show that our scaling-invariant matching gets more intuitive results than the previous (scaling-variant) matching. In addition, compared with the simple sequential scan, our index-based matching method improves performance by one or two orders of magnitude. (C) 2010 Elsevier B.V. All rights reserved
Navigation stability: A new isolation level in ORDBMSs
No full textIn order to enhance the performance, many database management systems (DBMSs) execute transactions at isolation level 2 rather than at isolation level 3, the strict two phase locking, even if it sacrifices consistency to a certain degree. Cursor stability, a variant of isolation level 2 in relational DBMs (RDBMSs), has been widely used as a useful technique for obtaining concurrency achievable at level 2 without much sacrificing consistency. However, cursor stability is much less usable in object-relational DBMSs (ORDBMSs) because navigational applications in ORDBMSs can suffer from critical inconsistency problems such as dangling pointers, lost updates, and reading inconsistent complex objects. In this paper, we propose a new isolation level, navigation stability, that prevents the inconsistency problems of cursor stability for navigational applications, while avoiding significant degradation of the concurrency of level 3. First, we analyze the inconsistency problems of cursor stability for navigational applications. Second, we define navigation stability as an extension of cursor stability and show that it solves those inconsistency problems of cursor stability in ORDBMSs. Third, through extensive simulation, we show that navigation stability significantly enhances the performance compared with level 3. For workloads consisting of transactions of long duration, compared with level 3, the throughput of navigation stability is enhanced by up to 200%; the average response time reduced by as much as 55%; and the abort ratio reduced by as much as 77%. From these results, we conclude that navigation stability is a useful isolation level in ORDBMSs that can be used in place of isolation level 3 to improve the performance and concurrency without significant sacrifice of consistency
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
