com.googlecode.concurrent-trees:concurrent-trees

"A tree is a tree. How many more do you have to look at?"

―Ronald Reagan

Concurrent Trees

This project provides concurrent Radix Trees and concurrent Suffix Trees for Java.

Overview

A Radix Tree (also known as patricia trie, radix trie or compact prefix tree) is a space-optimized tree data structure which allows keys (and optionally values associated with those keys) to be inserted for subsequent lookup using only a prefix of the key rather than the whole key. Radix trees have applications in string or document indexing and scanning, where they can allow faster scanning and lookup than brute force approaches. Some applications of Radix Trees:

• Associate objects with keys which have a natural hierarchy (for example nested categories, or paths in a file system)
• Scan documents for large numbers of keywords in a scalable way (i.e. more scalable than naively running document.contains(keyword), see below)
• Build indexes supporting fast "starts with", "ends with" or "equals" lookup
• Support auto-complete or query suggestion, for partial queries entered into a search box

A Suffix Tree (also known as PAT tree or position tree) is an extension of a radix tree which allows the suffixes of keys to be inserted into the tree. This allows subsequent lookup using any suffix or fragment of the key rather than the whole key, and in turn this can support fast string operations or analysis of documents. Some applications of Suffix Trees:

• Build indexes supporting fast "ends with" or "contains" lookup
• Perform more complex analyses of collections of documents, such as finding common substrings

The implementation in this project is actually a Generalized Suffix Tree.

Concurrency Support

All of the trees (data structures and algorithms) in this project are optimized for high-concurrency and high performance reads, and low-concurrency or background writes:

• Reads are lock-free (reading threads never block, even while writes are ongoing)
• Reading threads always see a consistent version of the tree
• Reading threads do not block writing threads
• Writing threads block each other but never block reading threads

As such reading threads should never encounter latency due to ongoing writes or other concurrent readers.

Tree Design

The trees in this project support lock-free reads while allowing concurrent writes, by treating the tree as a mostly-immutable structure, and assembling the changes to be made to the tree into a patch, which is then applied to the tree in a single atomic operation.

Inserting an entry into Concurrent Radix Tree which requires an existing node within the tree to be split:

• Reading threads traversing the tree while the patch above is being applied, will either see the old version or the new version of the (sub-)tree, but both versions are consistent views of the tree, which preserve the invariants. For more details see TreeDesign.

Tree Implementations

Feature matrix for tree implementations provided in this project, and lookup operations supported.

Tree Interface	Implementation	Key Equals (exact match)	Key Starts With	Key Ends With	Key Contains	Find Keywords In External Documents [1]
RadixTree	ConcurrentRadixTree	✓	✓
ReversedRadixTree	ConcurrentReversedRadixTree	✓		✓
InvertedRadixTree	ConcurrentInvertedRadixTree	✓	✓			✓
SuffixTree	ConcurrentSuffixTree	✓		✓	✓

^[1] Scanning for Keywords in External Documents

ConcurrentInvertedRadixTree allows unseen documents to be scanned efficiently for keywords contained in the tree, and performance does not degrade as additional keywords are added.

Let d = number of characters in document, n = number of keywords, k = average keyword length

Keyword scanning approach	Time Complexity (Number of character comparisons)	Example: 10000 10-character keywords, 10000 character document
Naive document.contains(keyword) for every keyword	O(d n k)	1,000,000,000 character comparisons
ConcurrentInvertedRadixTree	O(d log(k))	10,000 character comparisons (≤100,000 times faster)

Solver Utilities

Utilities included which solve problems using the included trees.

Solver	Solves
LCSubstringSolver	Longest common substring problem

Documentation and Example Usage

General Documentation

• JavaDocs - APIs
• Discussion Group - Post questions here
• FrequentlyAskedQuestions - Frequently Asked Questions, for various values of frequently
• NodeFactoryAndMemoryUsage - How to use custom node implementations and manage memory
• TreeDesign - Overview of the approach to concurrency

For more documentation see the documentation directory.

Example Usage

• ConcurrentRadixTreeUsage - Example Usage for Concurrent Radix Tree
• ConcurrentReversedRadixTreeUsage - Example Usage for Concurrent Reversed Radix Tree
• ConcurrentInvertedRadixTreeUsage - Example Usage for Concurrent Inverted Radix Tree
• ConcurrentSuffixTreeUsage - Example Usage for Concurrent Suffix Tree
• LCSubstringSolverUsage - Example Usage to find the Longest Common Substring in a collection of documents
• InMemoryFileSystemUsage - Example Usage for an In-Memory File System proof of concept based on Concurrent Radix Tree

Usage in Maven and Non-Maven Projects

Concurrent-Trees is in Maven Central. See Downloads.

Related Projects

• CQEngine, a NoSQL indexing and query engine with ultra-low latency

Project Status

As of writing (December 2016), version 2.6.0 of concurrent-trees is the latest release.

• Full test coverage
• Over 14,000 downloads per month and over 150,000 downloads to-date

See Release Notes and Frequently Asked Questions for details.

Report any bugs/feature requests in the Issues tab. For support please use the Discussion Group, not direct email to the developers.