Conference Proceeding Article
The general notion of a metric space encompasses a diverse range of data types and accompanying similarity measures. Hence, metric search plays an important role in a wide range of settings, including multimedia retrieval, data mining, and data integration. With the aim of accelerating metric search, a collection of pivot-based indexing techniques for metric data has been proposed, which reduces the number of potentially expensive similarity comparisons by exploiting the triangle inequality for pruning and validation. However, no comprehensive empirical study of those techniques exists. Existing studies each offers only a narrower coverage, and they use different pivot selection strategies that affect performance substantially and thus render cross-study comparisons difficult or impossible. We offer a survey of existing pivot-based indexing techniques, and report a comprehensive empirical comparison of their construction costs, update efficiency, storage sizes, and similarity search performance. As part of the study, we provide modifications for two existing indexing techniques to make them more competitive. The findings and insights obtained from the study reveal different strengths and weaknesses of different indexing techniques, and offer guidance on selecting an appropriate indexing technique for a given setting.
Databases and Information Systems | Data Storage Systems
Data Management and Analytics
Proceedings of the VLDB Endowment: 43rd International conference, Munich Germany, 2017 August 28 -September 1
City or Country
CHEN, Lu; GAO, Yunjun; ZHENG, Baihua; JENSEN, Christian S.; YANG, Hanyu; and YANG, Keyu.
Pivot-based Metric Indexing. (2017). Proceedings of the VLDB Endowment: 43rd International conference, Munich Germany, 2017 August 28 -September 1. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3739
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.