Dimensionality reduction and similarity computation by inner product approximations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dimensionality reduction and similarity computation by inner product approximations

Full text

Pdf (246 KB)

Source

Conference on Information and Knowledge Management archive
Proceedings of the ninth international conference on Information and knowledge management table of contents

McLean, Virginia, United States

Pages: 219 - 226

Year of Publication: 2000

ISBN:1-58113-320-0

Authors

Ömer Eğecioğlu	Department of Computer Science, University of California at Santa Barbara
Hakan Ferhatosmanoğlu	Department of Computer Science, University of California at Santa Barbara

Sponsors

SIGMIS: ACM Special Interest Group on Management Information Systems
SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 32, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/354756.354822 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
	2	Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
	3	Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
	4	Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
	5	Phil Bernstein , Michael Brodie , Stefano Ceri , David DeWitt , Mike Franklin , Hector Garcia-Molina , Jim Gray , Jerry Held , Joe Hellerstein , H. V. Jagadish , Michael Lesk , Dave Maier , Jeff Naughton , Hamid Pirahesh , Mike Stonebraker , Jeff Ullman, The Asilomar report on database research, ACM SIGMOD Record, v.27 n.4, p.74-80, Dec. 1998 [doi>10.1145/306101.306137]
	6	X. Cheng , R. Dolin , M. Neary , S. Prabhakar , K. V. Ravi Kanth , D. Wu , D. Agrawal , A. El Abbadi , M. Freeston , A. Singh , T. Smith , J. Su, Scalable access within the context of digital libraries, Proceedings of the IEEE international forum on Research and technology advances in digital libraries, p.70-81, May 07-09, 1997, Washington, D.C., United States
	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.
	8	S. T. Dumais. Improving the retrieval of information from external sources. Behavior Research Methods, Instruments and Computers, 23:229-236, 1991.
	9	Omer Egecioglu, How to Approximate the Inner-product: Fast Dynamic Algorithms for Euclidean Similarity, University of California at Santa Barbara, Santa Barbara, CA, 1999
	10	Omer Egecioglu , Hakan Ferhatosmanoglu, Dynamic Dimensionality Reduction and Similarity Distance Computation by Inner Product Approximations, University of California at Santa Barbara, Santa Barbara, CA, 1999
	11	C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
	12	Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
	13	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
	14	Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	15	N.A.J. Hastings and J.B. Peacock. Statistical Distributions, Halsted Press, New York, 1975.
	16	David Hull, Improving text retrieval for the routing problem using latent semantic indexing, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.282-291, July 03-06, 1994, Dublin, Ireland
	17	Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
	18	K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States
	19	B. S. Manjunath , W. Y. Ma, Texture Features for Browsing and Retrieval of Image Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.837-842, August 1996 [doi>10.1109/34.531803]
	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.
	21	Thomas Seidl , Hans-Peter Kriegel, Efficient User-Adaptable Similarity Search in Large Multimedia Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.506-515, August 25-29, 1997
	22	Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
	23	V. S. Subrahmanian, Principles of multimedia database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998

CITED BY 11

	Eamonn Keogh , Selina Chu , Michael Pazzani, Ensemble-index: a new approach to indexing large databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.117-125, August 26-29, 2001, San Francisco, California
	Ertem Tuncel , Hakan Ferhatosmanoglu , Kenneth Rose, VQ-index: an index structure for similarity searching in multimedia databases, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France
	Tsvi Kuflik , Zvi Boger , Peretz Shoval, Filtering search results using an optimal set of terms identified by an artificial neural network, Information Processing and Management: an International Journal, v.42 n.2, p.469-483, March 2006
	Ümit Y. Ogras , Hakan Ferhatosmanoglu, Dimensionality reduction using magnitude and shape approximations, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Vassilis Athitsos , Marios Hadjieleftheriou , George Kollios , Stan Sclaroff, Query-sensitive embeddings, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, High dimensional nearest neighbor searching, Information Systems, v.31 n.6, p.512-540, September 2006
	Vassilis Athitsos , Marios Hadjieleftheriou , George Kollios , Stan Sclaroff, Query-sensitive embeddings, ACM Transactions on Database Systems (TODS), v.32 n.2, p.8-es, June 2007
	Vassilis Athitsos , Panagiotis Papapetrou , Michalis Potamias , George Kollios , Dimitrios Gunopulos, Approximate embedding-based subsequence matching of time series, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Giuseppe Amato , Pasquale Savino, Approximate similarity search in metric spaces using inverted files, Proceedings of the 3rd international conference on Scalable information systems, June 04-06, 2008, Vico Equense, Italy
	Vassilis Athitsos , Jonathan Alon , Stan Sclaroff , George Kollios, BoostMap: An Embedding Method for Efficient Nearest Neighbor Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.30 n.1, p.89-104, January 2008
	Panagiotis Papapetrou , Paul Doliotis , Vassilis Athitsos, Towards faster activity search using embedding-based subsequence matching, Proceedings of the 2nd International Conference on PErvsive Technologies Related to Assistive Environments, p.1-8, June 09-13, 2009, Corfu, Greece