Continuous similarity search for evolving queries. Issue 3 (September 2016)

• Record Type: Journal Article
• Authors: Xu, Xiaoning; Gao, Chuancong; Pei, Jian; Wang, Ke; Al-Barakati, Abdullah
• Is Part Of: Knowledge and information systems. Volume 48:Issue 3(2016:Sep.)
• Page Start: 649
• Page End: 678
• Publication Date: 2016-09
• Subjects: Similarity search -- Data stream -- Evolving query; Expert systems (Computer science) -- Periodicals; Information storage and retrieval systems -- Periodicals; 006.33
• DOI: 10.1007/s10115-015-0892-x
• Languages: English
• ISSNs: 0219-1377

Abstract

Abstract In this paper, we study a novel problem of continuous similarity search for evolving queries. Given a set of objects, each being a set or multiset of items, and a data stream, we want to continuously maintain the top-k most similar objects using the lastn items in the stream as an evolving query. We show that the problem has several important applications. At the same time, the problem is challenging. We develop a filtering-based method and a hashing-based method. Our experimental results on both real data sets and synthetic data sets show that our methods are effective and efficient.