We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
MSQL: efficient similarity search in metric spaces using SQL.
- Authors
Lu, Wei; Hou, Jiajia; Yan, Ying; Zhang, Meihui; Du, Xiaoyong; Moscibroda, Thomas
- Abstract
Similarity search is a primitive operation that arises in a large variety of database applications. Typical examples include identifying articles with similar titles, finding similar images and music in a large digital object repository, etc. While there exist a wide spectrum of access methods for similarity queries in metric spaces, a practical solution that can be fully supported by existing RDBMS with high efficiency still remains an open problem. In this paper, we present MSQL, a practical solution for answering similarity queries in metric spaces fully using SQL. To the best of our knowledge, MSQL enables users to find similar objects by submitting SELECT-FROM-WHERE statements only. MSQL provides a uniform indexing scheme based on a standard built-in $$B^+$$ -tree index, with the ability to accelerate the query processing using index seek. Various query optimization techniques are incorporated in MSQL to significantly reduce CPU and I/O cost. We deploy MSQL on top of PostgreSQL. Extensive experiments on various real data sets demonstrate MSQL's benefits, performing up to two orders of magnitude faster than existing domain-specific SQL-based solutions and being comparable to native solutions.
- Subjects
METRIC spaces; DATA analysis; ALGORITHMS
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2017, Vol 26, Issue 6, p829
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-017-0481-6