Institute for Systems Research

Permanent URI for this communityhttp://hdl.handle.net/1903/4375

Browse

Subject: search.filters.subject.database

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Efficient Retrieval of Similar Time Sequences Under Time Warping
    (1997) Yi, B.; Jagadish, H.V.; Faloutsos, Christos; Faloutsos, Christos; ISR
    Fast similarity searching in large time-sequence databases has attracted a lot of research interest. All of them use the Euclidean distance ($L_2$), or some variation of $L_p$ metric. $L_p$ metrics lead to efficient indexing, thanks to feature extraction (e.g., by keeping the first few DFT coefficients) and subsequent use of fast spatial access methods for the points in feature space. In this work we examine a popular, field-tested dissimilarity function, the "time warping" distance function which permits local accelerations and decelerations in the rate of the signals or sequences. This function is natural and suitable for several applications, like matching of voice, audio and medical signals (e.g., electrocardiograms). However, from the indexing viewpoint it presents two major challenges: (a) it does not lead to any natural "features", precluding the use of spatial access methods (b) it is quadratic ($O(len_1 * len_2)$) on the length of the sequences involved. Here we show how to overcome both problems: for the former, we propose using a modification of the so-called "FastMap", to map sequences into points, trading off a tiny amount of "recall" (typically zero) for large gains in speed. For the latter, we provide a fast, linear test, to help us discard quickly many of the false alarms that FastMap will typically introduce. Using both ideas in cascade, our proposed method achieved up to 7.8-time speed-up over the straightforward sequential scanning, on both read and synthetic datasets.
  • Thumbnail Image
    Item
    Design and Evaluation of Incremental Data Structures and Algorithms for Dynamic Query Interfaces
    (1997) Tanin, Egemen; Beigel, Richard; Shneiderman, Ben; ISR
    Dynamic query interfaces (DQI) are a recently developed database access mechanism that provides continuous real-time feedback to the user during query formulation. Previous work shows that DQI are an elegant and powerful interface to small databases. Unfortunately, when applied to large databases, previous DQI algorithms slow to a crawl. We present a new incremental approach to DQI algorithms that works well with large databases, both in theory and in practice.