TY - JOUR
T1 - Indexing Metric Spaces for Exact Similarity Search
AU - Chen, Lu
AU - Gao, Yunjun
AU - Song, Xuan
AU - Li, Zheng
AU - Zhu, Yifan
AU - Miao, Xiaoye
AU - Jensen, Christian S.
N1 - Funding Information:
This work was supported in part by the NSFC under Grants No. (62102351, 62025206 and 61972338), the Zhejiang Provincial Natural Science Foundation under Grant No. LR21F020005 and the DIREC center project.
Publisher Copyright:
© 2022 Association for Computing Machinery.
PY - 2022/12/7
Y1 - 2022/12/7
N2 - With the continued digitization of societal processes, we are seeing an explosion in available data. This is referred to as big data. In a research setting, three aspects of the data are often viewed as the main sources of challenges when attempting to enable value creation from big data: volume, velocity, and variety. Many studies address volume or velocity, while fewer studies concern the variety. Metric spaces are ideal for addressing variety because they can accommodate any data as long as it can be equipped with a distance notion that satisfies the triangle inequality. To accelerate search in metric spaces, a collection of indexing techniques for metric data have been proposed. However, existing surveys offer limited coverage, and a comprehensive empirical study exists has yet to be reported. We offer a comprehensive survey of existing metric indexes that support exact similarity search: we summarize existing partitioning, pruning, and validation techniques used by metric indexes to support exact similarity search; we provide the time and space complexity analyses of index construction; and we offer an empirical comparison of their query processing performance. Empirical studies are important when evaluating metric indexing performance, because performance can depend highly on the effectiveness of available pruning and validation as well as on the data distribution, which means that complexity analyses often offer limited insights. This article aims at revealing strengths and weaknesses of different indexing techniques to offer guidance on selecting an appropriate indexing technique for a given setting, and to provide directions for future research on metric indexing.
AB - With the continued digitization of societal processes, we are seeing an explosion in available data. This is referred to as big data. In a research setting, three aspects of the data are often viewed as the main sources of challenges when attempting to enable value creation from big data: volume, velocity, and variety. Many studies address volume or velocity, while fewer studies concern the variety. Metric spaces are ideal for addressing variety because they can accommodate any data as long as it can be equipped with a distance notion that satisfies the triangle inequality. To accelerate search in metric spaces, a collection of indexing techniques for metric data have been proposed. However, existing surveys offer limited coverage, and a comprehensive empirical study exists has yet to be reported. We offer a comprehensive survey of existing metric indexes that support exact similarity search: we summarize existing partitioning, pruning, and validation techniques used by metric indexes to support exact similarity search; we provide the time and space complexity analyses of index construction; and we offer an empirical comparison of their query processing performance. Empirical studies are important when evaluating metric indexing performance, because performance can depend highly on the effectiveness of available pruning and validation as well as on the data distribution, which means that complexity analyses often offer limited insights. This article aims at revealing strengths and weaknesses of different indexing techniques to offer guidance on selecting an appropriate indexing technique for a given setting, and to provide directions for future research on metric indexing.
KW - indexing and querying
KW - metric similarity search
KW - Metric spaces
UR - http://www.scopus.com/inward/record.url?scp=85146492173&partnerID=8YFLogxK
U2 - 10.1145/3534963
DO - 10.1145/3534963
M3 - Journal article
AN - SCOPUS:85146492173
SN - 0360-0300
VL - 55
SP - 1
EP - 39
JO - ACM Computing Surveys
JF - ACM Computing Surveys
IS - 6
M1 - 3534963
ER -