Cache-conscious String Data Structures, Sorting and Algorithms: theory and practice

If you want to learn more about cache-efficient string data structures, you should check out my PhD thesis as it contains a wealth of information that can help you gain a much better understanding on how these data structures work, what other researchers have published, and what to expect out of performance. You download my PhD thesis here.  Note: you may require the latest Adobe Acrobat Reader.

Want to learn how to sort over 252GB of data for a Penny?   Easy!

Follow these steps:

1. Have a read of my refereed Industry paper on external sorting here. This should give you a good understanding on how the algorithm works and the basic outline of hardware and performance expectations ... not to mention a few tips and tricks on fine-tuning both software and hardware.
2. Study my 2009 and 2010 PennySort winning submissions to see first-hand how the algorithm is implemented. You can find the non-commerical version of the source here.
3. Then try to write your own ... and you will be well on your way to besting the best in external sorting :)

Interested in learning how to efficiently implement the HAT-trie in C?  I now offer my original implementation which you can download below. Please note, however, that my software is for non-commercial use only. This means that my code (in whole or any part of it) can not be used in a commercial (profit/non-profit) environment, product or service, without my written permission. This is important. See the statement shown at the top of my code for more details. You can download the HAT-trie here.

Please read my papers on the HAT-trie and also study my code; and feel free to ask any questions you may have regarding my work.

Once understood, try beating it!   It's possible :)

• Your data structure must support null-terminated variable-length strings. No fancy string-terminators like '0xff' instead of '\0', which can lead to faster string comparisons.
• The length of the string can not be pre-calculated prior to using the data structure / its interfaces or API.
• No HugeTLB, custom Kernels, or over-clocked hardware.
• An improvement in performance must not come at a high cost in space! ... both speed and space must be accounted for ... and do not forget to take the operating system overheads into account.  
• There is no point in attaining speed if the solution is not scalable ... a scalable solution is a practical one! 
• Have fun!

Interested in learning how to efficiently implement the array hash table in C? My original implementation can be download below. Please note, however, that my software is for non-commercial use only. This means that my code (in whole or any part of it) can not be used in a commercial (profit/non-profit) environment, product or service, without my written permission. This is important. See the statement shown at the top of my code for more details. You can download the array hash here here.

Please read my papers on the array hash table and also study my code; and feel free to ask any questions you may have regarding my work.

Once understood, try beating it!  ... the array hash, however, might be a little tougher to beat than the HAT-trie, lol :)

• Your data structure must support null-terminated variable-length strings. No fancy string-terminators like '0xff' instead of '\0', which can lead to faster string comparisons.
• The length of the string can not be pre-calculated prior to using the data structure / its interfaces or API.
• No HugeTLB, custom Kernels, or over-clocked hardware.
• An improvement in performance must not come at a high cost in space! ... both speed and space must be accounted for ... and do not forget to take the operating system overheads into account.  
• There is no point in attaining speed if the solution is not scalable ... a scalable solution is a practical one! 
• Have fun!

Learn how to efficiently implement the B-tree in C along with the newer alternative, the B-trie. These data structures are disk-resident, so they are not as fast as the in-memory variants but they can scale to many hundreds of gigabytes in size. My original implementations can now be download below. Please note, however, that my software is for non-commercial use only. This means that my code (in whole or any part of it) can not be used in a commercial (profit/non-profit) environment, product or service, without my written permission. This is important. See the statement shown at the top of my code for more details. 

Please read my paper on the B-trie to better your understanding on disk-resident data structures and also study my code; and feel free to ask any questions you may have regarding my work. You can download the disk-based data structures here.

Enjoy!

Here is everything I have implemented over the years for my research on cache-efficient string data structures. Please note, however, that my software is for non-commercial use only. This means that my code (in whole or any part of it) can not be used in a commercial (profit/non-profit) environment, product or service, without my written permission. This is important. Having said that, enjoy and feel free to ask any questions you may have regarding my work. You can download the list of data structures here.

• Array hash table (see Chapter 3 and 4 of my PhD thesis).
• Standard-chain hash table
• Array burst trie
• Standard-chain burst trie
• HAT-trie (see Chapter 5 of my PhD thesis).
• Array binary search tree (BST)
• Standard-chain binary search tree (BST)
• Standard-chain splay tree
• Standard-chain red-black tree
• Standard-chain Ternary Search Trie (TST)
• Buffered B-tree
• Buffered B-trie (see Chapter 6 of my PhD thesis).
• Array hash table for 32-bit Integer keys

Please show your support by checking out some of the other links shown on this site. Thank you.

• Mark Dennehy --- Cache conscious hash tables in Java
• Mark Dennehy --- Implementing HAT-Tries in Java
• Chris Vaszauskas --- HAT-trie in C++ (GitHub)
• Hacker News Blog --- A discussion on tries
• Hash tables on Wikipedia

Subject: Thanks for the 'B-tries for Disk-based String Management' paper it was instrumental in the success of my project 			
Sender Mike*** 

Hi Dr Askitis, 

I used your ' B-tries for Disk-based String Management' paper as the basis for a Java in memory 
Burst-Trie (although it uses the hybrid and pure splitting described in your paper).

