Article

Free access

An associative/parallel processor for partial match retrieval using superimposed codes

Authors:

Sudhir R. Ahuja,

Charles S. RobertsAuthors Info & Claims

ISCA '80: Proceedings of the 7th annual symposium on Computer Architecture

Pages 218 - 227

https://doi.org/10.1145/800053.801929

Published: 06 May 1980 Publication History

Abstract

This paper presents the design and implementation of special hardware for effective use of the method of superimposed codes. It is shown that the method of superimposed codes is particularly well suited to easy design and implementation of fast and modular hardware. The implementation has shown that a performance gain of two orders of magnitude over conventional software implementations is obtained by using the special hardware. This makes the method of superimposed codes extremely attractive for data base system requiring partial match retrieval. We also demonstrate that the associative memory design is easily adaptable to large scale integration which would make such an approach very cost effective and lead to even further gains in performance.

References

[1]

Ahuja, S.R., "An Associative/Parallel Processor for Partial Match Retrieval Using Superimposed Codes," Internal Memorandum, Bell Laboratories,N.J., 07733, 1979.

[2]

Anderson, G. A., and Kain, R. Y., "A Content Addressed Memory Designed for Data Base Applications," Proc. 1976 International Conference on Parallel processing, WSU, pp. 191-195.

[3]

Bain, W. B. and Ahuja, S.R., "Performance Analysis of Digital Bus Arbitration Algorithms," Internal Memorandum, Bell Laboratories,N.J. 07733, 1979.

[4]

Bird, R. M., Tu, J. D., and Worthy, R. M., "Associative/Parallel Processors for Searching Very Large Textual Data Bases," Third Workshop on Computer Architecture for Non-Numeric Processing, 1977.

Digital Library

[5]

Bobeck, A. H., Bonyhard, P. I., and Gensie, J.E., "Magnetic Bubbles - An Emerging New Memory Technology," Proc. IEEE, August 1975, Vol. 63, pp. 1176-1195.

[6]

Gabbe, J.D.,London, T. B., Miller, R.E. and Beyer, J. D., "Applications of Superimposed Coding to Partial-Match Retrieval," COMPSAC 78,pp. 464-470.

[7]

Healy, L. D., Doty, K. L., and Lipovski, G. J., "The Architecture of a Context Addressed Segment Sequential Storage," Proc. AFIPS FJCC, Vol. 41, 1972, pp. 691-701.

[8]

Hodges, D. A., "A Review and Projection of Semiconductor Components for Digital Storage," Proc. IEEE, August 1975, Vol. 63, pp. 1136-1147.

[9]

Hsiao, D.K., Kannan K. and Kerr,D.S.,"Structure Memory designs for a Database Computer," Proc. ACM77.

Digital Library

[10]

Knuth, D.E., The Art of Computer Programming, vol.3,section 6.5, Addison-Wesley Publishing Company.

Digital Library

[11]

Mooers, C. N., "Zatocoding Applied to the Mechanical Organization of Knowledge," American Documentation, 2, pp. 20-232, 1951.

[12]

Ozkarahan, E. A., Schuster, S. A., and Smith, K. C., "RAP - Associative processor for Data Base Management," AFIPS Conf. Proc. 1975, Vol. 44, pp. 379-388.

[13]

Roberts, C. S., "Partial-Match Retrieval Via the Method of Superimposed Codes," Proceedings IEEE, vol.67, no.12,December 1979, pp. 1624-1642.

[14]

Schuster,S.A., Nguyen,H.B., Ozkarahan, E.A. and Smith, K.C., "RAP.2 - An Associative Processor for Databases and its Applications", IEEE TC June 1979, pp. 446-458.

Digital Library

[15]

Slotnick, D. L., "Logic per Track Devices," Advances in Computers, Vol. 10, Academic Press, 1970, pp. 291-296.

[16]

Smith, Diane C.P. and Smith, John M., "Relational Data Base Machines," COMPUTER vol.12, March 1979,pp.28-39.

Digital Library

[17]

Su, Stanley Y.W., "Cellular-Logic Devices: Concepts and Applications," COMPUTER vol. 12, March 1979.

[18]

Wing, J., "Partial-Match Retrieval Using Tries, Hashing, and Superimposed Codes," M.S. Thesis, M.I.T., 1979.

Cited By

