Article

How to improve the pruning ability of dynamic metric access methods

Authors:

Caetano Traina, Jr.,

Roberto Santos Filho,

Christos FaloutsosAuthors Info & Claims

CIKM '02: Proceedings of the eleventh international conference on Information and knowledge management

Pages 219 - 226

https://doi.org/10.1145/584792.584831

Published: 04 November 2002 Publication History

Abstract

Complex data retrieval is accelerated using index structures, which organize the data in order to prune comparisons between data during queries. In metric spaces, comparison operations can be specially expensive, so the pruning ability of indexing methods turns out to be specially meaningful. This paper shows how to measure the pruning power of metric access methods, and defines a new measurement, called "prunability," which indicates how well a pruning technique carries out the task of cutting down distance calculations at each tree level. It also presents a new dynamic access method, aiming to minimize the number of distance calculations required to answer similarity queries. We show that this novel structure is up to 3 times faster and requires less than 25% distance calculations to answer similarity queries, as compared to existing methods. This gain in performance is achieved by taking advantage of a set of global representatives. Although our technique uses multiple representatives, the index structure still remains dynamic and balanced.

References

[1]

S. Berchtold, D. A. Keim, H.-P. Kriegel, "The X-tree: An Index Structure for High-dimensional data," in VLDB 1996, pp. 28--39.]]

Digital Library

[2]

K. Beyer, J. Godstein, R. Ramakrishnan, U. Shaft, "When is "Nearest Neighbor" Meaningful?," in ICDT 1999, pp. 217--235.]]

Digital Library

[3]

T. Bozkaya and Z. M. Özsoyoglu, "Distance-Based Indexing for High-Dimensional Metric Spaces," in ACM SIGMOD 1997, pp. 357--368.]]

Digital Library

[4]

S. Brin, "Near neighbor search in large metric spaces," in VLDB 1995, pp. 574--584.]]

Digital Library

[5]

W. A. Burkhard and R. M. Keller, "Some Approaches to Best-Match File Searching," CACM, vol. 16, pp. 230--236, 1973.]]

Digital Library

[6]

K. Chakrabarti and S. Mehrotra, "The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces," in IEEE ICDE 1999, pp. 440--447.]]

Digital Library

[7]

P. Ciaccia, M. Patella, P. Zezula, "M-tree: An efficient access method for similarity search in metric spaces," in VLDB 1997, pp. 426--435.]]

Digital Library

[8]

C. Faloutsos, B. Seeger, A. J. M. Traina, C. Traina, Jr., "Spatial Join Selectivity Using Power Laws," in ACM SIGMOD 2000, pp. 177--188.]]

Digital Library

[9]

V. Gaede and O. Günther, "Multidimensional Access Methods," ACM Computing Surveys, vol. 30, pp. 170--231, 1998.]]

Digital Library

[10]

N. Katayama and S. i. Satoh, "The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries," in ACM SIGMOD 1997, pp. 369--380.]]

Digital Library

[11]

K.-I. D. Lin, H. V. Jagadish, C. Faloutsos, "The TV-Tree: An Index Structure for High-Dimensional Data," VLDB Journal, vol. 3, pp. 517--542, 1994.]]

Digital Library

[12]

R. F. Santos, Filho, A. J. M. Traina, C. Traina, Jr., C. Faloutsos, "Similarity Search without Tears: The OMNI Family of All-purpose Access Methods," in ICDE 2001, pp. 623--630.]]

Digital Library

[13]

C. Traina, Jr., A. J. M. Traina, C. Faloutsos, "Distance exponent : a new concept for selectivity estimation in metric trees," Research Paper CMU-CS-99-110, March 1999 1999.]]

[14]

C. Traina, Jr., A. J. M. Traina, B. Seeger, C. Faloutsos, "Slim-Trees: High Performance Metric Trees Minimizing Overlap Between Nodes," in EDBT 2000, pp. 51--65.]]

Digital Library

[15]

J. K. Uhlmann, "Satisfying General Proximity/Similarity Queries with Metric Trees," Information Processing Letter, vol. 40, pp. 175--179, 1991.]]

[16]

P. N. Yianilos, "Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces," in ACM/SIGACT-SIAM - SODA 1993, pp. 311--321.]]

Digital Library

Cited By

Razente HBarioni MSantos Sousa R(2020)A comprehensive analysis of delayed insertions in metric access methodsInformation Systems10.1016/j.is.2020.101492(101492)Online publication date: Jan-2020
https://doi.org/10.1016/j.is.2020.101492
Razente HSousa RBarioni M(2018)Metric Indexing Assisted by Short-Term MemoriesSimilarity Search and Applications10.1007/978-3-030-02224-2_9(107-121)Online publication date: 4-Oct-2018
https://doi.org/10.1007/978-3-030-02224-2_9
Oliveira PTraina CKaster D(2015)Improving the Pruning Ability of Dynamic Metric Access Methods with Local Additional Pivots and Anticipation of InformationAdvances in Databases and Information Systems10.1007/978-3-319-23135-8_2(18-31)Online publication date: 15-Aug-2015
https://doi.org/10.1007/978-3-319-23135-8_2
Show More Cited By

