Uwe Deppisch
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.
- BAYE72.Bayer, R., McCreight, E.M.: Organia#tion and Maintenance of Large Ordered Indexes, Acta Informatica 1972, pp. 173- 189.Google Scholar
Digital Library
- CHRI84.Christodoulakis, S. et al.: Development of a Multimedia information System for an Office Environment, Proc. VLDB 1984, pp. 261- 271. Google ScholarDigital Library
- 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.Google Scholar
- DADA86.P. Dadam, K. Kuespert, F. Andersen, H. Blanken, R. Erbe, J. Guenauer, V. Lure, P. Pistor, G. Walch: A DBMS Prototype to Support Extended NF2 Relations: An/ntegrated View on Flat Tables and Hierarchies, accepted for SIGMOD 1986. Google ScholarDigital Library
- 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. "Google Scholar
- FALO84.Fedoutsos, C., Christodoulakis, S.: Signature Files: An Access Method for Documents and its Analytical Performance Evaluation, TOOIS 1984, pp. 267- 288. Google ScholarDigital Library
- FALO85a.Faloutsos, C.: Access Methods for Text, Computing Surveys 1985, pp. 49- 74. Google ScholarDigital Library
- FALO85b.Fedoutsos, C.: Signature files: Design and per~ formance comparison of some signature extraction methods, Proc. SIGMOD 1985, pp. 63 - 82. Google ScholarDigital Library
- 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.Google Scholar
- GIBB83.Gibbs, S., Tsichritsis, D.: A Data Modelling Approach for Office Information Systems, TOOIS 1983, pp. 299- 319. Google ScholarDigital Library
- GUTT84.Guttman, A.: R-T#eee: A dynamic index structure for spatial searching, Proc. SIG- MOD 1984, pp. 47- 57. Google ScholarDigital Library
- HARR71.Harrison, M.C.: Implementation of the Substring Test by Hashing, CACM 1971, pp. 777 - 779. Google ScholarDigital Library
- OREN84.Orenstein, J.A., Merrett, T.H.: A Class of Data Structures for Associative Searching, Proc. PODS 1984, pp. 181- 190. Google ScholarDigital Library
- PFAL80.Pfedts, J.L., Berman, W.J., Cagley, E.M.: Partial-Match Retrieval using Indexed Descriptor Files, CACM 1980, pp. 522- 528. Google ScholarDigital Library
- 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.Google Scholar
- RABI84.Rabitti, F., Zizka, J.: Evaluation of Acces Methods to Text Documents in Office Systems, in: Rijsbergen, van, C.J. (ed.): Proc. Research and Development in Information Retrieval 1984, pp. 21 - 40. Google ScholarDigital Library
- RABI85.Rabitti, F.: A Model for Multimedia Documents, in: TSIC85a, pp. 227- 250.Google Scholar
- RIVE76.Rivest, R.L.: Partial-Match Retrieval Algorithms, SIAM Journal of Computing 1976, pp. 19- 50.Google ScholarCross Ref
- RIJS79.Rijsbergen, van, C.J.: Information Retrieval, 2rid ed., London: Butherworth 1979. Google ScholarDigital Library
- ROBE79.Roberts, C.S.: Partial-Match Retrieved via the Method of Superimposed Codes, Proc. IEEE 1979, pp. 1624- 1642.Google ScholarCross Ref
- SACK83.Sacks-Davis, R., Ramamohanarao, K.: A twolevel superimposed coding scheme for Partial Match Retrieval, information Systems 1983, pp. 273- 280.Google Scholar
- SALT78.Salton, G., Wong, A.: Generation and Search of Clustered Files, TODS 1978, pp. 321 - 346. Google ScholarDigital Library
- SALT83a.Salton, G. Fox, E.A., Wu, H.: Extended Boolean Information Retrieval, CACM 1983, pp. 1022- 1036. Google ScholarDigital Library
- SALT83b.Salton, G., McGill, M.J.: Introduction to Modern Information Retrieval, New York: McGraw-Hill 1983. Google ScholarDigital Library
- SCHE77.Schek, H.-J.: Tolerating Fussiness in Keywords by Similarity Searches, Kybernetes 1977, pp. 175- 184.Google ScholarCross Ref
- SCHE78.Schek, H.-J.: The Reference String Access Method and Partial Match Retrieval, IBM Scientific Center Report TR 77.12.008; partly contained in: The Reference String Indexing Method, in: Bracchi, G., Lockemann, P.C. (eds.): Proc. Information System Methodolog3' 1978, Springer LNCS 65, pp. 432- 459. Google ScholarDigital Library
- SCHE81.Schek, H.-J.: Methods for the Administration of Textual Data in Data Base Systems, in: Oddy, R.N. et al. (eds.): Information Retrieval Research, London: Butherworth 1981, pp. 218 - 235. Google Scholar
- SCHE82.Schek, H.-J., Pistor, P.: Data Structures for an Integrated Data Base Management and Information Retrieval System, Proc. VLDB 1982, pp. 197- 207. Google ScholarDigital Library
- SEMS86.Semsroth, T.: Experimental Studies on S- Trees, Master Thesis, TU Darmstadt, 1986, forthcoming.Google Scholar
- TSIC85a.Teichritzis, D. (ed.): Office Automation, Berlin, Heidelberg: Springer 1985.Google Scholar
- TSIC85b.Tsichritzis, D., Christodoulakis, S., Lee, A., Vandenbroek, J.: A Multimedia Filing System, in: TSIC85a, pp. 43- 65.Google Scholar
- S-tree: a dynamic balanced signature index for office retrieval
Recommendations
Constructing Forward-Secure Identity-Based Encryption from Identity-Based Binary Tree Encryption
ISISE '12: Proceedings of the 2012 Fourth International Symposium on Information Science and EngineeringIn this paper, we propose a generic construction of forward-secure identity-based encryption. We first introduce a relaxed variant of hierarchical identity-based encryption called identity-based binary tree encryption and construct a concrete identity-...
M-TREE: a high efficiency security architecture for protecting integrity and privacy of software
Special issue: Security in grid and distributed systemsSecure processor architectures enable new sets of applications such as commercial grid computing, software copy protection and secure mobile agents by providing secure computing environments that are immune to both physical and software attacks. Despite ...
Tree-LSHB+: An LPN-Based Lightweight Mutual Authentication RFID Protocol
In this paper, we propose an enhancement of the Tree-based authentication protocol, named as the Tree-LSHB+ protocol. The protocol is a lightweight authentication protocol that is suitable for use in radio frequency identification (RFID) systems. ...
Comments