14

Suppose that you have a large collection of key/value pairs, where the value is some arbitrary real number. You're interested in creating a data structure supporting the following operations:

  • Insert, which adds a new key/value pair to the collection,
  • Delete, which removes a key/value pair from the collection,
  • Percentile, which tells which percentile the value associated with a given key is in, and
  • Tell-Percentile, which accepts a percentile number and returns the key whose value is the lowest value at at least the given percentile.

This data structure could be used, for example, to efficiently determine what percentile a given student is in when receiving a stream of nationwide test scores, or to identify hospitals that have unusually good or bad quality of service.

Is there a way to make these operations run efficiently (say, sublinear time?)

GEOCHET
  • 21,119
  • 15
  • 74
  • 98
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • If you want to look up the *same* percentile every time, you can maintain a pair of heaps to hold values above/below the desired percentile. See http://stackoverflow.com/questions/3738349/fast-algorithm-for-repeated-calculation-of-percentile/3738476#3738476 – Peter Cordes Oct 26 '15 at 11:57

2 Answers2

14

One possible way to implement this data structure is to use a hybrid of an order statistic tree and a hash table.

An order statistic tree is a type of balanced binary search tree that, in addition to the normal binary search tree operations, supports two more operations:

  • Rank(key), which returns the number of elements in the tree smaller than a given element, and
  • Select(k), which returns the kth smallest element in the tree.

Order statistic trees can be built by augmenting a normal balanced binary search tree (say, a red/black tree or an AVL tree) with extra information that is preserved during rotations. In this way, all of the normal BST operations on an order statistic tree can be made to run in O(log n) time, with the extra operations also running in O(log n) time.

Now, let's suppose that you were purely storing values scores, rather than key/percentile scores. In this case, it would be very simple to implement the percentile lookups as follows. Store all of the values in the order statistic tree. To determine the percentile score for a given value, use the rank operation on the order statistic tree to look up what index that value appears at. This gives a number, in the range from 0 to n - 1 (where n is the number of elements in the tree), denoting the position of that score in the order statistic tree. You can then multiply that number by 99 / (n - 1), to get a percentile score for the value that runs in the range from 0 to 99, as required.

To determine the lowest value greater than some percentile, you can use the select operation as follows. Given a percentile between 0 and 99, multiple that percentile by 99 / (n - 1) to get a real number between 0 and n - 1, inclusive. Taking the ceiling of that number produces a natural number in the range 0 to n - 1, inclusive. Using the select operation on the order statistic tree then can be used to find the first value in the range that is at or above the given percentile.

However, these operations assume that we have purely values in the data structure, not key/value pairs. To make this operation work for key/value pairs, we will augment our data structure as follows:

  1. Rather than just storing values, we will store key/value pairs in each node. The order statistic tree will sort the key/value pairs purely by their value, with the key carried around as satellite data.
  2. We will store a secondary hash table that maps keys to their associated values.

These two changes make it possible to implement the needed functionality for our data structure. To get the data structure to do percentile lookups by key, we first query the hash table with the given key to look up its associated value. We then do a percentile lookup on the value as done before. To get the data structure to tell us a key whose value is the first at or above a given percentile, we do a normal find-percentile operation on the order statistic tree as described above, then look up the key associated with the given value.

If we assume that the hash table uses chained hashing, then the time required for each operation is given below:

  • Insert: O(log n) time to insert the value/key pair into the order statistic tree, plus O(1) amortized time to insert the key/value pair into the hash table. Total time is O(log n) amortized.
  • Delete: O(log n) time to delete the value/key pair from the order statistic tree, plus (1) amortized time to delete the key/value pair from the hash table. Total time is O(log n) amortized.
  • Percentile: O(1) expected time to look up the value associated with the key, O(log n) time to do the rank operation, and O(1) extra time to map the rank to a percentile. Total time is O(log n) expected.
  • Find-Percentile: O(1) time required to map the percentile to a rank, and O(log n) time required to do the select operation. Total time is O(log n) worst-case.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
2

There is a simple and highly efficient possibility:

If you can live with searching the percentile only in a finally filled up students structure then:

Use an ArrayList to dynamically build up when you don't know the number of elements.
If you know them then start with the array directly, otherwise create the array from the dynamic array. (e.g ArrayList in java).

insert: not neccesary, replaced by adding at end, and sorting once.
delete: not neccessary, if you can live with that.
tell-percentile: even simpler: something very near to: element[length * percentile]: O(1)

In practise the array approach will be much faster than the balanced tree approach, at least in java, when your application can build up the array once (e.g daily student evaluation, build it up daily)

