C. M. Eastman
Skip Abstract Section
Abstract
File structures and algorithms for multikey searching allow more than a single key to be used in locating a record for use in retrieval or update. Such algorithms are of use in many different kinds of information systems, including database systems, information retrieval systems, and pattern recognition and image processing systems. Such algorithms have received increased attention in recent years. However, they are not as well understood as those which handle single keys.Multikey algorithms are more difficult to evaluate than those based on the use of single keys. There are simply more factors to be considered. The evaluations performed for such algorithms should allow comparisons in order to be useful to a community of researchers and users. Theoretical analyses should be based on reasonable and clearly stated assumptions. Experiments should be repeatable and statistically valid whether they are based on "real" data or on randomly generated data.
- AHOU79 Alfred V. Aho and Jeffrey D. Ullman, "Optimal partial-match retrieval when fields are independently specified", ACM TODS, Vol 4, No 2, June 1979, pp 168-179. Google Scholar
Digital Library
- ALAG80 Vangalur S. Alagar, "Algorithms for processing partial match queries using word fragments", Inform. Syst.,Vol 5, 1980, pp 323-332.Google ScholarCross Ref
- ANDE77 Henry D. Anderson and P. Bruce Berra, "Minimum cost selection of secondary indexes for formatted files", ACM TODS, Vol 2, No 1, March 1977, pp 68-90. Google ScholarDigital Library
- BATO79 D. S. Batory, "On searching transposed files", ACM TODS, Vol 4, No 4, Dec 1979, pp 531-544. Google ScholarDigital Library
- BENT79a Jon Louis Bentley, "Decomposable searching problems", Inform. Proc. Let., Vol 8, No 5, June 1979, pp 244-251.Google ScholarCross Ref
- BENT79b Jon Louis Bentley, "Multidimensional binary search trees in database applications", IEEE Trans. Soft. Eng., Vol SE-5, No 4, July 1979, pp 333-340.Google ScholarDigital Library
- BLAS77 Michael W. Blasgen, Richard G. Casey, and Kapali P. Eswaran, "An encoding method for multifield sortingand indexing", CACM, Vol 20, No 11, Nov 1977, pp 874-877. Google ScholarDigital Library
- BOLO79 Azad Bolour, "Optimality properties of multiple-key hashing functions", JACM, Vol 2 No 2, April 1979,pp 196-210. Google ScholarDigital Library
- BRIG81 R. C. Brigham, R. D. Dutton and J. R. Driscoll, "Complexity of a proposed database storage structure", Inform. Syst., Vol 6, No 1, 1981, pp 47-52.Google ScholarCross Ref
- BURK79 Walter A. Burkhard, "Partial-match hash coding: benefits of redundancy", ACM TODS, Vol 4, No 2, June 1979, pp 228-29. Google ScholarDigital Library
- BURT79 F. W. Burton and J. Kollias, "Optimising disc head movement in secondary key retrieval", Comp. J., Vol 22, No , 1979, pp 206-208.Google ScholarCross Ref
- CARD77 Alfonso F. Cardenas and James P. Sagamang, "Doubly-chained tree data base organisation --- analysis and design strategies", Comp. J., Vol 20, No 1, 1977, pp 15-26.Google ScholarCross Ref
- CHAN81 J. M Chang and K. S. Fu, "Extended k-d tree database organization: a dynamic multiattribute clustering method", IEEE Trans. Soft. Eng., Vol SE-7, No. 3, May 1981, pp 284-290.Google ScholarDigital Library
- CHRI82 S. Christodoulakis, "Issues in query evaluation", Database Engineering Bulletin, Vol 5, No 3, 1982, pp 48-51.Google Scholar
- CLAY78 Billy G. Claybrook, "Efficient algorithms for answering queries with unsorted multilists", Inform. Syst., Vol 3, pp 93-97, 1978.Google ScholarCross Ref
- COME78 Douglas Comer, "The difficulty of optimum index selection", ACM TODS, Vol 3, No 4, Dec 1978, pp 440-445. Google ScholarDigital Library
- COME81 Douglas Comer, "Analysis of a heuristic for full trie minimization", ACM TODS, Vol 6, No 3, Sept 1981, pp 513-537. Google ScholarDigital Library
- CROF80 W. Bruce Croft, "A model of cluster searching based on classification", Inform. Syst., Vol 5, 1980, pp 189-195.Google ScholarCross Ref
- EAST81 C. M. Eastman, "Optimal bucket size for nearest neighbor searching in k-d trees", Inform. Proc. Let., Vol 12, No 4, Aug 1981, pp 165-167.Google ScholarCross Ref
- FLOR78 A. Flory, J. Gunther and J. Kouloumdijan, "Data base reorganization by clustering methods", Inform. Syst., Vol 3, 1978, pp 59-62.Google ScholarCross Ref
- GOPA80 V. Gopalakrishna and C. E. Veni Madhavan, "Performance evaluation of attribute-based tree organization", ACM TODS, Vol 5, No 1, Mar 1980, pp 69-87. Google ScholarDigital Library
- HAMM78 Pierre Hammad and Jean-Marie Raviart, "Formulation of choice criterions for file organizations", Inform. Syst., Vol 3, 1978, pp 123-130.Google ScholarCross Ref
- HATZ80 M. Hatzopoulos and J. G. Kollias, "Some rules for introducing indexing paths in a primary file', Comp. J., Vol 23, No 3, 1980, pp 207-211.Google ScholarCross Ref
- HOOP80 J. ten Hoopen, "Consecutive retrieval with redundancy: an optimal linear and an optimal cyclic arangement and their storage space requirements", Inf. Proc. Let., Vol 11, Nos 4 and 5, Dec 1980, pp 211-217.Google Scholar
- JAKO80 Matti Jakobsson, "Reducing block accesses in inverted files by partial clustering", Inform. Syst., Vol 5, No 1, 1980, pp 1-6.Google ScholarCross Ref
- KASH77 R. L. Kashyap, S. K. C. Subas and S. B. Yao, "Analysis of the multiple-attribute-tree data-base organization", IEEE Trans. Soft. Eng., Vol SE-3, No 6, 1977, pp 451-466Google ScholarDigital Library
- KOLL79a J. G. Kollias, "File organizations and their reorganization", Inform. Syst., Vol 4, 1979, pp 49-54.Google ScholarCross Ref
- KOLL79b J. G. Kollias, "A heuristic approach for determing the optimal degree of file inversion", Inform. Syst., Vol 4, No 4, 1979, pp 307-318.Google ScholarCross Ref
- KOLH80 V. J. Kollias, M. Hatzopoulos, and J. G. Kollias, "Database maintenance efficiency using differential files", Inform. Syst., Vol 5, 1980, pp 319-321.Google ScholarCross Ref
- LEEW80 D. T. Lee and C. K. Wong, "Quintary trees : a file structure for multidimensional database systes", ACM TODS, Vol 5, No 9, Sept 1980, pp 339-353. Google ScholarDigital Library
- LINL79 W. C. Lin, R. C. T. Lee and H. C. Du, "Common properties of some multiattribute file systems", IEEE Trans. Soft. Eng., Vol SE-5, No 2, March 1979, pp 160-174.Google ScholarDigital Library
- LIOU77 J. H. Liou and S. B. Yao, "Multidimensional clustering for data base organization", Inform. Syst., Vol 2, No 4, 1977, pp 187-198.Google ScholarCross Ref
- LIPS77 W. Lipski, Jr., "One more polynomially complete consecutive retrieval problem", Inf. Proc. Let., Vol 6, No 3, June 1977, pp 91-93.Google ScholarCross Ref
- MARC81 Salvatore T. March, Dennis G. Severance, and Michael Wilens, "Frame momory: a storage architecture to support rapid design and implementation of efficient databases", ACM TODS, Vol 6, No 3, Sept 1981, pp 441-463. Google ScholarDigital Library
- MCD077 K. J. McDonell, "An inverted index implementation" Comp. J., Vol 20, No 2, 1977, pp 116-123.Google ScholarCross Ref
- MEHL81 Kurt Mehlhorn and Mark H. Overmars, "Optimal dynamization of decomposable searching problems", Inf. Proc. Let., Vol 12, No 2, April 1981, pp 93-98.Google ScholarCross Ref
- NICK77 B. M. Nicklas and G. Schlageter, "Index structuring in inverted data bases by TRIES", Comp. J., Vol 20, No 4, 1977, pp 321-324.Google ScholarCross Ref
- OVER81a Mark H. Overmars and Jan van Leeuwen, "Some principles for dynamizing decomposable searching problems", Inf. Proc. Let., Vol 12, No 1, Feb 1981, pp 49-53.Google ScholarCross Ref
- OVER81b Mark H. Overmars and J. van Leeuwen, "Worst case optimal insertion and deletion methods for decomposable searching problems", Inf. Proc. Let., Vol 12, NO 4, Aug 1981, pp 168-173.Google ScholarCross Ref
- PFAL80 John L. Pfaltz, William J. Berman, and Edgar M. Cagley, "Partial-match retrieval using indexed descriptor files", CACM, Vol 2, No 9, Sept 1980, pp 522-528. Google ScholarDigital Library
- PUTK79 Anne Putkonen, "On the selection of the access path in inverted database organization", Inform. Syst., Vol 4, 1979, pp 219-225.Google ScholarCross Ref
- ROSE78 Lawrence L. Rose and Malcolm H. Gotterer, "Dynamic file movement in multilevel storage systems", Inform. Syst., Vol 3, 1978, pp 117-121.Google ScholarCross Ref
- SALT78 G. Salton and A. Wong, "Generation and search of clustered files", ACM TODS, Vol 3, No 4, Dec 1978, pp 321-346. c Google ScholarDigital Library
- SAME80 Hanan Samet, "Deletion in two-dimensional quad trees", CACM, Vol 2, No 12, Dec 1980, pp 703-710. Google ScholarDigital Library
- SCHK77 Mario Schkolnick, "A clustering algorithm for hierarchical structures", ACM TODS, Vol 2, No 1, March 1977, pp 27-44. Google ScholarDigital Library
- SENG79 A. Sengupta, S. Bandyopadhyay and P. K. Srimani, "On identification of CR property in file organization", Inf. Proc. Let., Vol 9, No 2, Aug 79, pp 93-96.Google Scholar
- SHAP77 Marvin Shapiro, "The choice of reference points in best match file searching", CACM, Vol 20, No 5, May 1977, pp 339-343. Google ScholarDigital Library
- SHNE77 B. Shneiderman, "Reduced combined indices for efficient multiple attribute retrieval", Inform. Syst., Vol. 2, No 4, 1977, pp 149-154.Google ScholarCross Ref
- SILV79 Y. V. Silva Filho "Average case analysis of region search in balanced k-d trees", Inf. Proc. Let., Vol 8, No 5, June 79, pp 219-223.Google Scholar
- SILV81 Y. V. Silva Filho, "Optimal choice of discriminators in a balanced k-d binary search tree", Inf. Proc. Let., Vol 1, No 2, Nov 81, pp 67-70.Google Scholar
- SMIT82 A. J. Smith, "Research on file and I/O systems at the University of California, Berkeley", Database Engineering Bulletin, Vol 5, No 1, March 1982, pp 2-4.Google Scholar
- TAGU78 Jean M. Tague and Micheal J. Nelson, "Simulation of user judgments in bibliographic retrieval systems", Proceedings of the Fourth International Conference on Information Storage and Retrieval, Oakland, California, June 1981, pp 66-71. Google ScholarDigital Library
- TANA79 Katsumi Tanaka, Yahiko Kambayashi and Shuzo Yajima "Organization of quasi-consecutive retrieval files" Inform. Syst., Vol 4, 1979, pp 23-33.Google ScholarCross Ref
- TRUS80 Miroslaw Trszczynski "Once more on storage for consecutive retrieval", Inf. Proc. Let., Vol 10, No. 1, Feb 1980, pp 21-24.Google ScholarCross Ref
- VANL80 J. van Leeuwen and D. Wood, "Dynamization of decomposable searching problems", Inf. Proc. Let., Vol 10, No 2, March 1980, pp 51-56.Google ScholarCross Ref
- YANA79 S. Yamamoto, S. Tazawa, K. Ushio, and H. Ikeda, "Design of balanced multiple-valued file organization scheme with the least redundancy", ACM TODS, Vol 4, No 4, December 1979, pp 518-530. Google ScholarDigital Library
- YANG77 C. S. Yang, "Avoiding redundant record accesses in unsorted multilist file organizations", Inform. Syst, Vol 2, 1977, pp 155-158.Google ScholarCross Ref
- YANG78 C. S. Yang, "A class of hybrid list file organizations", Inform. Syst., Vol 3, No 1, 1978, pp 49-58.Google ScholarCross Ref
- YAOS77a S. B. Yao, "Approximating block accesses in database organizations", CACM, Vol 20, No 4, April 1977, pp 260-261. Google ScholarDigital Library
- YAOS77b S. B. Yao, "An attribute based model for database access cost analysis", ACM TODS, Vol 2, No 1, March 1977, pp 45-67. Google ScholarDigital Library
- ZVEG80 N. Zvegintov, "Partial match retrieval in an index sequential directory", Comp. J., Vol 2, No 1, 1980, pp 37-40.Google ScholarCross Ref
Index Terms
- Current practice in the evaluation of multikey search algorithms
Index terms have been assigned to the content through auto-classification.
Recommendations
Current practice in the evaluation of multikey search algorithms
SIGIR '83: Proceedings of the 6th annual international ACM SIGIR conference on Research and development in information retrievalFile structures and algorithms for multikey searching allow more than a single key to be used in locating a record for use in retrieval or update. Such algorithms are of use in many different kinds of information systems, including database systems, ...
Storing and searching a multikey table
STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingWe describe an implicit data structure for n multikey records that supports searching for a record, under any key, in the asymptotically optimal search time Ο(log n). This improves on [Mun87] in which Munro describes an implicit data structure for the ...
Symbolic Gray Code as a Multikey Hashing Function
In this paper, we extend the binary Gray code to symbolic Gray code. We then show that this symbolic Gray code can be used as a multikey hashing function for storing symbolic records. The record stored at location k and the record stored at location k + ...
Comments