Access methods for text

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Access methods for text

Full text

Pdf (2.59 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 17 , Issue 1 (March 1985) table of contents
Annals of discrete mathematics, 24

Pages: 49 - 74

Year of Publication: 1985

ISSN:0360-0300

Author

Chris Faloutsos

Univ. of Toronto, Toronto, Ont., Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 105, Citation Count: 86

Additional Information:

abstract references cited by index terms review 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/4078.4080 What is a DOI?

ABSTRACT

This paper compares text retrieval methods intended for office systems. The operational requirements of the office environment are discussed, and retrieval methods from database systems and from information retrieval systems are examined. We classify these methods and examine the most interesting representatives of each class. Attempts to speed up retrieval with special purpose hardware are also presented, and issues such as approximate string matching and compression are discussed. A qualitative comparison of the examined methods is presented. The signature file method is discussed in more detail.

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 , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
	2	Alfred V. Aho , Jeffrey D. Ullman, Optimal partial-match retrieval when fields are independently specified, ACM Transactions on Database Systems (TODS), v.4 n.2, p.168-179, June 1979 [doi>10.1145/320071.320074]
	3	Sudhir R. Ahuja , Charles S. Roberts, An associative/parallel processor for partial match retrieval using superimposed codes, Proceedings of the 7th annual symposium on Computer Architecture, p.218-227, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801929]
	4	ANGELL, R. C., FREUND, G. E., AND WILLET, P. 1983. Automatic spelling correction using a trigram similarity measure. Inf. Process. Manage. 19, 4, pp. 255-261.
	5	Ian J. Barton , Susan E. Creasey , Michael F. Lynch , Michael J. Snell, An information-theoretic approach to text searching in direct access systems, Communications of the ACM, v.17 n.6, p.345-350, June 1974 [doi>10.1145/355616.364034]
	6	BATCHER, K. E. 1968. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference. AFIPS Press, Reston, Va., pp. 307-314.
	7	BAYER, R., AND MCCREIGHT, E. 1972. Organization and maintenance of large ordered indexes. Acta Inf. 1, 3, pp. 173-189.
	8	Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
	9	R. M. Bird , J. C. Tu , R. M. Worthy, Associative/parallel processors for searching very large textual data bases, Proceedings of the 3rd workshop on Computer architecture : Non-numeric processing, p.8-9, January 1977
	10	BOURNE, C. P. 1963. Methods of Information Handling. Wiley, New York.
	11	BOURNE, C. P. 1977. Frequency and impact of spelling errors in bibliographic databases. Inf. Process. Manage. 13, 1, pp. 1-12.
	12	Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
	13	BRAUEN, T. 1971. Document vector modification. In The SMART Retrieval System--Experiments in Automatic Document Processing, G. Salton, Ed. Prentice-Hall, Englewood Cliffs, N.J., Ch. 24.
	14	BURKOWSKI, F. J. 1982. A hardware hashing scheme in the design of a multiterm string comparator. IEEE Trans. Comput. C-31, 9 (Sept.), 825-834.
	15	CHRISTODOULAKIS, S. 1983. Access files for hatching queries in large information systems. In Proceedings of ICOD II (Aug.).
	16	S. Christodoulakis, Framework for the development of an experimental mixed-mode message system, Proc. of the third joint BCS and ACM symposium on Research and development in information retrieval, p.1-20, November 1984, King's College, Cambridge
	17	CHRISTODOULAKIS, S., AND FALOUTSOS, C. 1984. Design considerations for a message file server. IEEE Trans. Softw. Eng. SE-IO, 2 (Mar.), 201- 210.
	18	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
	19	COOPER, W. S. 1970. On deriving design equations for information retrieval systems. J. Am. Soc. Inf. Sci. (Nov.-Dec.).
	20	CROFT, W. B. 1980. A model of cluster searching based on classification. Inf. Syst. 5, 189-195.
	21	Fred J. Damerau, A technique for computer detection and correction of spelling errors, Communications of the ACM, v.7 n.3, p.171-176, March 1964 [doi>10.1145/363958.363994]
	22	DATrOLA, R. 1979. FIRST: Flexible information retrieval system for text. J. Am. Soc. Inf. Sci, 30, (Jan.), 9-14.
	23	DE LA BRIANDAIS, S. R. 1959. File searching using variable length keys. In Proceedings of the AFIPS Spring Joint Computer Conference. AFIPS Press, Reston, Va., pp. 295-298.
	24	DEWEY, C. 1950. Relative Frequency of English Speech Sounds. Harvard University Press, Cambridge, Mass.
	25	DUDA, R. O., AND HART, P. E. 1973. Pattern Classification and Scene Analysis. Wiley, New York.
	26	Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
	27	FALOUTSOS, C. 1985a. Design of a signature file method that accounts for nonuniform occurrence and query frequencies. In Proceedings of the 11th Conference on Very Large Data Bases (Stockholm, Sweden, Aug.), to appear.
	28	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
	29	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]
	30	FILES, J. R., A~D HUSKEY, H. D. 1969. An information retrieval system based on superimposed coding. In Proceedings of the Fall Joint Computer Conference, vol. 35. AFIPS Press, Reston, Va., pp. 423- 432.
	31	Fox, E. A. 1984. Extended information retrieval with data and text. PODS, submitted for publication.
	32	Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
	33	FRIEDMAN, S. R., MACEYAK, J. A., AND WEISS, S. F. 1971. A relevance feedback system based on document transformation. In The SMART Retrieval System--Experiments in Automatic Document Processing, G. Salton, Ed., Prentice-Hall Englewood Cliffs, N.J., Ch. 23.
	34	Larry Fujitani, Laser optical disk: the coming revolution in on-line storage, Communications of the ACM, v.27 n.6, p.546-554, June 1984 [doi>10.1145/358080.358094]
	35	GALLAGER, R. G., AND VAN VOORH{$, D. C. 1975. Optimal source codes for geometrically distributed integer alphabets. IEEE Trans. Inf. Theor. IT~21 (March), 228-230.
	36	GOLOMB, S. W. 1966. Run length encodings. IEEE Trans. Inf. Theor. IT-12 (July), 399-401.
	37	GRAVINA, C. M. 1978. National Westminster Bank mass storage archiving. IBM Syst. J. 17, 4, 344- 358.
	38	Richard A. Gustafson, Elements of the randomized combinatorial file structure, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland [doi>10.1145/511285.511304]
	39	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980 [doi>10.1145/356827.356830]
	40	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]
	41	HASKIN, R. L. 1981. Special-purpose processors for text retrieval. Database Eng. 4, i (Sept.), 16-29.
	42	Roger L. Haskin , Lee A. Hollaar, Operational characteristics of a harware-based pattern matcher, ACM Transactions on Database Systems (TODS), v.8 n.1, p.15-40, March 1983 [doi>10.1145/319830.319832]
	43	Roger L. Haskin , Raymond A. Lorie, On extending the functions of a relational database system, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582390]
	44	Lee A. Hollaar, Specialized merge processor networks for combining sorted lists, ACM Transactions on Database Systems (TODS), v.3 n.3, p.272-284, Sept. 1978 [doi>10.1145/320263.320281]
	45	HOLLAAR, L. A. 1979. Text retrieval computers. IEEE Comput. Mag. 12, 3 (Mar.), 40-50.
	46	HOLLAAR, L. A., SMITH, K. F., CHOW, W. H., EMRATH, P. A., AND HASKIN, R. L. 1983. Architecture and operation of a large, full-text information-retrieval system. In Advanced Database Machine Architecture, D. K. Hsiao, Ed. Prentice- Hall, Englewood Cliffs, N.J., pp. 256-299.
	47	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	48	IBM 1979. STAIRS/VS: Reference Manual. IBM Systern Manual.
	49	John Howard Johnson, Formal models for string similarity, 1983
	50	KAUTZ, W. H., AND SINGLETON, R. C. 1964. Nonrandom binary superimposed codes. IEEE Trans. Inf. Theor. IT-IO (Oct.), 363-377.
	51	KNOTT, G. D. 1971. Expandable open addressing hash table storage and retrieval. In Proceedings of the ACM SIGFIDET Conference (San Diego, Calif.). ACM, New York, pp. 187-206.
	52	KNOTT, G. D. 1975. Hashing functions. Comput. J. 18, 3, pp. 265-278.
	53	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	54	KNUTH, D. E., MORRIS, J. H., AND PRATT, V. R. 1977. Fast pattern matching in strings. SlAM J. Cornput. 6, 2 (June), 323-350.
	55	LARSON, P. 1978. Dynamic hashing. BIT 18, pp. 184- 201.
	56	Per-Åke Larson, A Method for Speeding Up Text Retrieval, Databases for Business and Office Applications, Database Week, p.117-123, May 23-26, 1983 [doi>10.1145/647004.711872]
	57	LESK, M. E. 1978. Some applications of inverted indexes on the UNIX system. In the UNIX Programmer's Manual. Bell Laboratories, Murray Hill, N.J.
	58	LLOYD, J. W. 1980. Optimal partial-match retrieval. BIT 20, pp. 406-413.
	59	LLOYD, J. W., AND RAMAMOHANARAO, K. 1982. Partial-match retrieval for dynamic files. BIT, 22, pp. 150-168.
	60	Robert A. Wagner , Roy Lowrance, An Extension of the String-to-String Correction Problem, Journal of the ACM (JACM), v.22 n.2, p.177-183, April 1975 [doi>10.1145/321879.321880]
	61	G. N.N. Martin, Spiral Storage: Incrementally Augmentable Hash Addressed Storage, University of Warwick, Coventry, UK, 1979
	62	MCILROY, M. D. 1982. Development of a spelling list. IEEETrans. Commun. COM-30, 1 (Jan.), 91-99.
	63	McLEoo, I. A. 1981. A database management system for document retrieval applications. Inf. Syst. 6, 2, pp. 131-137.
	64	MOOERS, C. 1949. Application of random codes to the gathering of statistical information. Bull. 31, Zator Co., Cambridge, Mass., 1949. Based on M.S.C. thesis, MIT, Jan. 1948.
	65	J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
	66	OROSZ, G., AND TACKACS, L. 1956. Some probability problems concerning the marking of codes into the superimposed field. J. Doc. 12, 4 (Dec.), 231- 234.
	67	James L. Peterson, Computer programs for detecting and correcting spelling errors, Communications of the ACM, v.23 n.12, p.676-687, Dec. 1980 [doi>10.1145/359038.359041]
	68	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]
	69	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
	70	RIVEST, R. L. ~976. Partial match retrieval algorithms. SIAM J. Comput. 5, 1 (Mar.), 19-50.
	71	ROBERTS, C. S. 1979. Partial-match retrieval via the method of superimposed codes. Proc. iEEE 67, 12 (Dec.), 1624-1642.
	72	John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
	73	Roccmo, J. J. 1971. Relevance feedback in information retrieval. In The SMART Retrieval System-- Experiments in Automatic Document Processing, G. Salton, Ed., Prentice-Hall, Englewood Cliffs, N.J., Ch. 14.
	74	James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974 [doi>10.1145/360827.360831]
	75	G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
	76	SALTON, G. 1971b. Relevance feedback and the optimization of retrieval effectiveness. In The SMART Retrieval System--Experiments in Automatic Document Processing, G. Salton, Ed., Prentice-Hall, Englewood Cliffs, N.J., Ch. 15.
	77	SALTON, G. 1972. Experiments in automatic thesaurus construction for information retrieval. In Informarion Processing 71. North-Holland, Amsterdam, pp. 115-123.
	78	G. Salton, Recent Studies in Automatic Text Analysis and Document Retrieval, Journal of the ACM (JACM), v.20 n.2, p.258-278, April 1973 [doi>10.1145/321752.321757]
	79	Gerard Salton, Dynamic information and library processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1975
	80	SALTO~, G. 1980. Automatic information retrieval. IEEE Comput. Mag. 13, 9 (Sept.), 41-56.
	81	Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
	82	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]
	83	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]
	84	SCHUEGRAPH, E. J., ANO HEAPS, H. 8. 1976. Query processing in a retrospective document retrieval system that uses word fragments as language elements. Inf. Process. Manage. 12, pp. 283- 292.
	85	Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974 [doi>10.1145/356631.356633]
	86	SEVERANCE, D. G. 1983. A practitioner's Guide to database compression. In{. Syst. 8, 1, 51-62.
	87	8PARCK-JONES, K. 1972. A statistical interpretation of term specificity and its application in retrieval. J. Doc. 28, 1 (Mar.), 11-20.
	88	STELLHORN, W. H. 1977. An inverted file processor for information retrieval. IEEE Trans. Comput. C-26, 12 (Dec.), 1258-1267.
	89	STIASSNY, 8. 1960. Mathematical analysis of various superimposed coding methods. Am. Doc. 11, 2 (Feb.), 155-169.
	90	Michael Stonebraker , Heidi Stettner , Nadene Lynn , Joseph Kalash , Antonin Guttman, Document processing in a relational database system, ACM Transactions on Information Systems (TOIS), v.1 n.2, p.143-158, April 1983 [doi>10.1145/357431.357433]
	91	Dennis Tsichritzis , Stavros Christodoulakis, Message files, ACM Transactions on Information Systems (TOIS), v.1 n.1, p.88-98, Jan. 1983 [doi>10.1145/357423.357429]
	92	Dennis Tsichritzis , Stavros Christodoulakis , P. Economopoulos , Christos Faloutsos , A. Lee , D. Lee , J. Vandenbroeck , Carson C. Woo, A Multimedia Office Filing System, Proceedings of the 9th International Conference on Very Large Data Bases, p.2-7, October 31-November 02, 1983
	93	VAN RIJSBERGEN, C. J. 1971. An algorithm for information structuring and retrieval. Comput. J. 14, 4, pp. 407-412.
	94	C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
	95	WELCH, T. A. 1984. A technique for high-performance data compression. IEEE Comput. Mag. 17, 6 (June), 8-19.
	96	WINe, J. M. 1979. Partial-match retrieval using TRIES, hashing and superimposed codes. M.Sc. thesis, MIT, June.
	97	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]
	98	C. T. Yu , K. Lam , G. Salton, Term Weighting in Information Retrieval Using the Term Precision Model, Journal of the ACM (JACM), v.29 n.1, p.152-170, Jan. 1982 [doi>10.1145/322290.322300]
	99	ZAHN, C. T. 1971. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Trans. Comput. C-20, i (Jan.), 68-86.
	100	ZIV, J., AND LEMPEL, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. In{. Theor. IT-23, 3 (May), 337-343.

CITED BY 86

	Surajit Chaudhuri , Umeshwar Dayal , Tak W. Yan, Join queries with external text sources: execution and optimization techniques, ACM SIGMOD Record, v.24 n.2, p.410-422, May 1995
	Fazli Can, Incremental clustering for dynamic information processing, ACM Transactions on Information Systems (TOIS), v.11 n.2, p.143-164, April 1993
	Lon-Mu Liu , Yair M. Babad , Wei Sun , Ki-Kan Chan, Adaptive post-processing of OCR text via knowledge acquisition, Proceedings of the 19th annual conference on Computer Science, p.558-569, April 1991, San Antonio, Texas, United States
	Yangjun Chen , Karl Aberer, Layered index structures in document database systems, Proceedings of the seventh international conference on Information and knowledge management, p.406-413, November 02-07, 1998, Bethesda, Maryland, United States
	J. W. Chang , J. H. Lee , Y. J. Lee, Multikey access methods based on term discrimination and signature clustering, ACM SIGIR Forum, v.23 n.SI, p.176-185, June 1989
	R. Sacks-Davis , P. Wallis , R. Wilkinson, Using syntactic analysis in a document retrieval system that uses signature files, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.179-192, September 05-07, 1990, Brussels, Belgium
	J. K. Cringean , R. England , G. A. Manson , P. Willett, Parallel text searching in serial files using a processor farm, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.429-453, September 05-07, 1990, Brussels, Belgium
	Aristides Gionis , Dimitrios Gunopulos , Nick Koudas, Efficient and tumble similar set retrieval, ACM SIGMOD Record, v.30 n.2, p.247-258, June 2001
	R. Sacks-Davis , A. Kent , K. Ramamohanarao, Multikey access methods based on superimposed coding techniques, ACM Transactions on Database Systems (TODS), v.12 n.4, p.655-696, Dec. 1987
	Yoshiharu Ishikawa , Hiroyuki Kitagawa , Nobuo Ohbo, Evaluation of signature files as set access facilities in OODBs, ACM SIGMOD Record, v.22 n.2, p.247-256, June 1, 1993
	Chen-Chuan K. Chang , Héctor Garcia-Molina , Andreas Paepcke, Predicate rewriting for translating Boolean queries in a heterogeneous information system, ACM Transactions on Information Systems (TOIS), v.17 n.1, p.1-39, Jan. 1999
	Björn T. Jónsson , Michael J. Franklin , Divesh Srivastava, Interaction of query evaluation and buffer management for information retrieval, ACM SIGMOD Record, v.27 n.2, p.118-129, June 1998
	Robert W.P. Luk , H. V. Leong , Tharam S. Dillon , Alvin T.S. Chan , W. Bruce Croft , James Allan, A survey in indexing and searching XML documents, Journal of the American Society for Information Science and Technology, v.53 n.6, p.415-437, May, 2002
	Arvind Arasu , Junghoo Cho , Hector Garcia-Molina , Andreas Paepcke , Sriram Raghavan, Searching the Web, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.2-43, Aug. 2001
	Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996
	Fazli Can , Yuan-Ming Lee, HypIR: a hypertext-based approach to information retrieval, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.729-736, February 14-16, 1993, Indianapolis, Indiana, United States
	Dik Lun Lee , Chun-Wu Leng, Partitioned signature files: design issues and performance evaluation, ACM Transactions on Information Systems (TOIS), v.7 n.2, p.158-180, April 1989
	Lee-Feng Chien, PAT-tree-based keyword extraction for Chinese information retrieval, ACM SIGIR Forum, v.31 n.SI, p.50-58
	Justin Zobel , Alistair Moffat , Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing, ACM Transactions on Database Systems (TODS), v.23 n.4, p.453-490, Dec. 1998
	Yong S. Choi , Suk I. Yoo, Multi-agent learning approach to WWW information retrieval using neural network, Proceedings of the 4th international conference on Intelligent user interfaces, p.23-30, January 05-08, 1999, Los Angeles, California, United States
	Charu C. Aggarwal , Joel L. Wolf , Kun-Lung Wu , Philip S. Yu, Horting hatches an egg: a new graph-theoretic approach to collaborative filtering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.201-212, August 15-18, 1999, San Diego, California, United States
	Eric W. Brown, Fast evaluation of structured queries for information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.30-38, July 09-13, 1995, Seattle, Washington, United States
	T. Ito , M. Kubota, A retrieval system for on-line English-Japanese dictionaries, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.181-186, June 03-05, 1987, New Orleans, Louisiana, United States
	Essam A. El-Kwae , Mansur R. Kabuka, Efficient content-based indexing of large image databases, ACM Transactions on Information Systems (TOIS), v.18 n.2, p.171-210, April 2000
	Uwe Deppisch, S-tree: a dynamic balanced signature index for office retrieval, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.77-87, September 1986, Palazzo dei Congressi, Pisa, Italy
	Yong Kyu Lee , Seong-Joon Yoo , Kyoungro Yoon , P. Bruce Berra, Index structures for structured documents, Proceedings of the first ACM international conference on Digital libraries, p.91-99, March 20-23, 1996, Bethesda, Maryland, United States
	Tamas E. Doszkocs, IR, NLP, AI and UFOS: or IR-relevance, natural language problems, artful intelligence and user-friendly online systems, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.49-57, September 1986, Palazzo dei Congressi, Pisa, Italy
	F. J. Burkowski, Surrogate subsets: a free space management strategy for the index of a text retrieval system, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.211-226, September 05-07, 1990, Brussels, Belgium
	Lee-Feng Chien, Fast and quasi-natural language search for gigabytes of Chinese texts, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.112-120, July 09-13, 1995, Seattle, Washington, United States
	John Light, A distributed, graphical, topic-oriented document search system, Proceedings of the sixth international conference on Information and knowledge management, p.285-292, November 10-14, 1997, Las Vegas, Nevada, United States
	Yangjun Chen, Signature files and signature trees, Information Processing Letters, v.82 n.4, p.213-221, 31 May 2002
	David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
	Roger King , Ali Morfeq, Bayan: an Arabic text database management system, ACM SIGMOD Record, v.19 n.2, p.12-23, Jun. 1990
	Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993
	C. Eastman, File organizations & incrementally specified queries, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.217-222, June 03-05, 1987, New Orleans, Louisiana, United States
	Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, ACM SIGMOD Record, v.23 n.2, p.419-429, June 1994
	Peter Schäuble, SPIDER: a multiuser information retrieval system for semistructured and dynamic data, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-327, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States
	C. Mic Bowman , Peter B. Danzig , Udi Manber , Michael F. Schwartz, Scalable Internet resource discovery: research problems and approaches, Communications of the ACM, v.37 n.8, p.98-ff., Aug. 1994
	Anthony Tomasic , Hector Garcia-Molina, Query processing and inverted indices in shared: nothing text document information retrieval systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.3, July 1993
	D. H. -C. Du , S. Ghanta , K. J. Maly , S. M. Sharrock, An Efficient File Structure for Document Retrieval in the Automated Office Environment, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.258-273, June 1989
	Alistair Moffat , Justin Zobel , Neil Sharman, Text Compression for Dynamic Document Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.2, p.302-313, March 1997
	Yangjun Chen , Gerald Huck, Building signature-trees on path signatures in document databases, Effective databases for text & document management, Idea Group Publishing, Hershey, PA, 2003
	Ron Sacks-Davis , Alan Kent , Kotagiri Ramamohanarao , James Thom , Justin Zobel, Atlas: A Nested Relational Database System for Text Applications, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.454-470, June 1995
	Suleiman H. Mustafa, A morphology-driven string matching approach to Arabic text searching, Journal of Systems and Software, v.67 n.2, p.77-87, 15 August 2003
	C. S. Hartzman , C. R. Watters, A Relational Approach to Querying Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.2 n.4, p.401-409, December 1990
	Yangjun Chen , Yibin Chen, Signature file hierarchies and signature graphs: a new index method for object-oriented databases, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	S. Ayse Özel , I. Sengör Altingövde , Özgür Ulusoy , Gültekin Özsoyoǧlu , Z. Meral Özsoyoǧlu, Metadata-based modeling of information resources on the Web, Journal of the American Society for Information Science and Technology, v.55 n.2, p.97-110, January 15, 2004
	Roger Weber , Michael Mlivoncic, Efficient region-based image retrieval, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Fidel Cacheda , Angel Viña, Superimposing codes representing hierarchical information in web directories, Proceedings of the 3rd international workshop on Web information and data management, November 09-01, 2001, Atlanta, Georgia, USA
	K. Takahashi , H. Yamada , H. Nagai , K. Matsumi, A new string search hardware architecture for VLSI, ACM SIGARCH Computer Architecture News, v.14 n.2, p.20-27, June 1986
	Anthony Tomasic , Hector Garcia-Molina, Caching and database scaling in distributed shared-nothing information retrieval systems, ACM SIGMOD Record, v.22 n.2, p.129-138, June 1, 1993
	Xian Liu , Wilsun Xu, A Stochastic Programming Approach for Range Query Retrieval Problems, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.867-880, July 2002
	Dik Lun Lee , Young Man Kim , Gaurav Patel, Efficient Signature File Methods for Text Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.423-435, June 1995
	Ben Carterette , Fazli Can, Comparing inverted files and signature files for searching a large lexicon, Information Processing and Management: an International Journal, v.41 n.3, p.613-633, May 2005
	Kjetil Nørvåg, Fine-granularity signature caching in object database systems, Data Engineering, v.38 n.2, p.101-119, 08/01/2001
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Cher-Sheng Cheng , Jean Jyh-Jiun Shann , Chung-Ping Chung, Unique-order interpolative coding for fast querying and space-efficient indexing in information retrieval systems, Information Processing and Management: an International Journal, v.42 n.2, p.407-428, March 2006
	Rasmus Kaae , Thanh-Duy Nguyen , Dennis Nørgaard , Albrecht Schmidt, Kalchas: a dynamic XML search engine, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	R. A. Baeza-Yates, Algorithms for string searching, ACM SIGIR Forum, v.23 n.3-4, p.34-58, Spring 1989
	Dik Lun Lee , Frederick H. Lochovsky, HYTREM-A Hybrid Text-Retrieval Machine for Large Databases, IEEE Transactions on Computers, v.39 n.1, p.111-123, January 1990
	Vuk Ercegovac , David J. DeWitt , Raghu Ramakrishnan, The TEXTURE benchmark: measuring performance of text queries on a relational DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Yangjun Chen , Yibin Chen, A new tree inclusion algorithm, Information Processing Letters, v.98 n.6, p.253-262, 30 June 2006
	Merrill E. Iseman , Dennis E. Shasha, Performance and Architectural Issues for String Matching, IEEE Transactions on Computers, v.39 n.2, p.238-250, February 1990
	Yangjun Chen, On the cost of searching signature trees, Information Processing Letters, v.99 n.1, p.19-26, 16 July 2006
	Lin Xu , Curtis Dyreson, Approximate retrieval of XML data with ApproXPath, Proceedings of the nineteenth conference on Australasian database, December 03-04, 2007, Gold Coast, Australia
	Yangjun Chen , Yibin Chen, On the top-down tree inclusion, Proceedings of the 2nd IASTED international conference on Advances in computer science and technology, p.61-66, January 23-25, 2006, Puerto Vallarta, Mexico
	Soumyadeb Mitra , Windsor W. Hsu , Marianne Winslett, Trustworthy keyword search for regulatory-compliant records retention, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006
	Srinidhi Varadarajan , Tzi-cker Chiueh, SASE: implementation of a compressed text search engine, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.23-23, December 08-11, 1997, Monterey, California
	Liam R. E. Quin, A text retrieval package for the unix operating system, Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference, p.16-16, June 06-10, 1994, Boston, Massachusetts
	Udi Manber , Sun Wu, GLIMPSE: a tool to search through entire file systems, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.4-4, January 17-21, 1994, San Francisco, California
	A. Mili , R. Mili , R. T. Mittermeir, A survey of software reuse libraries, Annals of Software Engineering, 5, p.349-414, 1998
	Ke Wang, Discovering Patterns from Large and Dynamic Sequential Data, Journal of Intelligent Information Systems, v.9 n.1, p.33-56, July/Aug. 1997
	Justin Zobel , James A. Thom , Ron Sacks-Davis, Efficiency of Nested Relational Document Database Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.91-102, September 03-06, 1991
	Alan J. Kent , Ron Sacks-Davis , Kotagiri Ramamohanarao, A Superimposed Coding Scheme Based on Multiple Block Descriptor Files for Indexing Very Large Data Bases, Proceedings of the 14th International Conference on Very Large Data Bases, p.351-359, August 29-September 01, 1988
	Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
	Justin Zobel , Alistair Moffat , Ron Sacks-Davis, An Efficient Indexing Technique for Full Text Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.352-362, August 23-27, 1992
	Eric W. Brown , James P. Callan , W. Bruce Croft, Fast Incremental Indexing for Full-Text Information Retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, p.192-202, September 12-15, 1994
	Christos Faloutsos , Raphael Chan, Fast Text Access Methods for Optical and Large Magnetic Disks: Designs and Performance Comparison, Proceedings of the 14th International Conference on Very Large Data Bases, p.280-293, August 29-September 01, 1988
	Giuseppe Amato , Giovanni Mainetto , Pasquale Savino, An Approach to a Content-Based Retrieval ofMultimedia Data, Multimedia Tools and Applications, v.7 n.1-2, p.9-36, July 1998
	Kyuchul Lee , Yong Kyu Lee , P. Bruce Berra, Management of Multi-structured Hypermedia Documents: A Data Model, Query Language, and Indexing Scheme, Multimedia Tools and Applications, v.4 n.2, p.199-223, March 1997
	Yibin Chen, On the Signature Tree Construction and Analysis, IEEE Transactions on Knowledge and Data Engineering, v.18 n.9, p.1207-1224, September 2006
	Soumyadeb Mitra , Marianne Winslett , Windsor W. Hsu, Query-based partitioning of documents and indexes for information lifecycle management, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	I. Elizabeth Shanthi , Y. Izaaz , R. Nadarajan, On the SD-tree construction for optimal signature operations, Proceedings of the 1st Bangalore annual Compute conference, January 18-20, 2008, Bangalore, India
	Taketoshi Ushiama , Toyohide Watanabe, A framework for personal content search and recommendation based on personal experiences, International Journal of Advanced Intelligence Paradigms, v.1 n.2, p.151-162, April 2008
	Mo Li , Yunhao Liu, Underground coal mine monitoring with wireless sensor networks, ACM Transactions on Sensor Networks (TOSN), v.5 n.2, p.1-29, March 2009

INDEX TERMS

Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.2 Physical Design
Subjects: Access methods
H.3 INFORMATION STORAGE AND RETRIEVAL
H.4 INFORMATION SYSTEMS APPLICATIONS

I. Computing Methodologies
I.7 DOCUMENT AND TEXT PROCESSING

General Terms:
Design

REVIEW

"Harold Borko : Reviewer"

Automated text retrieval methods are used in libraries and in many online bibliographic and numerical data files. They provide the library user with fast and accurate access to books and journal papers. Text retrieval is also important in office more...

Collaborative Colleagues:

Chris Faloutsos: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player