Closest pairs search over data stream

• Main Authors: ZHU, Rui Zhu, WANG, Bin, YANG, Xiaochun, ZHENG, Baihua
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Streaming Data; ��-Closest Pair Search; Partition; Cube; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/9097; https://ink.library.smu.edu.sg/context/sis_research/article/10100/viewcontent/3617326_vor.pdf
• Institution: Singapore Management University

��-closest pair (KCP for short) search is a fundamental problem in database research. Given a set of��-dimensional streaming data S, KCP search aims to retrieve �� pairs with the shortest distances between them. While existing works have studied continuous 1-closest pair query (i.e., �� = 1) over dynamic data environments, which allow for object insertions/deletions, they require high computational costs and cannot easily support KCP search with �� > 1. This paper investigates the problem of KCP search over data stream, aiming to incrementally maintain as few pairs as possible to support KCP search with arbitrarily ��. To achieve this, we introduce the concept of NNS (short for Nearest Neighbour pair-Set), which consists of all the nearest neighbour pairs and allows us to support KCP search via only accessing O (��) objects. We further observe that in most cases, we only need to use a small portion of NNS to answer KCP search as typically �� ≪ ��. Based on this observation, we propose TNNS (short for Threshold-based NN pair Set), which contains a small number of high-quality NN pairs, and a partition named ��-DLBP (short for ��-Distance Lower-Bound based Partition) to organize objects, with �� being an integer significantly smaller than ��. ��-DLBP organizes objects using up to O (log �� �� ) partitions and is able to support the construction and update of TNNS efficiently.