It is so much faster and efficient than the compressed patricia trie and ternary search tree's that I 
implemented at first. My primary job is to write the software used to conduct a large scale (5% sample) 
travel survey conducted over the telephone and online in Southern Ontario, Canada. 

We have a database with 50,000+ street names and municipalities and we use the Burst Trie to index them 
for fast retrieval.  At first I wrote it for use in the web survey to remove any need to hit the db 
(and associated 200ms delay) when returning matches but now we use it in our call center 
application because of its speed.

We also support any-string matching (although not ordered) by using the speed of the 
trie to store all the suffixes of indexed strings.

I was planning on writing a report documenting our use of the Burst-Trie and crediting you and Justin Zobel ... 
You will both  be credited in the Conduct of the Survey report but that probably won't be written until 2013 or 2014 ...

Thanks for your highly understandable paper, it was enormously useful when writing our Java Burst Trie implementation.

Mike***

Subject: Your work is great			
Sender Alex***

Hey there Nikolas,

My name is Alex***, I'm really excited about your work on
the cache-conscious data structures -- this is awesome. Efficient
data structures is my passion too.

It'd be absolutely great if you could send to me the paper and the
sources for the following topics:

- Cache-conscious Collision Resolution in String Hash Tables
- HAT-trie: A Cache-conscious Trie-based Data Structure for Strings
- B-tries for Disk-based String Management
... oh... you know I just have realized that I crave to consume _all_
 your papers and sources... If you would kindly agree to pass those
 magnificent pieces to me that'd be really appreciated.

I plan to build either a python implementation (using cython) or a python
wrapper for the C implementation (using ctypes) of at least the HAT-tries.
Python lacks a good space/time efficient ordered dictionary.
...

-- Alex***

Subject: Very interested in your work
Sender: Kris***

Hi Nikolas, I am very intrigued by your research.  
Would it be possible to get access to the fundamental data structures that you have been discussing in your papers?

--Kris***

Subject: Repmaestro
Sender: Nih***

Hi,

I read and enjoyed your recent work; RepMaestro. Can you send me the link to download the software please?

Best,  

The copy-based burst sort algorithm is one of the fastest in-memory sorting algorithms for variable-length strings, as detailed in the computing literature. Nonetheless, the original implementation of the copy-based burst sort by its authors is not readily available. As such, I have written my own implementation of the copy-based burst sort in C, using my knowledge of cache-conscious string data structures. I am not sure if my implementation is as fast or as memory-efficient as the original used by the authors, but given the results below, I am confident that it can serve as a good baseline for your experiments :)

My implementation of the copy-based burst sort algorithm is a little different from how its explained in literature. First, the strings that are stored in containers are length-encoded --- the original algorithm simply stored null-terminated strings. Second, containers are not sized to fit into the L2 cache of a typical CPU, as is the intention of the burst sort algorithm. Instead, much like my implementation of the array burst trie and HAT-trie, containers are burst once they store more than a given number of strings, which, in my opinion, is a simpler and more optimal approach. The table below shows preliminary results of time (in seconds) and memory (in megabytes) required to sort the DISTINCT dataset provided above (28772169 unique strings), compared to the standard Linux sort command. The machine used to conduct the experiments was the AMD server described above. The source is available below.

64-bit Copy-based burst sort for strings:
My implementation of the copy based burst sort algorithm (for non-commercial use) is provided below for your education. Enjoy! You can also access the binary for Linux x86_64 platforms here.   (Usage: ./copy-based-burstsort [container-size] [number-of-file-fragments-to-sort] [file1] [file2] ... )
Some important notes: The code below handles ASCII-7 printable characters only and supports variable-length null-terminated strings, up to 32768 characters (including the null character). If you wish to compile my source code, the command is:
gcc -O3 -fomit-frame-pointer -w -DPAGING -o nikolas_askitis_copybased_burst_sort_paging nikolas_askitis_copybased_burst_sort.c sort_module.o common_burstsort.c
Utility files: common_burstsort.c, sort_module.h, sort_module.o, sort_module.c and include/common_burstsort.h

Lets consider the performance of my data structures on a more modern computing architecture, namely an AMD II X4 965 3.2Ghz Processor installed on a high-performance Asus motherboard with 8GB of DDR2-800 dual-channel 5-5-5-15 RAM, running Linux Kubuntu 10.01 64-bit (Kernel 2.6.35-22-generic SMP x86_64). The data structures were first constructed using 28772169 (304MB) unique variable-length null-terminated strings, provided above. The time and space required to construct was captured and shown in the Table below. We then measured the time required to search the data structures using over 177 million (1.1GB) variable-length null-terminated strings (Skew Set 1, provided above). These strings are of a highly-skew distribution (as is typically observed in practice). Notice, we report the actual process size of these data structures, which is important, as this captures any space overheads and memory fragmentation caused by the allocation and frequent resizing of dynamic arrays. I have compared the performance of my data structures against the Judy trie (version 1.0.5). The results below we captured without HugeTLB.

Dr Askitis has developed dramatic improvements to some of the most fundamental string data structures used in computation by redesigning them for use on current computer architectures. His new string algorithms are much faster and require much less space than their predecessors, some of which have been the subject of research for over fifty years. These improvements have the potential to greatly improve the efficiency of a wide range of computing applications including databases, web search and data processing.