Article

Free access

A cost model for similarity queries in metric spaces

Authors:

Pavel ZezulaAuthors Info & Claims

PODS '98: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 59 - 68

https://doi.org/10.1145/275487.275495

Published: 01 May 1998 Publication History

First page of PDF

References

[1]

N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R~-tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 A CM-SIGMOD International Conference on Management of Data, pages 322-331, Atlantic City, NJ, May 1990.

Digital Library

[2]

A, Belussi and (2. Faloutsos. Estimating the selectivity of spatial queries using the correlation fraetal dimension, In Proceedings of the 2Ist VLDB International Conference, pages 299-310, Zurich, Switzerland, September 1996.

Digital Library

[3]

S. Berchtold, C. BShm, D.A. Keim, and H.-P. Kriegel. A cost model for nearest neighbor search in highdimensional data space. In Proceedings of the 16th A CM Symposium on Principles of Database Systems (PODS'gT), pages 78-86, Tucson, AZ, May 1997.

Digital Library

[4]

T. Bozkaya and M. Ozsoyoglu. Distance-based indexing for high-dimensional metric spaces. In Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, pages 357-368, Tucson, AZ, May 1997.

Digital Library

[5]

T. Bozkaya, N. Yazdani, and M. Ozsoyoglu. Matching and indexing sequences of different lengths, in Proceedings of the 6th International Conference on Information and Knowledge Management (GIKM'97), Las Vegas, Nevada, November 1997.

Digital Library

[6]

S. Brin. Near neighbor search in large metric spaces. In Proceedings o,f the 21st VLDB International Conference, pages 574--584, Zurich, Switzerland, September 1995.

Digital Library

[7]

W. Chen and K. Aberer. Efficient querying on genomie databases by using metric space indexing techniques. In Ist International Workshop on Query Processing and Multimedia Issues in Distributed Systems (PMIDS'97), Toulouse, France, September 1997.

[8]

T. Chiueh. Content-based image indexing. In Proceedings of the 2Oth VLDB International Conference, pages 582-593, Santiago, Chile, September 1994.

Digital Library

[9]

P. Ciaccia and M. Patella. Bulk loading the M-tree. In Proceedings of the 9th Australasian Database Confer. ence (ADO'98), pages 15-26, Perth, Australia, February 1998.

[10]

P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the 23rd VLDB International Conference, pages 426--435, Athens, Greece, August 1997.

Digital Library

[11]

P. Ciaccia, M. Patella, and P. Zezula. Processing complex similarity queries with distance-based access methods. In Proceedings of the 6th EDBT International Conference, Valencia, Spain, March 1998.

Digital Library

[12]

C. Faloutsos and I. Kamel. Beyond uniformity and independence: Analysis of R-trees using the concept of fractal dimension. In Proceedings of the 18th A OM Symposium on Principles of Database Systems (PODS'94), pages 4-13, Minneapolis, MN, May 1994.

Digital Library

[13]

A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of the 198~ A GM SIGMOD International Conference on Management of Data, pages 47--57, Boston, MA, June 1984.

Digital Library

[14]

J.M. Hellerstein, j.F. Naughton, and A. Pfeffer. Generalized search trees for database systems. In Proceedings of the 21st VLDB International Conference, pages 562-- 573, Zurich, Switzerland, September 1995.

Digital Library

[15]

D.P. Huttenloeker, G.A. Klanderman, and W.3. Rueklidge. Comparing images using the Hausdortf distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(9):850--863, September 1993.

Digital Library

[16]

I. Kamel and C. Faloutsos. On packing R-trees. In Proceedings of the Second International Oonference on Information and Knowledge Management (GIKM'93), pages 490-499~ Washington, DG, November 1993.

Digital Library

[17]

D. Maio and D. Maltoni. A structural approach to fingerprint classification. In Proceedings of the 13th Inter. national Conference on Pattern Recognition, volume (3, pages 578-585, Wien, Austria, August 1996.

Digital Library

[18]

B, Mandelbrot, The Fractal Geometry of Nature. W,H,Freeman, New York, 1977.

[19]

A, Papadopoulos and Y. Manolopoulos. Performance of nearest-neighbor queries in R-trees. In Proceedings of the 6th IODT International Oonference, pages 394--408, Delphi~ Greece~ January 1997.

Digital Library

[20]

Y. Theodoridis and T. Sellis. A model for the prediction of R-tree performance. In Proceedings of the 15th A GM Symposium on Principles of Database Systems (PODS'96), pages 161-171, Montreal, Canada, June 1996,

Digital Library

Cited By

Wu CPeng Z(2024)Federated Trajectory Search via a Lightweight Similarity Computation FrameworkWeb and Big Data10.1007/978-981-97-2390-4_32(469-485)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-981-97-2390-4_32
Jiang NZhuang YChiu D(2023)An effective and efficient parallel large-scale cross-media retrieval in mobile cloud networkMultimedia Tools and Applications10.1007/s11042-023-16060-y83:5(13821-13850)Online publication date: 10-Jul-2023
https://doi.org/10.1007/s11042-023-16060-y
Leodolter MPlant CBrändle N(2023)Rotation invariant GPS trajectory miningGeoInformatica10.1007/s10707-023-00495-428:1(89-115)Online publication date: 8-Jun-2023
https://doi.org/10.1007/s10707-023-00495-4
Show More Cited By

Index Terms

A cost model for similarity queries in metric spaces

Recommendations

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 ...
An effective cost model for similarity queries in metric spaces
SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

This short paper presents an effective cost model to estimate the number of disk accesses (I/O cost) and the number of distance calculations (CPU cost) to process similarity range queries over data indexed by metric access methods.
Effective Hausdorff Dimension in General Metric Spaces

We introduce the concept of effective dimension for a wide class of metric spaces whose metric is not necessarily based on a measure. Effective dimension was defined by Lutz (Inf. Comput., 187(1), 49---79, 2003) for Cantor space and has also been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '98: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

May 1998

286 pages

ISBN:0897919963

DOI:10.1145/275487

Chairmen:
Alberto Mendelson
Univ. of Toronto
,
Jan Paredaens
Univ. of Antwerp

Copyright © 1998 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: 01 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS98

Sponsor:

SIGMOD/PODS98: Special Interest Group on Management of Data

June 1 - 4, 1998

Washington, Seattle, USA

Acceptance Rates

PODS '98 Paper Acceptance Rate 28 of 119 submissions, 24%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

139
Total Citations
View Citations
755
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)7

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu CPeng Z(2024)Federated Trajectory Search via a Lightweight Similarity Computation FrameworkWeb and Big Data10.1007/978-981-97-2390-4_32(469-485)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-981-97-2390-4_32
Jiang NZhuang YChiu D(2023)An effective and efficient parallel large-scale cross-media retrieval in mobile cloud networkMultimedia Tools and Applications10.1007/s11042-023-16060-y83:5(13821-13850)Online publication date: 10-Jul-2023
https://doi.org/10.1007/s11042-023-16060-y
Leodolter MPlant CBrändle N(2023)Rotation invariant GPS trajectory miningGeoInformatica10.1007/s10707-023-00495-428:1(89-115)Online publication date: 8-Jun-2023
https://doi.org/10.1007/s10707-023-00495-4
Karpov NZhang HZhang Q(2023)MinJoin++: a fast algorithm for string similarity joins under edit distanceThe VLDB Journal10.1007/s00778-023-00806-z33:2(281-299)Online publication date: 21-Aug-2023
https://doi.org/10.1007/s00778-023-00806-z
Zhang JYiu MTang BLi Q(2022)Fast Error-Bounded Distance Distribution ComputationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.305824134:11(5364-5377)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TKDE.2021.3058241
Echihabi KTsandilas TGogolou ABezerianos APalpanas T(2022)ProS: data series progressive k-NN similarity search and classification with probabilistic quality guaranteesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-022-00771-z32:4(763-789)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1007/s00778-022-00771-z
Zheng BZhao XWeng LNguyen QLiu HJensen C(2021)PM-LSH: a fast and accurate in-memory framework for high-dimensional approximate NN and closest pair searchThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-021-00680-731:6(1339-1363)Online publication date: 3-Jul-2021
https://dl.acm.org/doi/10.1007/s00778-021-00680-7
Zheng BZhao XWeng LHung NLiu HJensen C(2020)PM-LSHProceedings of the VLDB Endowment10.14778/3377369.337737413:5(643-655)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.14778/3377369.3377374
Ge XChrysanthis PPelechrinis KZeinalipour-Yazti DSharaf M(2020)Serendipity-based Points-of-Interest NavigationACM Transactions on Internet Technology10.1145/339119720:4(1-32)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1145/3391197
Gogolou ATsandilas TEchihabi KBezerianos APalpanas TMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Data Series Progressive Similarity Search with Probabilistic Quality GuaranteesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389751(1857-1873)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389751
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents