Parallel free-text search on the connection machine system

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel free-text search on the connection machine system

Full text

Pdf (1.04 MB)

Source

Communications of the ACM archive
Volume 29 , Issue 12 (December 1986) table of contents
Special issue on parallelism

Pages: 1229 - 1239

Year of Publication: 1986

ISSN:0001-0782

Authors

Craig Stanfill	Thinking Machines Corporation, Cambridge, MA
Brewster Kahle	Thinking Machines Corporation, Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 29, Citation Count: 56

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/7902.7907 What is a DOI?

ABSTRACT

A new implementation of free-text search using a new parallel computer—the Connection Machine®—makes possible the application of exhaustive methods not previously feasible for large databases.

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	David C. Blair , M. E. Maron, An evaluation of retrieval effectiveness for a full-text document-retrieval system, Communications of the ACM, v.28 n.3, p.289-299, March 1985 [doi>10.1145/3166.3197]
	2	D. J. Dodds, Reducing dictionary size by using a hashing technique, Communications of the ACM, v.25 n.6, p.368-370, June 1982 [doi>10.1145/358523.358547]
	3	W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
	4	Geoffrey James, Document databases, Van Nostrand Reinhold Co., New York, NY, 1984
	5	Kraay. T. Unpublished manuscript. MRJ, Fairfax, Va., Apr. 1986.
	6	Mott, P.M., Waltz, D.L., Resnikoff, H.L., and Robertson, G.G. Automatic indexing of text. Tech. Rep. 86-1, Thinking Machines Corp.. Cambridge. Mass.. Jan. 1986.
	7	Robert Nix, Experience with a space efficient way to store a dictionary, Communications of the ACM, v.24 n.5, p.297-298, May 1981 [doi>10.1145/358645.358654]
	8	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]
	9	Jerry L. Potter, The Massively Parallel Processor, MIT Press, Cambridge, MA, 1985
	10	G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
	11	Gerard Salton, Another look at automatic text-retrieval systems, Communications of the ACM, v.29 n.7, p.648-656, July 1986 [doi>10.1145/6138.6149]
	12	van Rijsbergen, C.J. It@mhor~ Retrieval. 2nd ed. Butterworths, London, 1979.

