Efficient feasibility checking algorithms for intersection-tree construction
Kun Ji · 2021
Rank-aware queries let users specify functions to score the records in a relation. An input to the functions produces a score for each record, which can be used for purposes such as ranking. While this feature makes rank-aware queries essential to a whole range of applications such as data analysis, the involvement of scoring functions makes them difficult to process. For example, to find the record at a particular rank under a function input, the current common approach is to compute the score for every record and sort them out. In a prior research, it is shown that given a set of records and their scoring functions, the domain of these functions can be partitioned into a number of disjointed subdomains such that the functions can be sorted according to their scores in each subdomain. A novel data structure called {\em Intersection-tree} (I-tree) was subsequently developed to compute the subdomains and sorted functions for each subdomain. The tree supports efficient search of the subdomains and the sorted function lists, where users can retrieve various types of rank-aware information, such as top k and the rank of a record of interest. The extensive evaluation confirms that I-tree is more efficient than other techniques when compared head to head. The I-tree, unfortunately, is computation-intensive to construct for a large number of records. A set of $n$ $d$-variable linear functions, each used to score one record, can create a total of $O(n^2)$ intersections, which together can partition their domain into $O(n^{2d})$ subdomains. These subdomains are computed and indexed while the intersections are inserted one by one to the tree. A major computation in this insertion process is feasibility checking, i.e., given a set of inequalities and an equation $f(X)=0$, determine whether there exist two distinct inputs $X^{'}$ and $X^{"}$ that satisfy all the inequalities, and $f(X^{'}) 0$. The original implementation applies the classic simplex algorithm to perform these checkings with a significant amount of unnecessary computation and thus is not efficient. In this thesis, we study the characteristics of I-tree and propose two approaches that minimize of the cost of feasibility checking in I-tree construction: 1) reduce the complexity of feasibility checking, and 2) reuse intermediate results for the next feasibility checking along the insertion path. We implement the proposed methods, evaluate their performance under various settings, and report the results in this thesis.