Browsing by Author "Manolopoulos, Yannis"

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Analysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectangles
    (1998-10-15) Faloutsos, Christos; Jagadish, H.V.; Manolopoulos, Yannis
    We give a closed-form expression for the average number of $n$-dimensional quadtree nodes (`pieces' or `blocks') required by an $n$-dimensional hyper-rectangle aligned with the axes. Our formula includes as special cases the formulae of previous efforts for 2-dimensional spaces \cite{Faloutsos92Analytical}. It also agrees with theoretical and empirical results that the number of blocks depends on the hyper-surface of the hyper-rectangle and not on its hyper-volume. The practical use of the derived formula is that it allows the estimation of the space requirements of the $n$-dimensional quadtree decomposition. Quadtrees are used extensively in 2-dimensional spaces (geographic information systems and spatial databases in general), as well in higher dimensionality spaces (as oct-trees for 3-dimensional spaces, e.g. in graphics, robotics and 3-dimensional medical images [Arya et al., 1994]. Our formula permits the estimation of the space requirements for data hyper-rectangles when stored in an index structure like a ($n$-dimensional) quadtree, as well as the estimation of the search time for query hyper-rectangles. A theoretical contribution of the paper is the observation that the number of blocks is a piece-wise linear function of the sides of the hyper-rectangle. (Also cross-referenced as UMIACS-TR-94-130)
  • Thumbnail Image
    Item
    Analysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectangles
    (1994) Faloutsos, Christos; Jagadish, H.V.; Manolopoulos, Yannis; ISR
    We give a closed-form expression for the average number of n- dimensional quadtree nodes (ieces' or locks') required by an n-dimensional hyper-rectangle aligned with the axes. Our formula includes as special cases the formulae of previous efforts for 2- dimensional spaces [8]. It also agrees with theoretical and empirical results that the number of blocks depends on the hyper- surface of the hyper-rectangle and not on its hyper-volume. The practical use of the derived formula is that it allows the estimation of the space requirements of the n-dimensional quadtree decomposition. Quadtrees are used extensively in 2- dimensional spaces (geographic information systems and spatial databases in general), as well in higher dimensionality spaces (as oct-trees for 3-dimensional spaces, e.g. in graphics, robotics and 3-dimensional medical images [2]). Our formula permits the estimation of the space requirements for data hyper- rectangles when stored in an index structure like a (n- dimensional) quadtree, as well as the estimation of the search time for query hyper-rectangles. A theoretical contribution of the paper is the observation that the number of blocks is a piece-wise linear function of the sides of the hyper-rectangle.
  • Thumbnail Image
    Item
    Experimenting with Pattern Matching Algorithms
    (1994) Manolopoulos, Yannis; Faloutsos, Christos; ISR
    Two new pattern matching algorithms based on the Boyer-Moore algorithm are presented. Their performance is compared to that of earlier relevant variants in terms of the number of character comparisons and the required running time by exhaustive simulation. Experimental results show the efficiency of both these two new algorithms.
  • Thumbnail Image
    Item
    Fast Subsequence Matching in Time-Series Data bases
    (1993) Faloutsos, Christos; Ranganathan, M.; Manolopoulos, Yannis; ISR
    We present an efficient indexing method to locate subsequences within a collection of sequences, such that the subsequences match a given (query) pattern within a specified tolerance. The idea is to map each data sequence into a small set of boxes in feature space. Then, these rectangles can be readily indexed using traditional spatial access methods, like the R*-tree [9]. More detailed, we use a sliding window over the data sequence and extract its features; the results is a trail in feature space. We propose an efficient and effective algorithm to divide such trail in sub-trails, which are subsequently represented by their Minimum Bounding Rectangles (MBRs). We also examine queries of varying lengths, and we show how to handle each case efficiently. We implemented our method and carried out experiments on synthetic and real data (stock price movements). We compared the method to sequential scanning, which is the only obvious competitor. The results were excellent: our method accelerated the search time from 3 times up to 100 times.
  • Thumbnail Image
    Item
    Fast Subsequence Matching in Time-Series Databases
    (1998-10-15) Faloutsos, Christos; Ranganathan, M.; Manolopoulos, Yannis
    We present an efficient indexing method to locate 1-dimensional subsequences within a collection of sequences, such that the subsequences match a given (query) pattern within a specified tolerance. The idea is to map each data sequence into a small set of multidimensional rectangles in feature space. Then, these rectangles can be readily indexed using traditional spatial access methods, like the R*-tree \cite{Beckmann90R}. In more detail, we use a sliding window over the data sequence and extract its features; the result is a trail in feature space. We propose an efficient and effective algorithm to divide such trails into sub-trails, which are subsequently represented by their Minimum Bounding Rectangles (MBRs). We also examine queries of varying lengths, and we show how to handle each case efficiently. We implemented our method and carried out experiments on synthetic and real data (stock price movements). We compared the method to sequential scanning, which is the only obvious competitor. The results were excellent: our method accelerated the search time from 3 times up to 100 times. Appeared in ACM SIGMOD 1994, pp 419-429. Given "Best Paper award" (Also cross-referenced as UMIACS-TR-93-131)