Re: GSOC Student Project Idea

On Apr23, 2013, at 23:25 , Alexander Korotkov <aekorotkov@gmail.com> wrote:
> I've taken a brief look on the paper and implementation. As I can see iDistance implements some global building strategy. I mean, for example, it selects some point, calculates distances from selected point to all points in dataset etc. So, it uses the whole dataset at the same time.
>

> However you can try to implement global index building in GiST or SP-GiST. In this case I think you should carefully estimate your capabilities during single GSoC project. You would need to extend GiST or SP-GiST interface and write completely new implementation of tree building algorithm. Question of how to exactly extend GiST or SP-GiST interface for this case could appear to be very hard even theoretically.

+1. That seemed to be a major roadblock to me too when I read the paper.

You could work around that by making partition identification a separate step. You'd have a function

  idist_analyze(cfg name, table name, field name)

which'd identify suitable partitions for the data distribution in table.field and store them somewhere. Such a set of pre-identified partitions would be akin to a tsearch configuration, i.e. all other parts of the iDistance machinery would use it to map points to index keys and queries to ranges of those keys. You'll want to look at how tsearch handles that, and check if the method can indeed be applied to iDistance.

In a first cut, you'd probably only allow inserts into index which don't change the maximum distances from the partition centers that idist_analyze() found. With that restriction in place, you might get away without GiST or SP-GiSt, and simply use postgres' standard btree, if you find a way to map queries of the form "field <idistance-knn-operator> idistance_knn_function(point, distance)" to "where (idstance_keys(field) between P1_lowerbound AND P2_upperbound) OR (idistance_keys(field) between P2_lowerbuild AND P2_upperbound) …" or something equivalent. 

Thank you both for the very helpful feedback. Perhaps the scope of this project (application's "completeness criteria") is better as a feasibility prototyping of the global/distance-based index strategy with B+-tree and/or GiST extension possibilities.

Let me briefly elaborate on the current implementation details related to your comments. The public C++ version uses a stand-alone STX B+-tree implementation, and has only been used in the research context of one-time data loading and indexing and then KNN retrieval performance efficiency. This requires an upfront global partition building (sequential look at all data points) and a bit of overhead information about the partitions (such as reference point locations and maximum distances in each). Of course, there are a lot of improvements, modifications, variants, etc., that can be built from this basic setup... but that's mostly my in-progress thesis work yet published or defended :)

A given query is broken down into range(s) of key values in the B+-tree, based on the negligible overhead info kept from partitioning. Only then does this small subset of pages need to be loaded from disk. where the partitions are located with respect to the query. Therefore it is necessary to have left/right leaf pointers within the B+-tree. While I think a DBMS-integrated implementation would be more ideal for general use by everyone, my naive assumption is that I could probably implement the idistance functionality in stored procedures and metadata tables (at the cost of performance and usability). 

Best regards,

Mike Schuh