Article

M-tree: An Efficient Access Method for Similarity Search in Metric Spaces

Authors:

Paolo Ciaccia,

Marco Patella,

Pavel ZezulaAuthors Info & Claims

VLDB '97: Proceedings of the 23rd International Conference on Very Large Data Bases

Pages 426 - 435

Published: 25 August 1997 Publication History

Abstract

No abstract available.

References

[1]

{AFS93} Rakesh Agrawal, Christos Faloutsos, Arun N. Swami: Efficient Similarity Search In Sequence Databases. FODO 1993: 69-84.

Digital Library

Google Scholar

[2]

{BKK96} Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39.

Digital Library

Google Scholar

[3]

{BKSS90} Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331.

Digital Library

Google Scholar

[4]

{BO97} Tolga Bozkaya, Z. Meral Özsoyoglu: Distance-Based Indexing for High-Dimensional Metric Spaces. SIGMOD Conference 1997: 357-368.

Digital Library

Google Scholar

[5]

{Bri95} Sergey Brin: Near Neighbor Search in Large Metric Spaces. VLDB 1995: 574-584.

Digital Library

Google Scholar

[6]

{Chi94} Tzi-cker Chiueh: Content-Based Image Indexing. VLDB 1994: 582-593.

Digital Library

Google Scholar

[7]

{FEF+94} Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz: Efficient and Effective Querying by Image Content. J. Intell. Inf. Syst. 3(3/4): 231-262(1994).

Digital Library

Google Scholar

[8]

{FL95} Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174.

Digital Library

Google Scholar

[9]

{FRM94} Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos: Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994: 419-429.

Digital Library

Google Scholar

[10]

{Gut84} Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57.

Digital Library

Google Scholar

[11]

{HNP95} Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573.

Digital Library

Google Scholar

[12]

{JD88} Anil K. Jain, Richard C. Dubes: Algorithms for Clustering Data. Prentice-Hall 1988.

Digital Library

Google Scholar

[13]

{RKV95} Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79.

Google Scholar

[14]

{SRF87} Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518.

Digital Library

Google Scholar

[15]

{Uhl91} Jeffrey K. Uhlmann: Satisfying General Proximity/Similarity Queries with Metric Trees. Inf. Process. Lett. 40(4): 175- 179(1991).

Crossref

Google Scholar

[16]

{VM95} Michael Vassilakopoulos, Yannis Manolopoulos: Dynamic Inverted Quadtree: A Structure for Pictorial Databases. Inf. Syst. 20(6): 483-500(1995).

Digital Library

Google Scholar

[17]

{WBKW96} Erling Wold, Thom Blum, Douglas Keislar, James Wheaton: Content-Based Classification, Search, and Retrieval of Audio. IEEE MultiMedia 3: 27-36(1996).

Digital Library

Google Scholar

[18]

{ZCR96} P. Zezula, P. Ciaccia, and F. Rabitti. M-tree: A dynamic index for similarity queries in multimedia databases. TR 7, HERMES ESPRIT LTR Project, 1996. Available at URL http://www.ced.tuc.gr/hermes/.

Google Scholar

Cited By

View all

Zhu YMa RZheng BKe XChen LGao Y(2024)GTS: GPU-based Tree Index for Fast Similarity SearchProceedings of the ACM on Management of Data10.1145/36549452:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654945
Lampropoulos KZardbani FMamoulis NKarras P(2023)Adaptive Indexing in High-Dimensional Metric SpacesProceedings of the VLDB Endowment10.14778/3603581.360359216:10(2525-2537)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.14778/3603581.3603592
Azizi IEchihabi KPalpanas T(2023)ELPIS: Graph-Based Similarity Search for Scalable Data ScienceProceedings of the VLDB Endowment10.14778/3583140.358316616:6(1548-1559)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.14778/3583140.3583166
Show More Cited By

Recommendations

M⁺-tree: a new dynamical multidimensional index for metric spaces
ADC '03: Proceedings of the 14th Australasian database conference - Volume 17

In this paper, we propose a new metric index, called M⁺ -tree, which is a tree dynamically organized for large datasets in metric spaces. The proposed M⁺-tree takes full advantages of M-tree and MVP-tree, with a new concept called key dimension, which ...
Naq-tree: effective index structure for similarity search in high dimensional space
NM-Tree: Flexible Approximate Similarity Search in Metric and Non-metric Spaces
DEXA '08: Proceedings of the 19th international conference on Database and Expert Systems Applications

So far, an efficient similarity search in multimedia databases has been carried out by metric access methods (MAMs), where the utilized similarity measure had to satisfy the metric properties (reflexivity, non-negativity, symmetry, triangle inequality). ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

VLDB '97: Proceedings of the 23rd International Conference on Very Large Data Bases

August 1997

593 pages

ISBN:1558604707

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 25 August 1997

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

407
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhu YMa RZheng BKe XChen LGao Y(2024)GTS: GPU-based Tree Index for Fast Similarity SearchProceedings of the ACM on Management of Data10.1145/36549452:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654945
Lampropoulos KZardbani FMamoulis NKarras P(2023)Adaptive Indexing in High-Dimensional Metric SpacesProceedings of the VLDB Endowment10.14778/3603581.360359216:10(2525-2537)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.14778/3603581.3603592
Azizi IEchihabi KPalpanas T(2023)ELPIS: Graph-Based Similarity Search for Scalable Data ScienceProceedings of the VLDB Endowment10.14778/3583140.358316616:6(1548-1559)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.14778/3583140.3583166
Ranjan RGrover SMedya SChakravarthy VSabharwal YRanu SKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)GREEDProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601906(22518-22530)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601906
Zhu YChen LGao YZheng BWang P(2022)DESIREProceedings of the VLDB Endowment10.14778/3547305.354731715:10(2121-2133)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.14778/3547305.3547317
Echihabi KFatourou PZoumpatianos KPalpanas TBenbrahim H(2022)Hercules against data series similarity searchProceedings of the VLDB Endowment10.14778/3547305.354730815:10(2005-2018)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.14778/3547305.3547308
Echihabi KZoumpatianos KPalpanas T(2021)New trends in high-D vector similarity searchProceedings of the VLDB Endowment10.14778/3476311.347640714:12(3198-3201)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.14778/3476311.3476407
Gudmundsson JHorton MPfeifer JSeybold M(2021)A Practical Index Structure Supporting Fréchet Proximity Queries among TrajectoriesACM Transactions on Spatial Algorithms and Systems10.1145/34601217:3(1-33)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1145/3460121
Wang SSun YBao Z(2020)On the efficiency of K-means clusteringProceedings of the VLDB Endowment10.14778/3425879.342588714:2(163-175)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.14778/3425879.3425887
Tran LMun MShahabi C(2020)Real-time distance-based outlier detection in data streamsProceedings of the VLDB Endowment10.14778/3425879.342588514:2(141-153)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.14778/3425879.3425885
Show More Cited By

View Options

View options

Get Access

Login options

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

Abstract

References

Cited By

Recommendations

M+-tree: a new dynamical multidimensional index for metric spaces

Naq-tree: effective index structure for similarity search in high dimensional space

NM-Tree: Flexible Approximate Similarity Search in Metric and Non-metric Spaces

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations

M⁺-tree: a new dynamical multidimensional index for metric spaces