Article

Free access

Dimensionality reduction and similarity computation by inner product approximations

Authors:

Ömer Eğecioğlu,

Hakan FerhatosmanoğluAuthors Info & Claims

CIKM '00: Proceedings of the ninth international conference on Information and knowledge management

Pages 219 - 226

https://doi.org/10.1145/354756.354822

Published: 06 November 2000 Publication History

PDF eReader

References

[1]

R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. In 4th Int. Conference on Foundations of Data Organization and Algorithms, pages 69-84, 1993.

Digital Library

Google Scholar

[2]

N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R* tree: An efficient and robust access method for points and rectangles. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 322-331, May 23- 25 1990.

Digital Library

Google Scholar

[3]

S. Berchtold, C. Bohm, D. Keim, and H. Kriegel. A cost model for nearest neighbor search in high-dimensional data space. In Proc. ACM Symp. on Principles of Database Systems, Tucson, Arizona, 1997.

Digital Library

Google Scholar

[4]

S. Berchtold, C. Bohm, and H.-P. Kriegel. The Pyramid- Technique: Towards breaking the curse of dimensionality. InProc. ACM SIGMOD Int. Conf. on Management of Data, pages 142-153, Seattle, Washington, USA, June 1998.

Digital Library

Google Scholar

[5]

P. Bernstein, M. Brodie, S. Ceri, D. DeWitt, M. Franklin, H. Garcia-Molina, J. Gray, J. Held, J. Hellerstein, H. Jagadish, M. Lesk, D. Maier, J. Naughton, H. Pirahesh, M. Stonebraker, and J. Ullman. The asilomar report on database research, December 1998.

Digital Library

Google Scholar

[6]

X. Cheng, R. Dolin, M. Neary, S. Prabhakar, K. Ravikanth, D. Wu, D. Agrawal, A. El Abbadi, M. Freeston, A. Singh, T. Smith, and J. Su. Scalable access within the context of digital libraries. In IEEE Proceedings of the International Conference onAdvances in Digital Libraries, ADL, pages 70-81, Washington, D.C., 1997.

Digital Library

Google Scholar

[7]

S. Deerwester, S.T. Dumais, G.W.Furnas, T.K. Launder, and R. Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41:391-407, 1990.

Crossref

Google Scholar

[8]

S. T. Dumais. Improving the retrieval of information from external sources. Behavior Research Methods, Instruments and Computers, 23:229-236, 1991.

Crossref

Google Scholar

[9]

. O. Egecioglu. How to approximate the inner-product: fast dynamic algorithms for similarity. Technical Report TRCS98-37, Department of Computer Science, University of California at Santa Barbara, December 1998.

Digital Library

Google Scholar

[10]

. O. Egecioglu and H. Ferhatosmanoglu, Dynamic Dimensionality Reduction and Similarity Distance Computation by Inner Product Approximations, Technical Report TRCS99-20, Department ofComputer Science, University of California at Santa Barbara, June 1999.

Digital Library

Google Scholar

[11]

C. Faloutsos, R. Barber, M. Flickner, J. Hafner, W. Niblack, D. Petkovic, and W. Equitz. Efficient and effective querying by image content. Journal of Intelligent Information Systems, 3:231-262, 1994.

Digital Library

Google Scholar

[12]

C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 419-429, Minneapolis, May 1994.

Digital Library

Google Scholar

[13]

A. Gionis, P. Indyk, and R. Motwani. Similarity searching in high dimensions via hashing. In Proceedings of the Int. Conf. on Very Large Data Bases, pages 518- 529, Edinburgh, Scotland, UK, September 1999.

Digital Library

Google Scholar

[14]

A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 47-57, 1984.

Digital Library

Google Scholar

[15]

N.A.J. Hastings and J.B. Peacock. Statistical Distributions, Halsted Press, New York, 1975.

Google Scholar

[16]

D. Hull. Improving text retrieval for the routing problem using latent semantic indexing. In Proc. of the 17th ACM-SIGIR Conference, pages 282-291, 1994.

Digital Library

Google Scholar

[17]

F. Korn, N. Sidiropoulos, C. Faloutsos, E. Siegel, and Z. Protopapas. Fast nearest neighbor search in medical image databases. In Proceedings of the Int. Conf. on Very Large Data Bases, pages 215-226, Mumbai, India, 1996.

Digital Library

Google Scholar

[18]

K. V. Ravi Kanth, D. Agrawal, and A. Singh. Dimensionality reduction for similarity searching in dynamic databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 1998.

Digital Library

Google Scholar

[19]

B. S. Manjunath and W. Y. Ma. Texture features for browsing and retrieval of image data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(8):837-42, August 1996.

Digital Library

Google Scholar

[20]

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, and P. Yanker. The QBIC project: Querying images by content using color, texture and shape. In Proc. of the SPIE Conf. 1908 on Storage and Retrieval for Image and Video Databases, volume 1908, pages 173-187, February 1993.

Crossref

Google Scholar

[21]

T. Seidl and Kriegel H.-P. Efficient user-adaptable similarity search in large multimedia databases. In Proceedings of the Int. Conf. on Very Large Data Bases, pages 506-515, Athens, Greece, 1997.

Digital Library

Google Scholar

[22]

T. Seidl and H.P. Kriegel. Optimal multi-step k-nearest neighbor search. In Proc. ACM SIGMOD Int. Conf. on Management of Data, Chicago, Illinois, U.S.A., June 1998. ACM.

Digital Library

Google Scholar

[23]

V.S. Subrahmanian. Principles of Multimedia Database Systems. Morgan Kaufmann Publishers, Inc., San Francisco, California, 1999.

