PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric

Full text

Pdf (1.52 MB)

Source

Journal of the ACM (JACM) archive
Volume 15 , Issue 4 (October 1968) table of contents

Pages: 514 - 534

Year of Publication: 1968

ISSN:0004-5411

Author

Donald R. Morrison

Sandia Laboratory, Computer Science, Division 5256, Albuquerque, New Mexico

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 69, Downloads (12 Months): 506, Citation Count: 91

Additional Information:

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

ABSTRACT

PATRICIA is an algorithm which provides a flexible means of storing, indexing, and retrieving information in a large file, which is economical of index space and of reindexing time. It does not require rearrangement of text or index as new material is added. It requires a minimum restriction of format of text and of keys; it is extremely flexible in the variety of keys it will respond to. It retrieves information in response to keys furnished by the user with a quantity of computation which has a bound which depends linearly on the length of keys and the number of their proper occurrences and is otherwise independent of the size of the library. It has been implemented in several variations as FORTRAN programs for the CDC-3600, utilizing disk file storage of text. It has been applied to several large information-retrieval problems and will be applied to others.

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	Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
	2	MORRISON, DONALD R. PATRICiA--Practical Algorithm to Retrieve Information Coded in Alphanumeric. Res. Rep. SC-RR-67-734, Sandia Corp., Albuquerque, N. Mex., Oct. 1967.
	3	MORRISON, DONALD R. A library automaton. Unpublished notes.

CITED BY 91

	Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.3-14, Oct. 1997
	Mike O'Connor , Christopher A. Gomez, The iFlow Address Processor, IEEE Micro, v.21 n.2, p.16-23, March 2001
	Bernd Klauer , Andreas Bleck , Klaus Waldschmidt, The AM3 Associative Processor, IEEE Micro, v.15 n.2, p.70-78, April 1995
	Luc Devroye, Laws of large numbers and tail inequalities for random tries and PATRICIA trees, Journal of Computational and Applied Mathematics, v.142 n.1, p.27-37, 1 May 2002
	Amanda D. Poor , Paul S. Licker, Documentation retrieval in a University Computer Center environment, Proceedings of the 1969 24th national conference, p.77-81, August 26-28, 1969
	H. V. Jagadish , Nick Koudas , Divesh Srivastava, On effective multi-dimensional indexing for strings, ACM SIGMOD Record, v.29 n.2, p.403-414, June 2000
	Peter Bumbulis , Ivan T. Bowman, A compact B-tree, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Douglas Comer, Heuristics for trie index minimization, ACM Transactions on Database Systems (TODS), v.4 n.3, p.383-395, Sept. 1979
	Yasusi Kanada, Axis-specified search: a fine-grained full-text search method for gathering and structuring excerpts, Proceedings of the third ACM conference on Digital libraries, p.108-117, June 23-26, 1998, Pittsburgh, Pennsylvania, United States
	Willibald Doeringer , Günter Karjoth , Mehdi Nassehi, Routing on longest-matching prefixes, IEEE/ACM Transactions on Networking (TON), v.4 n.1, p.86-97, Feb. 1996
	E. R. Fiala , D. H. Greene, Data compression with finite windows, Communications of the ACM, v.32 n.4, p.490-505, April 1989
	Lee-Feng Chien, PAT-tree-based keyword extraction for Chinese information retrieval, ACM SIGIR Forum, v.31 n.SI, p.50-58
	Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States
	Marcel Waldvogel , George Varghese , Jon Turner , Bernhard Plattner, Scalable high-speed prefix matching, ACM Transactions on Computer Systems (TOCS), v.19 n.4, p.440-482, November 2001
	Timothy Bell , Ian H. Witten , John G. Cleary, Modeling for text compression, ACM Computing Surveys (CSUR), v.21 n.4, p.557-591, Dec. 1989
	P. Krishnan , Jeffrey Scott Vitter , Bala Iyer, Estimating alphanumeric selectivity in the presence of wildcards, ACM SIGMOD Record, v.25 n.2, p.282-293, June 1996
	Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001
	David E. Ferguson, Bit-Tree: a data structure for fast file processing, Communications of the ACM, v.35 n.6, p.114-120, June 1992
	Ricardo A. Baeza-Yates , Gaston H. Gonnet, Fast text searching for regular expressions or automaton searching on tries, Journal of the ACM (JACM), v.43 n.6, p.915-936, Nov. 1996
	Jason Tsong-Li Wang , Gung-Wei Chirn , Thomas G. Marr , Bruce Shapiro , Dennis Shasha , Kaizhong Zhang, Combinatorial pattern discovery for scientific data: some preliminary results, ACM SIGMOD Record, v.23 n.2, p.115-125, June 1994
	Beng Chin Ooi , Kian-Lee Tan, B-trees: bearing fruits of all kinds, Australian Computer Science Communications, v.24 n.2, p.13-20, January-February 2002
	Paolo Ferragina , Roberto Grossi, Fast string searching in secondary storage: theoretical developments and experimental results, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.373-382, January 28-30, 1996, Atlanta, Georgia, United States
	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
	Robert Bernecky, Representations for enclosed arrays, ACM SIGAPL APL Quote Quad, v.12 n.1, p.42-46, September 1981
	Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
	Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999
	Yangjun Chen , Duren Che , Karl Aberer, On the efficient evaluation of relaxed queries in biological databases, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	A. Blumer , J. Blumer , D. Haussler , R. McConnell , A. Ehrenfeucht, Complete inverted files for efficient text retrieval and analysis, Journal of the ACM (JACM), v.34 n.3, p.578-595, July 1987
	Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States
	Chris Clifton , Hector Garcie-Molina, The design of a document database, Proceedings of the ACM conference on Document processing systems, p.125-134, December 05-08, 1988, Santa Fe, New Mexico, United States
	Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, High-order entropy-compressed text indexes, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Chia-Hui Chang , Shao-Chen Lui, IEPAD: information extraction based on pattern discovery, Proceedings of the 10th international conference on World Wide Web, p.681-688, May 01-05, 2001, Hong Kong, Hong Kong
	František Franěk , Jan Holub , William F. Smyth , Xiangdong Xiao, Computing quasi suffix arrays, Journal of Automata, Languages and Combinatorics, v.8 n.4, p.593-606, April 2003
	Chia-Hui Chang , Chun-Nan Hsu , Shao-Cheng Lui, Automatic information extraction from semi-structured Web pages by pattern discovery, Decision Support Systems, v.35 n.1, p.129-147, 01 April 2003
	Paolo Ferragina , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Two-dimensional substring indexing, Journal of Computer and System Sciences, v.66 n.4, p.763-774, 1 June 2003
	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
	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
	Timothy Sherwood , George Varghese , Brad Calder, A pipelined memory architecture for high throughput network processors, ACM SIGARCH Computer Architecture News, v.31 n.2, May 2003
	Keh-Jiann Chen , Wen Tsuei , Lee-Feng Chien, PAT-trees with the deletion function as the learning device for linguistic patterns, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
	Jenq-Haur Wang , Jei-Wen Teng , Pu-Jen Cheng , Wen-Hsiang Lu , Lee-Feng Chien, Translating unknown cross-lingual queries in digital libraries using a web-based approach, Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2004, Tuscon, AZ, USA
	Walid G. Aref , Ihab F. Ilyas, SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees, Journal of Intelligent Information Systems, v.17 n.2-3, p.215-240, December 2001
	H. Shang , T. h. Merrettal, Tries for Approximate String Matching, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.540-547, August 1996
	Minsoo Jung , Masami Shishibori , Yasuhiro Tanaka , Jun-ichi Aoe, A dynamic construction algorithm for the compact patricia trie using the hierarchical structure, Information Processing and Management: an International Journal, v.38 n.2, p.221-236, March 2002
	Steffen Heinz , Justin Zobel , Hugh E. Williams, Burst tries: a fast, efficient data structure for string keys, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.192-223, April 2002
	Steffen Heinz , Justin Zobel, Performance of data structures for small sets of strings, Australian Computer Science Communications, v.24 n.1, p.87-94, January-February 2002
	A. Blumer , J. Blumer , A. Ehrenfeucht , D. Haussler , R. McConnell, Building a complete inverted file for a set of text files in linear time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.349-358, December 1984
	E. Oomoto , K. Tanaka, OVID: Design and Implementation of a Video-Object Database System, IEEE Transactions on Knowledge and Data Engineering, v.5 n.4, p.629-643, August 1993
	Gerth Stølting Brodal , Rolf Fagerberg, Cache-oblivious string dictionaries, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.581-590, January 22-26, 2006, Miami, Florida
	Anindya Basu , Girija Narlikar, Fast incremental updates for pipelined forwarding engines, IEEE/ACM Transactions on Networking (TON), v.13 n.3, p.690-703, June 2005
	Mayank Bawa , Tyson Condie , Prasanna Ganesan, LSH forest: self-tuning indexes for similarity search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu , Yitong Yin, Fast construction of overlay networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Mohammad J. Akhbarizadeh , Mehrdad Nourani, Hardware-based IP routing using partitioned lookup table, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.769-781, August 2005
	Rama Sangireddy , Natsuhiko Futamura , Srinivas Aluru , Arun K. Somani, Scalable, memory efficient, high-speed IP lookup algorithms, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.802-812, August 2005
	R. A. Baeza-Yates, Algorithms for string searching, ACM SIGIR Forum, v.23 n.3-4, p.34-58, Spring 1989
	Hamid Fadishei , Morteza Saheb Zamani , Masoud Sabaei, A novel reconfigurable hardware architecture for IP address lookup, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
	PATRICIA - II: two level overlayed indexes for large libraries, ACM SIGIR Forum, v.7 n.4, p.12-16, Winter 1972
	Mihail Halachev , Nematollaah Shiri , Anand Thamildurai, Exact match search in sequence data using suffix trees, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Jahangir Hasan , T. N. Vijaykumar, Dynamic pipelining: making IP-lookup truly scalable, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
	Fu-ren Lin , Chih-ming Hsueh, Knowledge map creation and maintenance for virtual communities of practice, Information Processing and Management: an International Journal, v.42 n.2, p.551-568, March 2006
	Strahil Ristov, LZ trie and dictionary compression, Software—Practice & Experience, v.35 n.5, p.445-465, 25 April 2005
	Xianghui Hu , Xinan Tang , Bei Hua, High-performance IPv6 forwarding algorithm for multi-core and multithreaded network processor, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Andrej Brodnik , Svante Carlsson , Michael L. Fredman , Johan Karlsson , J. Ian Munro, Worst case constant time priority queue, Journal of Systems and Software, v.78 n.3, p.249-256, December 2005
	Jenq-Haur Wang , Jei-Wen Teng , Wen-Hsiang Lu , Lee-Feng Chien, Exploiting the Web as the multilingual corpus for unknown query translation, Journal of the American Society for Information Science and Technology, v.57 n.5, p.660-670, March 2006
	Gonzalo Navarro , Edgar Chávez, A metric index for approximate string matching, Theoretical Computer Science, v.352 n.1, p.266-279, 7 March 2006
	Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States
	G. Badr , B. J. Oommen, On using conditional rotations and randomized heuristics for self-organizing ternary search tries, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
	Kai Zheng , Chengchen Hu , Hongbin Lu , Bin Liu, A TCAM-based distributed parallel IP lookup scheme and performance analysis, IEEE/ACM Transactions on Networking (TON), v.14 n.4, p.863-875, August 2006
	T. H. Merrett, Aldat: A retrospective on a work in progress, Information Systems, v.32 n.4, p.505-544, June, 2007
	Carsten Binnig , Stefan Hildenbrand , Franz Färber, Dictionary-based order-preserving string compression for main memory column stores, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Colin Meek , Jignesh M. Patel , Shruti Kasetty, OASIS: an online and accurate technique for local-alignment searches on biological sequences, Proceedings of the 29th international conference on Very large data bases, p.910-921, September 09-12, 2003, Berlin, Germany
	Jinlin Chen , Terry Cook, Mining contiguous sequential patterns from web logs, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	O. Demir , M. R. Head , K. Ghose , G. Govindaraju, Protecting Grid Data Transfer Services with Active Network Interfaces, Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, p.9-16, November 13-14, 2005
	Justin Zobel , Alistair Moffat , Ron Sacks-Davis, Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files, Proceedings of the 19th International Conference on Very Large Data Bases, p.290-301, August 24-27, 1993
	Naresh Soni , Nick Richardson , Lun-Bin Huang , Suresh Rajgopal , George Vlantis, NPSE: A High Performance Network Packet Search Engine, Proceedings of the conference on Design, Automation and Test in Europe: Designers' Forum, p.20074, March 03-07, 2003
	Mohamed Y. Eltabakh , Wing-Kai Hon , Rahul Shah , Walid G. Aref , Jeffrey S. Vitter, The SBC-tree: an index for run-length compressed sequences, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Luc Devroye , Gabor Lugosi , Gahyun Park , Wojciech Szpankowski, Multiple choice tries and distributed hash tables, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.891-899, January 07-09, 2007, New Orleans, Louisiana
	Chia-Hui Chang , Harianto Siek , Jiann-Jyh Lu , Chun-Nan Hsu , Jen-Jie Chiou, Reconfigurable Web Wrapper Agents, IEEE Intelligent Systems, v.18 n.5, p.34-40, September 2003
	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
	Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008
	Hamid Fadishei , Mehdi Saeedi , Morteza Saheb Zamani, A fast IP routing lookup architecture for multi-gigabit switching routers based on reconfigurable systems, Microprocessors & Microsystems, v.32 n.4, p.223-233, June, 2008
	Jesper Jansson , Kunihiko Sadakane , Wing-Kin Sung, Ultra-succinct representation of ordered trees, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.575-584, January 07-09, 2007, New Orleans, Louisiana
	Aleksandar Stojmirović , Vladimir Pestov, Indexing schemes for similarity search in datasets of short protein fragments, Information Systems, v.32 n.8, p.1145-1165, December, 2007
	Yeim-Kuan Chang , Yung-Chieh Lin, Dynamic Segment Trees for Ranges and Prefixes, IEEE Transactions on Computers, v.56 n.6, p.769-784, June 2007
	Jinlin Chen, Contiguous item sequential pattern mining using UpDown Tree, Intelligent Data Analysis, v.12 n.1, p.25-49, January 2008
	Mihai Stroe , Radu Berinde , Cosmin Negruseri , Dan Popovici, An approximate string matching approach for handling incorrectly typed urls, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Hasan Amjad, Data Compression for Proof Replay, Journal of Automated Reasoning, v.41 n.3-4, p.193-218, November 2008
	Jon Sneyers , Tom Schrijvers , Bart Demoen, The computational power and complexity of constraint handling rules, ACM Transactions on Programming Languages and Systems (TOPLAS), v.31 n.2, p.1-42, February 2009
	Haibin Liu , Christian Blouin , Vlado Kešelj, An unsupervised method for extracting domain-specific affixes in biological literature, Proceedings of the Workshop on BioNLP 2007: Biological, Translational, and Clinical Language Processing, June 29-29, 2007, Prague, Czech Republic
	Sharad Agarwal , Jacob R. Lorch, Matchmaking for online games and other latency-sensitive P2P systems, ACM SIGCOMM Computer Communication Review, v.39 n.4, October 2009
	Haibin Liu , Christian Blouin , Vlado Kešelj, Identifying interaction sentences from biological literature using automatically extracted patterns, Proceedings of the Workshop on BioNLP, June 04-05, 2009, Boulder, Colorado