Closest pairs search over data stream

��-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 dy...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHU, Rui Zhu, WANG, Bin, YANG, Xiaochun, ZHENG, Baihua
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2024
Subjects:
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
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-10100
record_format dspace
spelling sg-smu-ink.sis_research-101002024-08-01T15:07:15Z Closest pairs search over data stream ZHU, Rui Zhu WANG, Bin YANG, Xiaochun ZHENG, Baihua ��-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. 2024-06-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9097 info:doi/10.1145/3617326 https://ink.library.smu.edu.sg/context/sis_research/article/10100/viewcontent/3617326_vor.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Streaming Data ��-Closest Pair Search Partition Cube Databases and Information Systems
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Streaming Data
��-Closest Pair Search
Partition
Cube
Databases and Information Systems
spellingShingle Streaming Data
��-Closest Pair Search
Partition
Cube
Databases and Information Systems
ZHU, Rui Zhu
WANG, Bin
YANG, Xiaochun
ZHENG, Baihua
Closest pairs search over data stream
description ��-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.
format text
author ZHU, Rui Zhu
WANG, Bin
YANG, Xiaochun
ZHENG, Baihua
author_facet ZHU, Rui Zhu
WANG, Bin
YANG, Xiaochun
ZHENG, Baihua
author_sort ZHU, Rui Zhu
title Closest pairs search over data stream
title_short Closest pairs search over data stream
title_full Closest pairs search over data stream
title_fullStr Closest pairs search over data stream
title_full_unstemmed Closest pairs search over data stream
title_sort closest pairs search over data stream
publisher Institutional Knowledge at Singapore Management University
publishDate 2024
url https://ink.library.smu.edu.sg/sis_research/9097
https://ink.library.smu.edu.sg/context/sis_research/article/10100/viewcontent/3617326_vor.pdf
_version_ 1814047730400493568