More Web Proxy on the site http://driver.im/

research-article

Free access

Highly parallel associative search and its application to cellular database machine design

Author:

Sakti PramanikAuthors Info & Claims

AFIPS '81: Proceedings of the May 4-7, 1981, national computer conference

Pages 521 - 528

https://doi.org/10.1145/1500412.1500487

Published: 04 May 1981 Publication History

Abstract

This paper describes a fast associative search algorithm based on parallel searching by pattern-splitting. The text is read as a sequence of substrings and searching is parallel within each substring. Substring length can be arbitrarily chosen and this division is independent of the logical partitioning of the data, such as tuple and domain. This provides a flexible storage structure across tracks of the secondary storage. The algorithm developed is used in the design of a hardware associative search. It works directly on the secondary storage and is a basis for database machine design. The design is cellular in structure and can be implemented by using LSI technology.

References

[1]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, "The Design and Analysis of Computer Algorithms" Addison-Wesley, 1975: Reading, MA.

Digital Library

[2]

G. F. Amello, "Charged-coupled devices for memory applications", AFIPS Conf. Proc. Vol. 44 pp. 515--522, 1975.

Digital Library

[3]

R. M. Bird, J. C. Tu and R. M. Worthy, "Associative/parallel processors for searching very large textual data bases", 3rd Workshop on Computer Architecture and Nonnumeric Processing, Syracuse Univ., Syracuse, NY, May 17--18, 1977.

Digital Library

[4]

G. P. Copeland, G. J. Lipovsky, and S. Y. W. Su, "The Architecture of CASSM: A cellular system for nonumeric processing", 1st Annual Symp. on Computer Architecture, 1973.

Digital Library

[5]

C. J. Date, "An Introduction to Database Systems" 2nd Edition, Addison-Wesley, 1977: Reading, MA.

Digital Library

[6]

J. F. Gimpel, "Algorithms in SNOBOL4", Wiley Interscience, 1976.

Digital Library

[7]

A. K. Gillis, et al., "Holographic memories-fantasy or reality?". AFIPS Conf. Proc. Vol. 44 pp. 535--539, 1975.

Digital Library

[8]

N. C. Hughs, et al, "BEAMOS---A new electronic digital memory", AFIPS Conf. Proc. Vol. 44, pp. 541--548, 1975.

Digital Library

[9]

D. E. Knuth, J. H. Morris, and V. R. Pratt, "Fast pattern matching in strings", SIAM J. Comput. Vol. 6, No. 2, pp. 323--350, June 1977.

Digital Library

[10]

C. S. Lin, D. C. P. Smith, J. M. Smith, "The design of a rotating associative memory for relational database applications," ACM Trans. Data Base Systems, Vol. 1, pp. 53--65, 1976.

Digital Library

[11]

Stephen W. Miller, Ed. "Memory and Storage Technogy---@Vol. II" AFIPS Press, 1977.

[12]

N. Minsky, "Rotating storage devices as partially associative memories," Proc. ACM SIGFIDET Workshop on Data Description, Access, and Control, 1972.

[13]

Amar Mukhopadhyay, "Hardware algorithms for nonnumeric computation", IEEE Trans. Comput., Vol. C-28, June, 1979.

Digital Library

[14]

E. A. Ozkarahan, S. A. Schuster, and K. C. Smith, "RAP-An Associative processor for database management", National Computer Conference, 1975.

Digital Library

[15]

B. Parhami "A highly parallel computer system for information retrieval", Proc. Fall Joint Computer Conf., 1972.

Digital Library

[16]

J. L. Parker, "A logic per track retrieval systems", IFIP Congress, 1971.

[17]

S. B. Pramanik, Edgar T. Irons "A data-handling mechanics of on-line text editing systems with efficient secondary storage access", National Computer Conference, 1979.

[18]

S. B. Pramanik, "A mathematical model of character string manipulation", National Computer Conference, 1980.

Digital Library

[19]

S. B. Pramanik, "MAP EDITING", Ph.D. Thesis, Yale University, 1974.

Digital Library

[20]

C. V. Ramamoorthy, J. L. Turner, and B. W. Wah, "A design of a fast cellular associative memory for ordered retrieval", IEEE Trans. Comput. Vol. 2--27, Sept. 1978.

Digital Library

[21]

S. Y. W. Su, G. P. Copeland, and G. J. Lipovsky, "Retrieval operations and data representation in a context addressed disk system", Proc. ACM Programming Languages and Information Retrieval Interface Meeting, 1973.

Digital Library

[22]

D. L. Slotnick, "Logic per track devices", Advances in Computers, Academic Press, 1970.

Cited By

Lozinskii E(1986)A problem-oriented inferential database systemACM Transactions on Database Systems10.1145/6314.641911:3(323-356)Online publication date: 1-Aug-1986
https://dl.acm.org/doi/10.1145/6314.6419
Pramanik S(1982)Database filtersACM SIGARCH Computer Architecture News10.1145/1067649.80172810:3(201-210)Online publication date: 1-Apr-1982
https://dl.acm.org/doi/10.1145/1067649.801728

Recommendations

Prototyping Bubba, A Highly Parallel Database System

Bubba is a highly parallel computer system for data-intensive applications. The basis of the Bubba design is a scalable shared-nothing architecture which can scale up to thousands of nodes. Data are declustered across the nodes (i.e. horizontally ...
Evaluation of Associative Memory Using Parallel Chained Hashing

Two parallel hashing algorithms based on open and chained hashing are discussed. The parallel chained hashing algorithm is efficient even in the environment where deletion and insertion frequently occur. The chained hashing memory with fewer memory ...
Associative Parallel Containers in STAPL
Languages and Compilers for Parallel Computing

The Standard Template Adaptive Parallel Library (<Emphasis Type="SmallCaps">stapl</Emphasis>) is a parallel programming framework that extends C++ and <Emphasis Type="SmallCaps">stl</Emphasis>with support for parallelism. <Emphasis Type="SmallCaps">...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

AFIPS '81: Proceedings of the May 4-7, 1981, national computer conference

May 1981

736 pages

ISBN:9781450379212

DOI:10.1145/1500412

Copyright © 1981 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

AFIPS: American Federation of Information Processing Societies

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1981

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
109
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lozinskii E(1986)A problem-oriented inferential database systemACM Transactions on Database Systems10.1145/6314.641911:3(323-356)Online publication date: 1-Aug-1986
https://dl.acm.org/doi/10.1145/6314.6419
Pramanik S(1982)Database filtersACM SIGARCH Computer Architecture News10.1145/1067649.80172810:3(201-210)Online publication date: 1-Apr-1982
https://dl.acm.org/doi/10.1145/1067649.801728

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents