Gaurav's Blog

return rand();

Miscellaneous Project / Research Worthy Ideas [WIP]

| Comments

I would scribble some project / research - worthy ideas. That may or may not yield much benefit, but I would probably like to travel down that path some time.

  • Concurrent Linked Lists Linked Lists that can be operated on concurrently. There has been some work done on Lock-Free Linked Lists etc, probably worth checking out, and implementing.

  • Bloom Filters / Quotient Filters Definitely worth implementing an efficient Bloom Filter / Quotient Filter. An exciting research area is to design a Bloom-Filter type data structure to efficiently answer the query - “Is there an element in the range [p,q]?”, with a NO (which is guaranteed), or MAYBE (the false-positive rate should be adjustable).

  • Persistent / Temporal Data Structures See Prof. Erik Demaine’s lecture.

  • Sorting / Searching Practical In-Place Merge-Sort [PS]

  • Dynamic RMQ / LCA in O(1) time. Simplify what Cole and Hariharan did for LCA in this paper. And/or devise a dynamic RMQ mechanism which can be done in O(log n) / O(1).

  • Fractional Cascading This is a really cool idea. Read about it here. It helps speed up bounded-box queries by a log factor.

Please feel free to suggest ideas.