Article

Free access

Searching a two key table under a single key

Author:

J. I. MunroAuthors Info & Claims

STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing

Pages 383 - 387

https://doi.org/10.1145/28395.28436

Published: 01 January 1987 Publication History

PDF eReader

Abstract

We present a method for arranging an arbitrary 2-key table as an n by 2 array such that a search can be performed under either key in O(lg²n lglg n) time. This is in sharp contrast with an Ω(√n) lower bound for the problem under a model in which all comparisons must involve the value being searched for.

References

[1]

H. Alt and K. MeNhom, Searching Semisorted TaNes, SiCOMP, vot. 14 no. 4, 1985, pp. 840-848.

Google Scholar

[2]

H. Alt, K. MeNhom and J.I. Mum-o, Partial Match Retrieval in Implicit Data Structures, Information Processing Letters, vol. 19 no. 2, 1984, pp. 61-65.

Digital Library

Google Scholar

[3]

J. Bentley, Multidimensional Binary Search Trees Used for Associative Searching, CACM 18, 9, Sept. 1975, pp. 509-516.

Digital Library

Google Scholar

[4]

A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigclerson, Tradeoff Between Search and Update Time for the Implicit Dictionary Problem, Proe. ICALP, 1986, pp. 50-59.

Digital Library

Google Scholar

[5]

A. Borodin, L. Guibas, N. Lynch and A. Yao, Efficient Searching Using Partial Ordering, Information Prying Letters, vol. 12 no. 2, 1981, pp. 71-75.

Crossref

Google Scholar

[6]

$. C.~k, pet~nal communication.

Google Scholar

[7]

G.N. Frederickson, Implicit Data Structures for the Dictionary Problem, J. ACM, vol. 30 no. 1, 1983, pp. 80-94.

Digital Library

Google Scholar

[8]

J.I. Munro, A Multikey Search Problem, Proc. Allerton, 1979, pp. 241- 244.

Google Scholar

[9]

J.I. Munro, An Implicit Data Structure Supporting Insertion, Deletion and Search in 0(log2n) Time, JCSS 33, 1, Aug. 1986, pp. 66-74.

Digital Library

Google Scholar

[10]

J.I. Munro and H. Suwanda, Implicit Data Structures, JCSS, vol. 21, 1980, pp. 236-250.

Google Scholar

[11]

J.W.J. Williams, Algorithms 232: Heal:~rt, CACM 71, 1964, pp. 347- 348.

Google Scholar

Cited By

View all

Lam TLee K(2005)The implicit dictionary problem revisitedAlgorithms and Computation10.1007/3-540-56279-6_100(479-488)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-56279-6_100
Tsotras VGopinath B(2005)Efficient algorithms for managing the history of evolving databasesICDT '9010.1007/3-540-53507-1_75(141-174)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-53507-1_75
Franceschini GMunro I(2004)Proximity MergesortProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/982792.982833(291-299)Online publication date: 11-Jan-2004
https://dl.acm.org/doi/10.5555/982792.982833
Show More Cited By

Index Terms

Searching a two key table under a single key

Recommendations

Hashing, searching, sketching
Full table quadratic searching for scatter storage

The quadratic residue search method for hash tables avoids much of the clustering experienced with a linear search method. The simple quadratic search only accesses half the table. It has been shown that when the length of the table is a prime of the ...
Randomization does not help searching predecessors
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

At STOC'06, we presented a new technique for proving cell-probe lower bounds for static data structures with deterministic queries. This was the first technique which could prove a bound higher than communication complexity, and it gave the first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing

January 1987

471 pages

ISBN:0897912217

DOI:10.1145/28395

Editor:
Alfred V. Aho

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC87

Sponsor:

SIGACT

STOC87: 19th Annual ACM Conference on Theory of Computing

New York, New York, USA

Acceptance Rates

STOC '87 Paper Acceptance Rate 50 of 165 submissions, 30%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
319
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)9

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lam TLee K(2005)The implicit dictionary problem revisitedAlgorithms and Computation10.1007/3-540-56279-6_100(479-488)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-56279-6_100
Tsotras VGopinath B(2005)Efficient algorithms for managing the history of evolving databasesICDT '9010.1007/3-540-53507-1_75(141-174)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-53507-1_75
Franceschini GMunro I(2004)Proximity MergesortProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/982792.982833(291-299)Online publication date: 11-Jan-2004
https://dl.acm.org/doi/10.5555/982792.982833
Fiat ANaor MSchmidt JSiegel ASimon J(1988)Non-oblivious hashingProceedings of the twentieth annual ACM symposium on Theory of computing10.1145/62212.62248(367-376)Online publication date: 1-Jan-1988
https://dl.acm.org/doi/10.1145/62212.62248
Fiat ANaor MSchäffer ASchmidt JSiegel ASimon J(1988)Storing and searching a multikey tableProceedings of the twentieth annual ACM symposium on Theory of computing10.1145/62212.62245(344-353)Online publication date: 1-Jan-1988
https://dl.acm.org/doi/10.1145/62212.62245

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Hashing, searching, sketching

Full table quadratic searching for scatter storage

Randomization does not help searching predecessors