Saladi Rahul
B.Tech and MS by research in Computer Science Engineering

Areas of Interest Algorithms and Data Structures, Computational Geometry, Moving Objects Databases

Email: srahul**



Research:

I work in the field of Computational Geometry which deals with building efficient data structures and algorithms for various geometrical problems which have real-world applications. Specifically, I have worked on Range-Aggregate Queries and Moving Objects Databases

  • Range-Aggregate Queries
  • The problems tackled in my thesis revolved around range-aggregate queries for geometric objects. Given a set 'S' of geometric objects and a query region 'q', a standard intersection problem (e.g. range searching, point enclosure, halfspace range searching) simply reports or counts the objects of 'S' intersecting 'q'. In many applications such as OLAP, VLSI, GIS etc., it is more useful to consider 'range-aggregate' version of these problems wherein we need to efficiently compute some aggregate function of the objects of 'S' intersecting 'q'.

  • Moving Objects Databases
  • This is a relatively new field of research that has received a lot of interest in recent years. The general goal of this research is to allow one to represent moving entities in databases and to ask queries about such movements. Moving entities could be cars, trucks, aircraft, ships, mobile phone users, terrorists, or polar bears.

    An interesting problem was to detect if a collision will occur among objects moving in a time-parameterized motion inside a given query region. A brute-force method takes O(n*n) (quadratic) query time. The objective was to come up with o(n*n) (sub-quadratic) query time solution while using linear or near-linear space. We also introduced and implemented an external memory data structure (named ETPR-tree) built upon a set of moving objects (which are subject to updates) to predict which of them would lie within a query region and a future query time-interval.

    Publications:

    Unpublished Reports