CITED BY 56

	R. G. Born , J. R. Kenevan, Analytic derivation of processor potential utilization in straight line, ring, square mesh, and hypercube networks, ACM SIGMETRICS Performance Evaluation Review, v.16 n.1, p.94-103, May 1988
	Brij Masand , Gordon Linoff , David Waltz, Classifying news stories using memory based reasoning, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.59-65, June 21-24, 1992, Copenhagen, Denmark
	Ramana Rao , Daniel M. Russell , Jock D. Mackinlay, System components for embedded information retrieval from multiple disparate information sources, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.23-33, December 1993, Atlanta, Georgia, United States
	C. Faloutsos , D. Metaxas, Declustering using error correcting codes, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.253-258, March 1989, Philadelphia, Pennsylvania, United States
	Paolo Ciaccia , Paolo Tiberio , Pavel Zezula, Declustering of key-based partitioned signature files, ACM Transactions on Database Systems (TODS), v.21 n.3, p.295-338, Sept. 1996
	Larry Press, Collective dynabases, Communications of the ACM, v.35 n.6, p.26-32, June 1992
	G. C. Fox, What have we learnt from using real parallel machines to solve real problems?, Proceedings of the third conference on Hypercube concurrent computers and applications, p.897-955, January 1989, Pasadena, California, United States
	Robert H. Creecy , Brij M. Masand , Stephen J. Smith , David L. Waltz, Trading MIPS and memory for knowledge engineering, Communications of the ACM, v.35 n.8, p.48-64, Aug. 1992
	Ross Wilkinson , Philip Hingston, Using the cosine measure in a neural network for document retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.202-210, October 13-16, 1991, Chicago, Illinois, United States
	R. K. Belew, Adaptive information retrieval: using a connectionist representation to retrieve and learn about documents, ACM SIGIR Forum, v.23 n.SI, p.11-20, June 1989
	Erol Gelenbe, Performance analysis of the connection machine, ACM SIGMETRICS Performance Evaluation Review, v.18 n.1, p.183-191, May 1990
	P. Efraimidis , C. Glymidakis , B. Mamalis , P. Spirakis , B. Tampakas, Parallel text retrieval on a high performance supercomputer using the Vector Space Model, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.58-66, July 09-13, 1995, Seattle, Washington, United States
	Scott Henninger, Retrieving software objects in an example-based programming environment, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.251-260, October 13-16, 1991, Chicago, Illinois, 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
	IJsbrand Jan Aalbersberg, Posting compression in dynamic retrieval environments, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.72-81, October 13-16, 1991, Chicago, Illinois, United States
	Fabio Grandi , Paolo Tiberio , Pavel Zezula, Frame-sliced partitioned parallel signature files, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.286-287, June 21-24, 1992, Copenhagen, Denmark
	Thomas Erickson , Gitta Salomon, Designing a desktop information system: observations and issues, Proceedings of the SIGCHI conference on Human factors in computing systems: Reaching through technology, p.49-54, April 27-May 02, 1991, New Orleans, Louisiana, United States
	Gerard Salton , James Allan , Chris Buckley, Automatic structuring and retrieval of large text files, Communications of the ACM, v.37 n.2, p.97-108, Feb. 1994
	David K. Gifford , Pierre Jouvelot , Mark A. Sheldon , James W. O'Toole, Jr., Semantic file systems, ACM SIGOPS Operating Systems Review, v.25 n.5, p.16-25, Oct. 1991
	W. Bruce Croft , Pasquale Savino, Implementing ranking strategies using text signatures, ACM Transactions on Information Systems (TOIS), v.6 n.1, p.42-62, Jan. 1988
	Brendon Cahoon , Kathryn S. McKinley , Zhihong Lu, Evaluating the performance of distributed architectures for information retrieval using a variety of workloads, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.1-43, Jan. 2000
	Roger E. Eggen , John R. Metzner, An inherently parlle large grained data flow environment, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.551-557, February 1988, Atlanta, Georgia, United States
	Craig Stanfill , David Waltz, Toward memory-based reasoning, Communications of the ACM, v.29 n.12, p.1213-1228, Dec. 1986
	Ophir Frieder , Hava Tova Siegelmann, On the allocation of documents in multiprocessor information retrieval systems, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.230-239, October 13-16, 1991, Chicago, Illinois, United States
	Gerard Salton, The smart document retrieval project, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.356-358, October 13-16, 1991, Chicago, Illinois, United States
	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
	C. Stanfill , R. Thau , D. Waltz, A parallel indexed algorithm for information retrieval, ACM SIGIR Forum, v.23 n.SI, p.88-97, June 1989
	Chun-Wu Roger Leng , Dik Lun Lee, Optimal weight assignment for signature generation, ACM Transactions on Database Systems (TODS), v.17 n.2, p.346-373, June 1992
	Christos Faloutsos , Stavros Christodoulakis, Description and performance analysis of signature file methods for office filing, ACM Transactions on Information Systems (TOIS), v.5 n.3, p.237-257, July 1987
	C. Stanfill, Partitioned posting files: a parallel inverted file structure for information retrieval, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.413-428, September 05-07, 1990, Brussels, Belgium
	Yangjun Chen, Signature files and signature trees, Information Processing Letters, v.82 n.4, p.213-221, 31 May 2002
	Z. Lin , C. Faloutsos, Frame-Sliced Signature Files, IEEE Transactions on Knowledge and Data Engineering, v.4 n.3, p.281-289, June 1992
	Dik Kun Lee , Liming Ren, Document ranking on weight-partitioned signature files, ACM Transactions on Information Systems (TOIS), v.14 n.2, p.109-137, April 1996
	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
	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
	P. Zezula , F. Rabitti , P. Tiberio, Dynamic partitioning of signature files, ACM Transactions on Information Systems (TOIS), v.9 n.4, p.336-367, Oct. 1991
	P. Zezula , F. Rabitti , P. Tiberio, Dynamic partitioning of signature files, ACM Transactions on Information Systems (TOIS), v.9 n.4, p.336-367, Oct. 1991
	M. V. Ramakrishna, Practical performance of Bloom filters and parallel free-text searching, Communications of the ACM, v.32 n.10, p.1237-1239, Oct. 1989
	IJsbrand Jan Aalbersberg, Incremental relevance feedback, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.11-22, June 21-24, 1992, Copenhagen, Denmark
	N. C. Rowe , A. Zaky, Load Balancing of Parallelized Information Filters, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.456-461, March 2002
	Victor Wing-Kit Mak , Kuo Chu Lee , Ophir Frieder, Exploiting parallelism in pattern matching: an information retrieval application, ACM Transactions on Information Systems (TOIS), v.9 n.1, p.52-74, Jan. 1991
	Gerard Salton , Chris Buckley, Parallel text search methods, Communications of the ACM, v.31 n.2, p.202-215, Feb. 1988
	K. L. Liu , G. J. Lipovski , C. Yu , Naphtali Rishe, Efficient processing of one and two dimensional proximity queries in associative memory, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.138-146, August 18-22, 1996, Zurich, Switzerland
	Dik L. Lee , Huei Chuang , Kent Seamons, Document Ranking and the Vector-Space Model, IEEE Software, v.14 n.2, p.67-75, March 1997
	Pascal Faudemay , Mongia Mhiri, An Associative Accelerator for Large Databases, IEEE Micro, v.11 n.6, p.22-34, November 1991
	T. Samad , P. Israel, A Browser for Large Knowledge Bases Based on a Hybrid Distributed/Local Connectionist Architecture, IEEE Transactions on Knowledge and Data Engineering, v.3 n.1, p.89-99, March 1991
	Christos Faloutsos , Dimitris Metaxas, Disk Allocation Methods Using Error Correcting Codes, IEEE Transactions on Computers, v.40 n.8, p.907-914, August 1991
	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
	Computer Staff, Letters to the Editor, Computer, v.21 n.1, p.7-8, 10, January 1988
	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
	M. F. Khan , Ray Paul , Ishfaq Ahmed , Arif Ghafoor, Intensive Data Management in Parallel Systems: A Survey, Distributed and Parallel Databases, v.7 n.4, p.383-414, Oct. 1999
	Neil C. Rowe, Using local optimality criteria for efficient information retrieval with redundant information filters, ACM Transactions on Information Systems (TOIS), v.14 n.2, p.138-174, April 1996
	K. C. Lee , O. Frieder , V. Mak, A parallel VLSI architecture for unformatted data processing, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.80-86, December 05-07, 1988, Austin, Texas, United States
	Robert W. P. Luk , Wai Lam, Efficient in-memory extensible inverted file, Information Systems, v.32 n.5, p.733-754, July, 2007
	Pavel Zezula , Paolo Ciaccia , Paolo Tiberio, Hamming Filters: A Dynamic Signature File Organization for Parallel Stores, Proceedings of the 19th International Conference on Very Large Data Bases, p.314-327, August 24-27, 1993
	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

INDEX TERMS

Classification:
C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD); Parallel processors**

H. Information Systems
H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Design, Performance

REVIEW

"Santosh Chokhani : Reviewer"

As the title suggests, this paper describes techniques to exploit parallelism of the Connection Machine for free-text search algorithms while searching natural-language documents contained in large databases, ranging from a few megabytes to a fe more...

Collaborative Colleagues:

Craig Stanfill: colleagues

Brewster Kahle: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player