name of picture
Picture taken in Seattle, USA.
Credits: Mythrills


  • Employment News. I will be starting a postdoc at UIUC! My hosts are Prof. Timothy Chan and Prof. Sariel Har-Peled.

  • [Feb 2017] My solo author paper on approximate range counting has been accepted at SoCG 2017!!!

  • [November 2016] Visited University of Waterloo, Canada to work with Prof. Timothy Chan.

  • [Summer 2015] I will be doing an internship at Microsoft Research in Redmond, Washington.

  • [Spring 2015] My paper along with Prof. Yufei Tao has been accepted at PODS 2015.

  • [Fall 2014] My paper (solo author) on rectangle stabbing and point location in three-dimensions has been accepted at SODA :) Hurray !!!

  • [Spring 2014] I have been awarded Doctoral Dissertation Fellowship (DDF) for 2014-15 by Univeristy of Minnesota.

  • [Spring 2012] Visited CUHK, Hong Kong to work with Prof. Yufei Tao.

  • [Fall 2012] Awarded first prize for my presentation in "Fast Forward Preview Session" at ACM SIGSPATIAL GIS 2012.

  • [Fall 2011] Awarded the UMN Computer Science department fellowship for Fall 2011.

Rahul Saladi

Ph.D., Computer Science and Engineering, University of Minnesota Twin Cities.

Advisor: Prof. Ravi Janardan
Email: sala0198 [at] umn [dot] edu


Rahul Saladi got Ph.D. from the Computer Science and Engineering dept. at University of Minnesota. He obtained his bachelor's degree and master's degree in computer science from IIIT-Hyderabad. Rahul has been awarded the Computer Science Fellowship in Fall 2011 and the Doctoral Dissertation Fellowship (DDF) for the 2014-15. At the Fast Forward Preview Session at ACM SIGSPATIAL GIS 2012 he was awarded the first prize for his presentation. He has published his work in top theoretical computer science venues (SODA, SoCG, PODS) and in a top databases venue (TKDE).

Research Interests

Geometric algorithms and data structures, Computational geometry, Algorithms for spatial databases.

On one hand, I like to build non-trivial data structures and algorithms for geometric problems which come with theoretically strong guarantees in terms of their performance. On the other hand, for geometric problems arising in spatial databases I also like to build prototype systems with provably good theoretical bounds.

Manuscripts in Submission

Timothy Chan, Saladi Rahul, Konstantions Tsakalidis
Optimal Orthogonal Point Location in 3-d
Our result: A fundamental problem in computational geometry for which we provide an optimal solution in the pointer machine model and the I/O-model.

Saladi Rahul
A Linear-Time Algorithm to Compute the Approximate Number of Inversions

Our result: Counting inversions in an array is a texbook problem in computer science. The number of inversions, K, in a list L =(L(1), L(2),..., L(n)) is defined as the number of pairs i < j with L(i) > L(j). This work presents a linear-time algorithm to compute the approximate value of K. The state-of-the-art linear-time algorithm [Chan and Patrascu, SODA'10] works for the special case where L is a permutation, i.e., each L(i) is a distinct integer in the range [1, n]. Our algorithm does not put any such restriction, i.e., L(i) can be any real-value.


Saladi Rahul.
Approximate Range Counting Revisited [Arxiv]
33rd International Symposium on Computational Geometry (SoCG 2017)

Prosenjit Gupta, Ravi Janardan, Saladi Rahul, Michiel Smid.
Computational Geometry: Generalized (or Colored) Intersection Searching [PDF]
Handbook of Data Structures and Applications, Sartaj Sahni and Dinesh Mehta eds., CRC Press, 2nd Edition. (To Appear).

Saladi Rahul, Yufei Tao.
Efficient Top-k Indexing via General Reductions [PDF]
35th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), 2016

Saladi Rahul.
Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in R3 [PDF][Slides]
ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)

Saladi Rahul, Yufei Tao.
On Top-k Range Reporting in 2D Space [PDF]
34th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), 2015

Akash Agrawal, Saladi Rahul, Yuan Li, Ravi Janardan.
Range search on tuples of points [PDF]
Journal of Discrete Algorithms 30: 1-12 (2015)

Saladi Rahul, Ravi Janardan.
A General Technique for Top-k Geometric Intersection Query Problems[PDF]
IEEE Transactions on Knowledge and Data Engineering (IEEE TKDE), 2014.

Saladi Rahul, Ravi Janardan.
Algorithms for Range-Skyline Queries[PDF]
20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS), 2012.

Haritha Bellam, Saladi Rahul, Krishnan Rajan.
Colored Range Searching on Internal Memory[PDF]
Proc. of 17th International Conference on Database Systems for Advanced Applications (DASFAA), pages 111-125, 2012.

Saladi Rahul, Prosenjit Gupta, K. S. Rajan.
Data Structures for Range-Aggregation over Categories[PDF]
International Journal of Foundations of Computer Science, 22(7): 1707-1728, 2011.

Saladi Rahul, Prosenjit Gupta, Ravi Janardan, K. S. Rajan.
Efficient Top-k Queries for Orthogonal Ranges [PDF]
Proc. of 5th International Workshop on Algorithms and Computation (WALCOM), pages 110-121, 2011.

Saladi Rahul, Ananda Swarup Das, K. S. Rajan, Kannan Srinathan.
Range-Aggregate Queries Involving Geometric Aggregation Operations[PDF]
Proc. of 5th International Workshop on Algorithms and Computation (WALCOM), pages 122-133, 2011.

Saladi Rahul, Haritha Bellam, Prosenjit Gupta, Krishnan Rajan.
Range aggregate structures for colored geometric objects[PDF]
Proc. of 22nd Annual Canadian Conference on Computational Geometry (CCCG), pages 249-252, 2010.

Saladi Rahul, Prosenjit Gupta, K. S. Rajan.
Data Structures for Range Aggregation by Categories [PDF]
Proc. of 21st Annual Canadian Conference on Computational Geometry (CCCG), pages 133-136, 2009.

Back to top

Last updated 07/18/12 -- Page Design based on UC Berkely HTML Templates Web Analytics