Nature of Computation and Communication. International Conference, ICTCC 2014, Ho Chi Minh City, Vietnam, November 24-25, 2014, Revised Selected Papers

Research Article

Efficient -Nearest Neighbor Search for Static Queries over High Speed Time-Series Streams

Download
283 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-15392-6_9,
        author={Bui Giao and Duong Anh},
        title={Efficient -Nearest Neighbor Search for Static Queries over High Speed Time-Series Streams},
        proceedings={Nature of Computation and Communication. International Conference, ICTCC 2014, Ho Chi Minh City, Vietnam, November 24-25, 2014, Revised Selected Papers},
        proceedings_a={ICTCC},
        year={2015},
        month={2},
        keywords={
                    -NN search Streaming time-series Multi-scale filtering Multi-resolution index structure Static query},
        doi={10.1007/978-3-319-15392-6_9}
    }
    
  • Bui Giao
    Duong Anh
    Year: 2015
    Efficient -Nearest Neighbor Search for Static Queries over High Speed Time-Series Streams
    ICTCC
    ICST
    DOI: 10.1007/978-3-319-15392-6_9
Bui Giao1,*, Duong Anh1,*
  • 1: Ho Chi Minh City University of Technology
*Contact email: giao.bc@cb.sgu.edu.vn, dtanh@cse.hcmut.edu.vn

Abstract

In this paper, we propose a solution to the multi-step -nearest neighbor (NN) search. The method is the reduced tolerance-based -NN search for static queries in streaming time-series. A multi-scale filtering technique combined with a multi-resolution index structure is used in the method. We compare the proposed method to the traditional multi-step NN search in terms of the CPU search time and the number of distance function calls in the post-processing step. The results reveal that the reduced tolerance-based -NN search outperforms the traditional -NN search. Besides, applying multi-threading to the proposed method enables the system to have a fast response to high speed time-series streams for the -NN search of static queries.