Digital Library

Google Scholar

Cited By

View all

Tao XPaoletti MWu ZHaut JRen PPlaza A(2024)An Abundance-Guided Attention Network for Hyperspectral UnmixingIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.335325962(1-14)Online publication date: 2024
https://doi.org/10.1109/TGRS.2024.3353259
Hwang YAhn H(2011)Convergent bounds on the euclidean distanceProceedings of the 25th International Conference on Neural Information Processing Systems10.5555/2986459.2986503(388-396)Online publication date: 12-Dec-2011
https://dl.acm.org/doi/10.5555/2986459.2986503
Papapetrou PAthitsos VPotamias MKollios GGunopulos D(2011)Embedding-based subsequence matching in time-series databasesACM Transactions on Database Systems10.1145/2000824.200082736:3(1-39)Online publication date: 26-Aug-2011
https://dl.acm.org/doi/10.1145/2000824.2000827
Show More Cited By

Index Terms

Dimensionality reduction and similarity computation by inner product approximations

Recommendations

Dimensionality Reduction and Similarity Computation by Inner-Product Approximations

As databases increasingly integrate different types of information such as multimedia, spatial, time-series, and scientific data, it becomes necessary to support efficient retrieval of multidimensional data. Both the dimensionality and the amount of ...
Dimensionality reduction-based spoken emotion recognition

To improve effectively the performance on spoken emotion recognition, it is needed to perform nonlinear dimensionality reduction for speech data lying on a nonlinear manifold embedded in a high-dimensional acoustic space. In this paper, a new supervised ...
Dimensionality reduction for similarity search with the Euclidean distance in high-dimensional applications

In multimedia information retrieval, multimedia data are represented as vectors in high-dimensional space. To search these vectors efficiently, a variety of indexing methods have been proposed. However, the performance of these indexing methods degrades ...

Comments

Information & Contributors

Information

Published In

CIKM '00: Proceedings of the ninth international conference on Information and knowledge management

November 2000

532 pages

ISBN:1581133200

DOI:10.1145/354756

Chairmen:
Arvin Agah
Univ. of Kansas, Lawrence
,
Jamie Callan
Carnegie Mellon Univ., Pittsburgh, PA
,
Elke Rundensteiner
Worcester Polytechnic Institute, Worcester, MA
,
Susan Gauch
Univ. of Kansas, Lawrence

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM00

Sponsor:

CIKM00: Ninth International Conference on Information and Knowledge Management

November 6 - 11, 2000

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

14
Total Citations
View Citations
690
Total Downloads

Downloads (Last 12 months)95
Downloads (Last 6 weeks)16

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tao XPaoletti MWu ZHaut JRen PPlaza A(2024)An Abundance-Guided Attention Network for Hyperspectral UnmixingIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.335325962(1-14)Online publication date: 2024
https://doi.org/10.1109/TGRS.2024.3353259
Hwang YAhn H(2011)Convergent bounds on the euclidean distanceProceedings of the 25th International Conference on Neural Information Processing Systems10.5555/2986459.2986503(388-396)Online publication date: 12-Dec-2011
https://dl.acm.org/doi/10.5555/2986459.2986503
Papapetrou PAthitsos VPotamias MKollios GGunopulos D(2011)Embedding-based subsequence matching in time-series databasesACM Transactions on Database Systems10.1145/2000824.200082736:3(1-39)Online publication date: 26-Aug-2011
https://dl.acm.org/doi/10.1145/2000824.2000827
Papapetrou PDoliotis PAthitsos V(2009)Towards faster activity search using embedding-based subsequence matchingProceedings of the 2nd International Conference on PErvasive Technologies Related to Assistive Environments10.1145/1579114.1579180(1-8)Online publication date: 9-Jun-2009
https://dl.acm.org/doi/10.1145/1579114.1579180
Athitsos VPapapetrou PPotamias MKollios GGunopulos DLakshmanan LNg RShasha D(2008)Approximate embedding-based subsequence matching of time seriesProceedings of the 2008 ACM SIGMOD international conference on Management of data10.1145/1376616.1376656(365-378)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1376616.1376656
Athitsos VAlon JSclaroff SKollios G(2008)BoostMapIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2007.114030:1(89-104)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1109/TPAMI.2007.1140
Athitsos VHadjieleftheriou MKollios GSclaroff S(2007)Query-sensitive embeddingsACM Transactions on Database Systems10.1145/1242524.124252532:2(8-es)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1145/1242524.1242525
Ferhatosmanoglu HTuncel EAgrawal DEl Abbadi A(2006)High dimensional nearest neighbor searchingInformation Systems10.1016/j.is.2005.01.00131:6(512-540)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1016/j.is.2005.01.001
Jeong SKim SKim KChoi B(2006)An effective method for approximating the euclidean distance in high-dimensional spaceProceedings of the 17th international conference on Database and Expert Systems Applications10.1007/11827405_84(863-872)Online publication date: 4-Sep-2006
https://dl.acm.org/doi/10.1007/11827405_84
Athitsos VHadjieleftheriou MKollios GSclaroff SOzcan F(2005)Query-sensitive embeddingsProceedings of the 2005 ACM SIGMOD international conference on Management of data10.1145/1066157.1066238(706-717)Online publication date: 14-Jun-2005
https://dl.acm.org/doi/10.1145/1066157.1066238
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Dimensionality Reduction and Similarity Computation by Inner-Product Approximations

Dimensionality reduction-based spoken emotion recognition

Dimensionality reduction for similarity search with the Euclidean distance in high-dimensional applications