On the estimation of the number of desired records with respect to a given query

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the estimation of the number of desired records with respect to a given query

Full text

Pdf (1.15 MB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 3 , Issue 1 (March 1978) table of contents

Pages: 41 - 56

Year of Publication: 1978

ISSN:0362-5915

Authors

C. T. Yu	Univ. of Alberta, Edmonton, Alta., Canada
W. S. Luk	Univ. of Alberta, Edmonton, Alta., Canada
M. K. Siu	Univ. of Alberta, Edmonton, Alta., Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 26, Citation Count: 14

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

ABSTRACT

The importance of the estimation of the number of desired records for a given query is outlined. Two algorithms for the estimation in the “closest neighbors problem” are presented. The numbers of operations of the algorithms are &Ogr;(ml2) and &Ogr;(ml), where m is the number of clusters and l is the “length” of the query.

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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	BAYER, R., AND McCREIGHT, E.M. Organization and maintenance of large ordered indices. Acta Informatica 1 (1972), 290-306.
	3	BORODIN, A., AND MUNRO, I. The Computational Complexity of Algebraic and Numerical Problems. American Elsevier, New York, 1975.
	4	E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
	5	Michael Hammer , Arvola Chan, Index selection in a self-adaptive data base management system, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
	6	James Martin, Computer Database Organization, 2nd Ed, Prentice Hall PTR, Upper Saddle River, NJ, 1977
	7	G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
	8	Mario Schkolnick, Secondary index optimization, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500106]
	9	VAN RIJSBERGEN, C.J. Further experiments with hierarchical clustering in document retrieval. Inform. Stor. and Retr. 10, 1 (1974), 1-14.
	10	C. T. Yu , W. S. Luk, Analysis of Effectiveness of Retrieval in Clustered Files, Journal of the ACM (JACM), v.24 n.4, p.607-622, Oct. 1977 [doi>10.1145/322033.322039]
	11	C. T. Yu , G. Salton, Precision Weighting—An Effective Automatic Indexing Method, Journal of the ACM (JACM), v.23 n.1, p.76-88, Jan. 1976 [doi>10.1145/321921.321930]

CITED BY 14

	W. Bruce Croft, On the implementation of some models of document retrieval, ACM SIGIR Forum, v.14 n.2, p.71-77, September 1979
	J. S. Deogun , V. V. Raghavan, User-oriented document clustering: a framework for learning in information retrieval, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.157-163, September 1986, Palazzo dei Congressi, Pisa, Italy
	D. Chow , C. T. Yu, On the Construction of Feedback Queries, Journal of the ACM (JACM), v.29 n.1, p.127-151, Jan. 1982
	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984
	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
	G. Salton , A. Wong, Generation and search of clustered files, ACM Transactions on Database Systems (TODS), v.3 n.4, p.321-346, Dec. 1978
	K. Lam , C. T. Yu, A clustered search algorithm incorporating arbitrary term dependencies, ACM Transactions on Database Systems (TODS), v.7 n.3, p.500-508, Sept. 1982
	King-Lup Liu , Clement Yu , Weiyi Meng , Wensheng Wu , Naphtali Rishe, A Statistical Method for Estimating the Usefulness of Text Databases, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1422-1437, November 2002
	Matthew B. Koll, Information retrieval theory and design based on a model of the user's concept relations, Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, p.77-93, June 23-27, 1980, Cambridge, England
	I. A. R. Moghrabi , R. Makholian, Vector-based approach to analysis of file space properties, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
	Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, ACM SIGMOD Record, v.14 n.2, June 1984
	Kenneth C. Sevcik, Data base system performance prediction using an analytical model (invited paper), Proceedings of the seventh international conference on Very Large Data Bases, p.182-198, September 09-11, 1981, Cannes, France
	Weiyi Meng , King-Lup Liu , Clement T. Yu , Xiaodong Wang , Yuhsi Chang , Naphtali Rishe, Determining Text Databases to Search in the Internet, Proceedings of the 24rd International Conference on Very Large Data Bases, p.14-25, August 24-27, 1998
	I. A. R. Moghrabi , R. A. Makholian, A New Approach to Clustering Records in Information Retrieval Systems, Information Retrieval, v.3 n.2, p.105-126, July 2000