S-tree: a dynamic balanced signature index for office retrieval

ABSTRACT

The signature approach is an access method for partial-match retrieval which meets many requirements of an office environment. Signatures are hash coded binary words derived from objects stored in the data base. They serve as a filter for retrieval in order to discard a large number of nonqualifying objects. In an indexed signature method the signatures of objects stored on a single page are used to form a signature for that page. In this paper we describe a new technique of indexed signatures which combines the dynamic balancing of B-trees with the signature approach. The main problem of appropriate splitting is solved in a heuristic way. Operations are described and a simple performance analysis is given. The analysis and some experimental results indicate a considerable performance gain. Moreover, the new S-tree approach supports a clustering on a signature basis. Further remarks on adaptability complete this work.

REFERENCES

• BAYE72: Bayer, R., McCreight, E.M.: Organia#tion and Maintenance of Large Ordered Indexes, Acta Informatica 1972, pp. 173- 189.
• CHRI84: Stavros Christodoulakis , J. Vanderbroek , J. Li , T. Li , S. Wan , Y. Wang , M. Papa , Elisa Bertino, Development of a Multimedia Information System for an Office Environment, Proceedings of the 10th International Conference on Very Large Data Bases, p.261-271, August 27-31, 1984
• DADA83: Dadam, P., Pistor, P., Schek, H.-J.: A Predicate oriented Locking Approach for Integrated Information Systems, in: Mason, R.E.A. (ed.): Information Processing 83, Proc. IFIP 1983, pp. 763- 768.
• DADA86: P. Dadam , K. Kuespert , F. Andersen , H. Blanken , R. Erbe, A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies, ACM SIGMOD Record, v.15 n.2, p.356-367, June 1986
• DEPP85: Deppisch, U., Obermeit, V., Paul, H.-B., Schek, H.-J., SchoU, M.H., Weikum, G.: The Storage Subsystem of a Data Base Kernel System (in German), Proc. GI Conf. on Database Systems for Office Automation, Engineering and Scientific Applications 1985, pp. 421 -. 440; English version.available as Technical Report DVSI-1985-T1, TU Darmstadt, 1985. "
• FALO84: Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
• FALO85a: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• FALO85b: Chris Faloutsos, Signature files: design and performance comparison of some signature extraction methods, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.63-82, May 1985, Austin, Texas, United States
• FALO85c: Faloutsos, C., Christodoulakis, S.: Design of a Signature File Method that Accounts for Non-Unlform Occurence and Query Frequencies, Proc. VLDB 1985, pp. 165- 170.
• GIBB83: Simon Gibbs , Dionysis Tsichritzis, A data modeling approach for office information systems, ACM Transactions on Information Systems (TOIS), v.1 n.4, p.299-319, Oct. 1983 [doi>10.1145/357442.357444]
• GUTT84: 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
• HARR71: Malcolm C. Harrison, Implementation of the substring test by hashing, Communications of the ACM, v.14 n.12, p.777-779, Dec. 1971 [doi>10.1145/362919.362934]
• OREN84: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• PFAL80: John L. Pfaltz , William J. Berman , Edgar M. Cagley, Partial-match retrieval using indexed descriptor files, Communications of the ACM, v.23 n.9, p.522-528, Sept. 1980 [doi>10.1145/359007.359013]
• PRAB83: Prabhakax, T.V., Saha#abuddhe, H.V.: Signature Trees- A Data Structure for Index Organisatlon, Proc. IEEE Conf. on Systems, Man and Cybernetics 1983, pp. 1145- 1147.
• RABI84: F. Rabitti , J. Zizka, Evaluation of access methods to text documents in office systems, Proc. of the third joint BCS and ACM symposium on Research and development in information retrieval, p.21-40, November 1984, King's College, Cambridge
• RABI85: Rabitti, F.: A Model for Multimedia Documents, in: TSIC85a, pp. 227- 250.
• RIVE76: Rivest, R.L.: Partial-Match Retrieval Algorithms, SIAM Journal of Computing 1976, pp. 19- 50.
• RIJS79: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• ROBE79: Roberts, C.S.: Partial-Match Retrieved via the Method of Superimposed Codes, Proc. IEEE 1979, pp. 1624- 1642.
• SACK83: Sacks-Davis, R., Ramamohanarao, K.: A twolevel superimposed coding scheme for Partial Match Retrieval, information Systems 1983, pp. 273- 280.
• SALT78: 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 [doi>10.1145/320289.320291]
• SALT83a: Gerard Salton , Edward A. Fox , Harry Wu, Extended Boolean information retrieval, Communications of the ACM, v.26 n.11, p.1022-1036, Nov. 1983 [doi>10.1145/182.358466]
• SALT83b: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• SCHE77: Schek, H.-J.: Tolerating Fussiness in Keywords by Similarity Searches, Kybernetes 1977, pp. 175- 184.
• SCHE78: Hans-Jörg Schek, The reference string indexing method, Proceedings of the 2nd Conference of the European Cooperation on Informatics: Information Systems Methodology, p.432-459, October 10-12, 1978
• SCHE81: H.-J. Schek, Methods for the administration of textual data in database systems, Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, p.218-235, June 23-27, 1980, Cambridge, England
• SCHE82: Hans-Jörg Schek , Peter Pistor, Data Structures for an Integrated Data Base Management and Information Retrieval System, Proceedings of the 8th International Conference on Very Large Data Bases, p.197-207, September 08-10, 1982
• SEMS86: Semsroth, T.: Experimental Studies on S- Trees, Master Thesis, TU Darmstadt, 1986, forthcoming.
• TSIC85a: Teichritzis, D. (ed.): Office Automation, Berlin, Heidelberg: Springer 1985.
• TSIC85b: Tsichritzis, D., Christodoulakis, S., Lee, A., Vandenbroek, J.: A Multimedia Filing System, in: TSIC85a, pp. 43- 65.