Crainiceanu ALemire D(2015)BloofiInformation Systems10.1016/j.is.2015.01.00254:C(311-324)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.is.2015.01.002
Yuwono BLee D(2005)A backend text retrieval machine for signature-based document rankingAdvances in Computing and Information — ICCI '9110.1007/3-540-54029-6_177(288-297)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-54029-6_177
Chung SBerra P(2005)A comparison of concatenated and superimposed code word surrogate files for very large data/knowledge basesAdvances in Database Technology—EDBT '8810.1007/3-540-19074-0_63(364-387)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-19074-0_63
Show More Cited By

Index Terms

An associative/parallel processor for partial match retrieval using superimposed codes
1. Computer systems organization
  1. Architectures
    1. Parallel architectures

Recommendations

Uniqueness of some optimal superimposed codes

Four new results on the uniqueness of optimal superimposed codes are presented, namely, the uniqueness of ( w , r ) superimposed codes of size N T with $$N = \left( {\begin{array}{*{20}c} {w + r + 1} \\ w \\ \end{array} } \right)$$ and T = w + r + 1 and the uniqueness of (2, 2) superimposed codes of size 18 9, (2, 2) ...
New constructions of superimposed codes

Kautz-Singleton (1964) suggested a class of binary superimposed codes which are based on the q-ary Reed-Solomon codes (RS codes). Applying a concatenation of the binary constant-weight error-correcting codes and the shortened RS codes, we obtain new ...
Low-weight superimposed codes and related combinatorial structures: Bounds and applications
Abstract
A ( k , n )-superimposed code is a well known and widely used combinatorial structure that can be represented by a t × n binary matrix such that for any k columns of the matrix and for any column c chosen among these k columns, there ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '80: Proceedings of the 7th annual symposium on Computer Architecture

May 1980

333 pages

ISBN:9781450373906

DOI:10.1145/800053

Copyright © 1980 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

SIGCOMM: ACM Special Interest Group on Data Communication
AFCET: Assoc Francaise des Sciences
SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society
INRIA: Institut Natl de Recherche en Info et en Automatique
SEE: Société des Electriciens et des Electroniciens

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 May 1980

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
267
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Crainiceanu ALemire D(2015)BloofiInformation Systems10.1016/j.is.2015.01.00254:C(311-324)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.is.2015.01.002
Yuwono BLee D(2005)A backend text retrieval machine for signature-based document rankingAdvances in Computing and Information — ICCI '9110.1007/3-540-54029-6_177(288-297)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-54029-6_177
Chung SBerra P(2005)A comparison of concatenated and superimposed code word surrogate files for very large data/knowledge basesAdvances in Database Technology—EDBT '8810.1007/3-540-19074-0_63(364-387)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-19074-0_63
Ciaccia PTiberio PZezula P(1996)Declustering of key-based partitioned signature filesACM Transactions on Database Systems10.1145/232753.23275521:3(295-338)Online publication date: 1-Sep-1996
https://dl.acm.org/doi/10.1145/232753.232755
Edirisooriya SEdirisooriya G(1993)When to use partitioned signature files for retrieving information in multimedia systemsDigest of Papers. Compcon Spring10.1109/CMPCON.1993.289629(23-28)Online publication date: 1993
https://doi.org/10.1109/CMPCON.1993.289629
Grandi FTiberio PZezula PFox E(1992)Frame-sliced partitioned parallel signature filesProceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval10.1145/133160.133211(286-287)Online publication date: 1-Jun-1992
https://dl.acm.org/doi/10.1145/133160.133211
Winters V(1992)Parallelism for high performance query processingAdvances in Database Technology — EDBT '9210.1007/BFb0032441(344-356)Online publication date: 1992
https://doi.org/10.1007/BFb0032441
Tavakoli NModaress-Razavi H(1990)An architecture for parallel search of large, full-text databasesProceedings. PARBASE-90: International Conference on Databases, Parallel Architectures, and Their Applications10.1109/PARBSE.1990.77159(342-349)Online publication date: 1990
https://doi.org/10.1109/PARBSE.1990.77159
Lee DLeng C(1990)A partitioned signature file structure for multiattribute and text retrieval[1990] Proceedings. Sixth International Conference on Data Engineering10.1109/ICDE.1990.113492(389-396)Online publication date: 1990
https://doi.org/10.1109/ICDE.1990.113492
Lee DLochovsky F(1990)HYTREM-A Hybrid Text-Retrieval Machine for Large DatabasesIEEE Transactions on Computers10.1109/12.4628539:1(111-123)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.1109/12.46285
Show More Cited By

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