Index Terms

How to improve the pruning ability of dynamic metric access methods
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
  2. Information retrieval

Recommendations

Faster construction of ball-partitioning-based metric access methods
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied Computing

Most similarity search techniques for multimedia data is performed in metric spaces and with the aid of data structures known as metric access methods (MAM). Herein, we present three new node split strategies for M-tree and Slim-tree construction, the ...
Where are you heading, metric access methods?: a provocative survey
SISAP '10: Proceedings of the Third International Conference on SImilarity Search and APplications

In this paper the impact of the metric indexing paradigm on the real-world applications is discussed. We pose questions whether the priorities in research of metric access methods (MAMs) established in the past decades reflect the actual needs of ...
Dynamic skyline queries in metric spaces
EDBT '08: Proceedings of the 11th international conference on Extending database technology: Advances in database technology

Skyline query is of great importance in many applications, such as multi-criteria decision making and business planning. In particular, a skyline point is a data object in the database whose attribute vector is not dominated by that of any other ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '02: Proceedings of the eleventh international conference on Information and knowledge management

November 2002

704 pages

ISBN:1581134924

DOI:10.1145/584792

General Chair:
Charles Nicholas
University of Maryland Baltimore County
,
Program Chairs:
David Grossman
Illinois Institute of Technology
,
Konstantinos Kalpakis
University of Maryland Baltimore County
,
Sajda Qureshi
Erasmus University, Rotterdam
,
Han van Dissel
Erasmus University, Rotterdam
,
Len Seligman
The MITRE Corporation

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM02

Sponsor:

CIKM02: Eleventh ACM International Conference on Information and Knowledge Management

November 4 - 9, 2002

Virginia, McLean, USA

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
609
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Razente HBarioni MSantos Sousa R(2020)A comprehensive analysis of delayed insertions in metric access methodsInformation Systems10.1016/j.is.2020.101492(101492)Online publication date: Jan-2020
https://doi.org/10.1016/j.is.2020.101492
Razente HSousa RBarioni M(2018)Metric Indexing Assisted by Short-Term MemoriesSimilarity Search and Applications10.1007/978-3-030-02224-2_9(107-121)Online publication date: 4-Oct-2018
https://doi.org/10.1007/978-3-030-02224-2_9
Oliveira PTraina CKaster D(2015)Improving the Pruning Ability of Dynamic Metric Access Methods with Local Additional Pivots and Anticipation of InformationAdvances in Databases and Information Systems10.1007/978-3-319-23135-8_2(18-31)Online publication date: 15-Aug-2015
https://doi.org/10.1007/978-3-319-23135-8_2
Jin SKim OFeng W(2013)MX-tree: A Double Hierarchical Metric Index with Overlap ReductionComputational Science and Its Applications – ICCSA 201310.1007/978-3-642-39640-3_42(574-589)Online publication date: 2013
https://doi.org/10.1007/978-3-642-39640-3_42
Cordeiro RFaloutsos CTraina Júnior CCordeiro RFaloutsos CTraina Júnior C(2013)Related Work and ConceptsData Mining in Large Sets of Complex Data10.1007/978-1-4471-4890-6_2(7-20)Online publication date: 11-Jan-2013
https://doi.org/10.1007/978-1-4471-4890-6_2
Carélo CPola ICiferri RTraina ATraina CCiferri C(2011)Slicing the metric space to provide quick indexing of complex data in the main memoryInformation Systems10.1016/j.is.2010.06.00436:1(79-98)Online publication date: Mar-2011
https://doi.org/10.1016/j.is.2010.06.004
Florez OQi XOcsa A(2009)MOBHRGProceedings of the 2009 IEEE International Conference on Acoustics, Speech and Signal Processing10.1109/ICASSP.2009.4959788(1133-1136)Online publication date: 19-Apr-2009
https://dl.acm.org/doi/10.1109/ICASSP.2009.4959788
Celik C(2008)Effective Use of Space for Pivot-Based Metric Indexing StructuresProceedings of the First International Workshop on Similarity Search and Applications (sisap 2008)10.1109/SISAP.2008.22(113-120)Online publication date: 11-Apr-2008
https://dl.acm.org/doi/10.1109/SISAP.2008.22
Celik C(2008)Effective use of space for pivot-based metric indexing structures2008 IEEE 24th International Conference on Data Engineering Workshop10.1109/ICDEW.2008.4498351(402-409)Online publication date: Apr-2008
https://doi.org/10.1109/ICDEW.2008.4498351
Venkateswaran JKahveci TJermaine CLachwani D(2008)Reference-based indexing for metric spaces with costly distance measuresThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-007-0062-117:5(1231-1251)Online publication date: 1-Aug-2008
https://dl.acm.org/doi/10.1007/s00778-007-0062-1
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents