Patent application serial number 406549 has not been assigned to a company or institution.
The following quote was obtained by the news editors from the background information supplied by the inventors: "Tries are tree data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. A trie data structure turns a string set into a digital search tree. Several operations may be supported using the data structure, such as mapping the strings to integers, retrieving a string from the trie, performing prefix searches and many others. Thanks to their simplicity and functionality tries may be used in a variety of fields including but not limited to computational biology, data compression, data mining, information retrieval, natural language processing, network routing, pattern matching, text processing and web applications.
"A path-decomposed trie is a trie (tree data structure for storing a set of strings) where each node in the path decomposed trie represents a path in the trie. A path-decomposed trie is thus smaller than a trie from which it is formed and this reduces space requirements. Reducing space requirements is increasingly important, for example, for web-scale applications such as internet search engines and others. However, a trade-off may occur between reducing space requirements and reducing running time of the data structures during use for operations such as mapping the strings to integers, retrieving a string from the trie and other queries.
"The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known path-decomposed trie data structures."
In addition to the background information obtained for this patent application, VerticalNews journalists also obtained the inventors' summary information for this patent application: "The following presents a simplified summary of the disclosure in order to provide a basic understanding to the reader. This summary is not an extensive overview of the disclosure and it does not identify key/critical elements or delineate the scope of the specification. Its sole purpose is to present a selection of concepts disclosed herein in a simplified form as a prelude to the more detailed description that is presented later.
"Path-decomposed trie data structures are described, for example, for representing sets of strings in a succinct manner whilst still enabling fast operations on the string sets such as string retrieval or looking up a string with a specified identifier. A path-decomposed trie is a trie (tree data structure for storing a set of strings) where each node in the path decomposed trie represents a path in the trie. In various embodiments a path-decomposed trie data structure is represented succinctly by interleaving node labels and node degrees in an array and optionally by compressing the node labels using a static dictionary. Node labels may be string characters and a node degree may be a number of children of a node. In some embodiments a path-decomposed hollow trie data structure is used to provide a hash function for string sets.
"Many of the attendant features will be more readily appreciated as the same becomes better understood by reference to the following detailed description considered in connection with the accompanying drawings.
DESCRIPTION OF THE DRAWINGS
"The present description will be better understood from the following detailed description read in light of the accompanying drawings, wherein:
"FIG. 1 is a schematic diagram of a path-decomposed trie data structure used in conjunction with a search engine in an information retrieval system;
"FIG. 2 is a schematic diagram of a trie data structure;
"FIG. 3 is a schematic diagram of a path-decomposed trie;
"FIG. 4 is a flow diagram of a method of forming a succinct encoding of a path-decomposed trie;
"FIG. 5 is a schematic diagram of a succinct encoding of a path-decomposed trie;
"FIG. 6 is a schematic diagram of use of a dictionary to compress part of an encoding of a path-decomposed trie;
"FIG. 7 is a flow diagram of a method of forming a succinct encoding of a path-decomposed hollow trie;
"FIG. 8 illustrates an exemplary computing-based device in which embodiments of path-decomposed trie data structures may be implemented.
"Like reference numerals are used to designate like parts in the accompanying drawings."
URL and more information on this patent application, see: OTTAVIANO, Giuseppe. Path-Decomposed Trie Data Structures. U.S. Patent Application Serial Number 406549, filed
Keywords for this news article include: Patents, Information Technology, Information and Data Architecture.
Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2013, NewsRx LLC
Most Popular Stories
- Twitter Coming to Phones Without Internet
- Twitter Names Woman to Board
- Obamacare Doing Just Fine, Ky. Governor Says
- Rand Paul Signs up for Obamacare
- How to Arm Yourself Against CryptoLocker Virus
- Thalia Gets Star on Hollywood Walk of Fame
- World Cup Draws: Coaches, Players Offer Insights
- Hispanic Employment Improves in November
- Trapped Florida Whales Head for Deeper Waters
- Aspen Contracting Adding 300 Jobs