I have implemented the (my) above algorithm using an self written ArrayListInt, which does the same as ArrayList but uses primitive types (double, int), instead of objects types. I sorted it once, when all data have been read.

Further you wanted key value:
I would just add an Tree Map (balanced tree). Now it is a bit doubtfull if the TreeMap and the additonal percentile array make sense: That depends then on how often you have to search, and memory usage versus search time.

Update:

Results: treeset vs sorted array (dynamic build up the array, then finally sort once:

num elements: 1000 treeSet: 4.55989 array=0.564159
num elements: 10000 treeSet: 2.662496 array=1.157591
num elements: 100000 treeSet: 31.642027 array=12.224639
num elements: 1000000 treeSet: 1319.283703 array=140.293312
num elements: 10000000 treeSet: 21212.307545 array=3222.844045

This ammount of elements (1e7) now is near the limit (1GB heap space) , in the next step memory would run out (already happedned at 1e7, but with cleaning up memory after treeset, the run for measure 1e7 worked, too.

What is missing are the search times, but an sorted array with binsearch is only beatable by an hashtable

Finally: If you can build up the student set once, e.g daily, then using the array approach gives a much simpler percentile search.

AlexWien
  • 28,470
  • 6
  • 53
  • 83
  • 1
    -1: Yikes - it seems you may have fundamentally misunderstood complexity analysis. The fact that an `O(N)` approach may be faster than an `O(log(N))` approach for a specific (small) value of `N` *does not* mean that the `O(N)` approach is *always* better, as you've stated. The whole point of Big O analysis is asymptotic performance - as `N` tends to larger values the `O(log(N))` approach will win out over the `O(N)`, irrespective of constant/lower-order factors. – Darren Engwirda Dec 21 '12 at 23:17
  • 2
    Are you really sure that memcopy can move 10000 elements faster than a BST lookup of a 10000 element tree? With modern memory allocators optimizing for locality, I'd be very skeptical that this is true. Can you back this up with some data or a reference? – templatetypedef Dec 21 '12 at 23:18
  • @Yikes: I wrote: in practise always win, that means fo real applications, not for a benchmark where you feed MAX_INT elements into. further do not forget memory usgage, if the computer runs out out of memory before the O(ld N) wins over the O(N) then you can be in a situation that the O(ld N) due higher memeroy usgae can never benefit from its asymptotical advantage. – AlexWien Dec 21 '12 at 23:35
  • @templatetypedef num elements 50.000, Operation: insert in middle, ArrayList (memcopy) vs LinkedList (pointer re-asigning): addMiddleTest() to array list took 735 addMiddleTest() to linked list using general methods took 11688 addMiddleTest() to linked list using linked list methods took 8406; see for example: http://chaoticjava.com/posts/linkedlist-vs-arraylist/ so the arraylist has to move 25.000 elements to the right when inserting into the middle, while the Linkedlist has to reasign only two pointers, and still is 10 times slower, at 50.000 elements. – AlexWien Dec 21 '12 at 23:54
  • @AlexWien: Could you provide us with some data to back up your claims?? I'd be interested to know the runtime stats for building a BST vs. maintaining a sorted array (with your binary search + insertion approach) for `N = {1e3, 1e4, 1e5, 1e6}`. – Darren Engwirda Dec 21 '12 at 23:57
  • 2
    @AlexWien- I could be wrong about this, but I'm fairly confident that the slowdown you're seeing is because the linked list has to traverse half of the list to find the insertion point. In other words, both the array and linked lists have to do O(n) work: the array for the shuffling, and the list for the searching. I seriously doubt that this generalizes to mean a huge BST will be slower than a huge array. All my practical experience contradicts what you're claiming. – templatetypedef Dec 22 '12 at 00:13
  • @templatetypedef in my above statemet i forgot that the LinkedList cannot apply a binary search to find the inserting position like Array and tree. So it would loose all time in itertaing and cannot gain in fast insert / delete – AlexWien Dec 22 '12 at 00:26
  • @templatetypedef yes, in the meantime you have answered, and pointed out that the iteration which cannot use bin search is the problem. I searched but did not find any performance comparsion between ArrayList and a balanced binary Tree like javas TreeSet, do you know any? – AlexWien Dec 22 '12 at 00:29
  • 1
    @templatetypedef My old approach was wrong, keeping the array sorted is not a good idea, so i changed to build up the array and sort it once, which is easiest and probaly fastest, if you live with the limitaion of immutable structure once build up. (For values up to 100k I still would use the array approach even for dynamic structure, becuase its cheaper to implement): Answer updated – AlexWien Dec 22 '12 at 14:02