C. T. Yu
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 Ο(ml2) and Ο(ml), where m is the number of clusters and l is the “length” of the query.
- 1 AHO, A.V., HOPCROFT, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
Digital Library
- 2 BAYER, R., AND McCREIGHT, E.M. Organization and maintenance of large ordered indices. Acta Informatica 1 (1972), 290-306.Google ScholarDigital Library
- 3 BORODIN, A., AND MUNRO, I. The Computational Complexity of Algebraic and Numerical Problems. American Elsevier, New York, 1975.Google Scholar
- 4 CODD, E.F. A relational model of data for large shared data banks. Comm. ACM 18, 9 (Sept. 1970), 377-387. Google ScholarDigital Library
- 5 HAMMER, M., AND C~XN, A. Index selection in a seILadaptive data base management system. Proc. ACM SIGMOD Int. Conf. on Management of Data, Washington, D.C., 1976, pp. 1-8. Google Scholar
- 6 MARTIN, J. Computer Data-Base Organization. Prentice-Hall, Englewood Cliffs, N.J., 1975. Google ScholarDigital Library
- 7 SALTON, G. The Smart Retrieval System--Experime~ts in Automatic Document Processing. Prentice-Hall, Englewood Cliffs, N.j., 1971. Google ScholarDigital Library
- 8 SCHKOLNICK, M. Secondary index optimization. Proc. ACM SIGMOD Int. Conf. on Management of Data, San Jose, Calif., 1975, pp. 186-1~92. Google ScholarDigital Library
- 9 VAN RIJSBERGEN, C.J. Further experiments with hierarchical clustering in document retrieval. Inform. Stor. and Retr. 10, 1 (1974), 1-14.Google ScholarCross Ref
- 10 YU, C.T., AND LUK, W.S. Analysis of effectiveness of retrieval in clustered files. J. ACM 2~, 4 (Oct. 1977), 607-622. Google ScholarDigital Library
- 11 Yu, C.T., AND SALTON, G. Precision weighting--an effective automatic indexing method. J. ACM 28, 1 (Jan. 1976), 76--88. Google ScholarDigital Library
Index Terms
- On the estimation of the number of desired records with respect to a given query
Recommendations
Query Estimation by Adaptive Sampling
ICDE '02: Proceedings of the 18th International Conference on Data EngineeringThe ability to provide accurate and efficient result estimations of user queries is very important for the query optimizer in database systems. In this paper, we show that the traditional estimation techniques with data reduction points of view do not ...
Different query verification approaches used to test entity SQL
DBTest '08: Proceedings of the 1st international workshop on Testing database systemsTesting a query language is a complex and challenging task. A tester must determine the representative subset of queries which must be tested from an infinite set of valid queries. Once the representative set of queries is determined, they then face the ...
Scalable Query Profiling Employing Purging and Elimination Technique
ICIBE '18: Proceedings of the 4th International Conference on Industrial and Business EngineeringReusing Queries contributes in speeding up the performance of database in responding to future queries as it can reduce the number of database queries to be processed and sent back to the user. Profiling a query in a machine who requested a query in ...
Comments