The choice of reference points in best-match file searching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The choice of reference points in best-match file searching

Full text

Pdf (459 KB)

Source

Communications of the ACM archive
Volume 20 , Issue 5 (May 1977) table of contents

Pages: 339 - 343

Year of Publication: 1977

ISSN:0001-0782

Author

Marvin Shapiro

National Institutes of Health, Bethesda, MD

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 34, Citation Count: 16

Additional Information:

abstract 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/359581.359599 What is a DOI?

ABSTRACT

Improvements to the exhaustive search method of best-match file searching have previously been achieved by doing a preprocessing step involving the calculation of distances from a reference point. This paper discusses the proper choice of reference points and extends the previous algorithm to use more than one reference point. It is shown that reference points should be located outside of data clusters. The results of computer simulations are presented which show that large improvements can be achieved by the proper choice and location of multiple reference points.

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	W. A. Burkhard , R. M. Keller, Some approaches to best-match file searching, Communications of the ACM, v.16 n.4, p.230-236, April 1973 [doi>10.1145/362003.362025]
	2	Cover, T.M. and Hart, P.E.: Nearest neighbor pattern classification. IEEE Trans. Info. Theory, IT-13 (January 1967), 21-27.

CITED BY 16

	Tetsuro Ito , Makoto Kizawa, Hierarchical file organization and its application to similar-string matching, ACM Transactions on Database Systems (TODS), v.8 n.3, p.410-433, Sept. 1983
	Dennis Shasha , Tsong-Li Wang, New techniques for best-match retrieval, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.140-158, Apr. 1990
	C. M. Eastman, Current practice in the evaluation of multikey search algorithms, ACM SIGIR Forum, v.17 n.4, Summer 1983
	Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, ACM SIGMOD Record, v.24 n.2, p.163-174, May 1995
	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980
	Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001
	Peter N. Yianilos, Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.361-370, January 09-11, 2000, San Francisco, California, United States
	Alfredo Ferro , Giovanni Gallo , Rosalba Giugno , Alfredo Pulvirenti, Best-Match Retrieval for Structured Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.7, p.707-718, July 2001
	Domenico Cantone , Alfredo Ferro , Alfredo Pulvirenti , Diego Reforgiato Recupero , Dennis Shasha, Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.535-550, April 2005
	Fionn Murtagh, Clustering in massive data sets, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Gisli R. Hjaltason , Hanan Samet, Index-driven similarity search in metric spaces, ACM Transactions on Database Systems (TODS), v.28 n.4, p.517-580, December 2003
	Gísli R. Hjaltason , Hanan Samet, Properties of Embedding Methods for Similarity Searching in Metric Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.530-549, May 2003
	Gonzalo Navarro, Searching in metric spaces by spatial approximation, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.1, p.28-46, August 2002
	Jason Tsong-Li Wang , Dennis Shasha, Query Processing for Distance Metrics, Proceedings of the 16th International Conference on Very Large Data Bases, p.602-613, August 13-16, 1990
	Edgar Chávez , José L. Marroquín , Gonzalo Navarro, Fixed Queries Array: A Fast and Economical Data Structure for Proximity Searching, Multimedia Tools and Applications, v.14 n.2, p.113-135, June 2001
	Dragomir Yankov , Eamonn Keogh , Umaa Rebbapragada, Disk aware discord discovery: finding unusual time series in terabyte sized datasets, Knowledge and Information Systems, v.17 n.2, p.241-262, November 2008

INDEX TERMS

Keywords:
best match, file searching, matching, nearest-neighbor classification

Collaborative Colleagues:

Marvin Shapiro: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player