Existing literature on k-Maximum Inner-Product Search has made it a common belief that tree based methods are less effective in terms of index construction time and query performance compared to locality sensitive hashing based, similarity graph based and quantization based methods. However, in this paper we partially roll over the existing assessments about tree based k- Maximum Inner-Product Search methods by our newly proposed tree structure named LRUS-CoverTree. The experimental results show that the new k- Maximum Inner-Product Search algorithm based on LRUS-CoverTree outperforms the state-of-the-art locality sensitive hashing based methods, and achieves comparable performance with similarity graph based and quantization based methods in terms of query time and accuracy. What's more important, the desirable query performance is attained with significantly lower index construction time compared to all the other methods. Besides the experimental evaluations, substantial theoretical results about the LRUS-CoverTree and the new k-Maximum Inner-Product Search algorithm are provided, including construction time and search time complexity, size and height of the tree, and so on. Furthermore, several new effective upper bounds on the inner-product value are provided to support the efficient branch-and-bound algorithm on LRUS-CoverTree. In summary, our novel tree structure and new algorithm significantly improve upon existing tree based methods, and it is hoped that this contribution can lead to a reconsideration of tree based k-Maximum Inner-Product Search methods.

This paper presents a new approach for semi-external topological sorting algorithm on big directed acyclic graph(DAG). Topological sorting aims to find an ordering of each node in DAG, which satisfies$u$precedes$v$in the ordering for each edge$(u,v)$in DAG. Topological sorting is an important subroutine for scheduling and other external graph algorithms. But, the internal topological sorting algorithm cannot handle big DAGs and the I/O complexity of total external topological sorting is too high for practical applications. Therefore, we pay attention to the semi-external topological sorting for big DAGs in this paper. We find that the existing semi-external topological sorting algorithm is mainly based on constructing a DFS-Tree in internal memory. However, this DFS-based algorithm is natively more difficult than topological sorting, because DFS-Tree determines a strict total order, while topological order is only a partial order. Therefore, a partial orderlevel orderis proposed in this paper. Based on thelevel order, we propose a new semi-external topological sorting algorithm. Next, two optimizations,NodeRemoveandEdgeRemove, are proposed to reduce the CPU and I/O cost. In addition, we also propose a batch algorithm. Finally, we perform experimental studies using real and synthetic datasets to confirm the efficiency of our approach. According to the experimental results, our algorithms are better than the previous DFS-based algorithms.